On Sunday, 6 July 2014 at 21:31:57 UTC, Dmitry Olshansky wrote:
Strawman.
...
Again your ignorance of what a struct could do shows.
...
Plain wrong. Again seeing you have strong Java background,
isn't particularly surprising.
...
Ignorance.
On Sunday, 6 July 2014 at 04:20:21 UTC, Timon Gehr
On Monday, 7 July 2014 at 10:55:38 UTC, Wanderer wrote:
I'm starting to think that D community should grow up few more
years before reasonable discussion is possible.
Last few days, I became disappointed in D - not because the
language is rather immature and unstable yet, but mainly
because
On Sunday, 6 July 2014 at 04:20:21 UTC, Timon Gehr wrote:
That's not 'merely holding a pointer' and it applies to class
references just as much.
Eh?
This is genius, you've just proven that references are as
unsafe as pointers, and people who spent much time and efforts
designing the whole
Please don't under-quote, thanks.
Pointers are perfectly fine as long as there is no pointer arithmetic.
Wrong. Merely holding a pointer (i.e. a physical address) is unsafe already.
Non-deep serialization, or any other preservation of such a struct and GC
is unable to keep the track of
06-Jul-2014 07:19, Wanderer пишет:
On Saturday, 5 July 2014 at 16:03:17 UTC, Dmitry Olshansky wrote:
There are trade-offs. The world is not black and white and I don't
follow 'one rule everywhere'.
This is not a trade-off at all. You suggested to keep database records
linearly, with space
On Friday, 4 July 2014 at 12:18:54 UTC, Daniel Murphy wrote:
Yes they do.
http://en.wikipedia.org/wiki/Database_index#Clustered
You can obviously only do that for one index.
Ugh, and what happens in such hypothetical database if you update
its first row so it becomes 1 byte longer than
05-Jul-2014 18:02, Wanderer пишет:
On Friday, 4 July 2014 at 12:18:54 UTC, Daniel Murphy wrote:
Yes they do. http://en.wikipedia.org/wiki/Database_index#Clustered
You can obviously only do that for one index.
Ugh, and what happens in such hypothetical database if you update its
first row so
On Saturday, 5 July 2014 at 14:20:33 UTC, Dmitry Olshansky wrote:
Provision some extra space in each record. DBs do this all the
time, regardless of layout.
Which means waste of space you complained about just below.
Besides, you understand this is not a solution: one byte more
than that
05-Jul-2014 19:08, Wanderer пишет:
On Saturday, 5 July 2014 at 14:20:33 UTC, Dmitry Olshansky wrote:
Provision some extra space in each record. DBs do this all the time,
regardless of layout.
Which means waste of space you complained about just below.
There are trade-offs. The world is not
Wanderer wrote in message news:jbvbufgyhbjrkpukr...@forum.dlang.org...
For pair of integers, you can use long and sort an array of longs.
Awesome, now your sort order depends on processor endianness!
Storing structs in contiguous memory is sometimes better for some things.
The fact that
On 07/05/2014 07:07 PM, Daniel Murphy wrote:
Wanderer wrote in message news:jbvbufgyhbjrkpukr...@forum.dlang.org...
For pair of integers, you can use long and sort an array of longs.
Awesome, now your sort order depends on processor endianness!
?
k=i32|j, i=k32, j=k(1L32)-1.
On Saturday, 5 July 2014 at 16:03:17 UTC, Dmitry Olshansky wrote:
There are trade-offs. The world is not black and white and I
don't follow 'one rule everywhere'.
This is not a trade-off at all. You suggested to keep database
records linearly, with space gaps between records to support
tiny
On 07/06/2014 05:19 AM, Wanderer wrote:
On Saturday, 5 July 2014 at 16:03:17 UTC, Dmitry Olshansky wrote:
...
Pointers are perfectly fine as long as there is no pointer arithmetic.
Wrong. Merely holding a pointer (i.e. a physical address) is unsafe
already. Non-deep serialization, or any
Wanderer wrote in message news:aroorrxjloihxtthk...@forum.dlang.org...
Databases don't sort their records physically. The main reason
for that is that each record has many columns so there are many
various possible sort orders.
Yes they do.
On Monday, 23 June 2014 at 16:33:13 UTC, Chris Cain wrote:
It's not really about the time complexity but the absolute time
it must take. But I showed the example that shows that the fact
that any stable sort must do extra work:
[2,2,2,2,1]
An unstable sort may swap the first 2 and the 1
On 7/3/14, 12:29 AM, Wanderer wrote:
Nobody, never, measures sort algorithms by amount of swaps.
That... is quite the claim. -- Andrei
On Thursday, 3 July 2014 at 07:29:42 UTC, Wanderer wrote:
Nobody, never, measures sort algorithms by amount of swaps.
What if you're sorting a large database with large records?
On 03/07/2014 9:13 AM, Andrei Alexandrescu wrote:
On 7/3/14, 12:29 AM, Wanderer wrote:
Nobody, never, measures sort algorithms by amount of swaps.
That... is quite the claim. -- Andrei
Most of the algorithm rankings I am aware of list both compares and
swaps, because which one has the
On Thursday, 3 July 2014 at 10:13:20 UTC, ed wrote:
What if you're sorting a large database with large records?
Databases don't sort their records physically. The main reason
for that is that each record has many columns so there are many
various possible sort orders.
Instead, databases
On Thursday, 3 July 2014 at 11:30:57 UTC, Alix Pexton wrote:
Saying that one is always more significant than the other is
far too much of an oversimplification.
I just thought, with the presence of structs in D, things are not
that simple. Structs don't use references and their contents is
On Thursday, 3 July 2014 at 15:40:33 UTC, Wanderer wrote:
On Thursday, 3 July 2014 at 11:30:57 UTC, Alix Pexton wrote:
Saying that one is always more significant than the other is
far too much of an oversimplification.
I just thought, with the presence of structs in D, things are
not that
On 03/07/2014 4:16 PM, Wanderer wrote:
On Thursday, 3 July 2014 at 11:30:57 UTC, Alix Pexton wrote:
and how it is stored (all in a single page of memory vs across
multiple networked disks vs in immutable memory such that each swap
actually duplicate the whole dataset).
And how much of that
On Thursday, 3 July 2014 at 07:29:42 UTC, Wanderer wrote:
Nobody, never, measures sort algorithms by amount of swaps.
Maybe not in swaps, but I have seen sorting algorithms measured
similarly using reads and writes. As others have stated, it can
be a useful metric if you're sorting a range
On Monday, 23 June 2014 at 16:33:13 UTC, Chris Cain wrote:
It's not really about the time complexity but the absolute time
it must take. But I showed the example that shows that the fact
that any stable sort must do extra work:
[2,2,2,2,1]
[...]
I'm sorry if i'm going to say some stupid
On Tuesday, 24 June 2014 at 09:22:24 UTC, Andrea Fontana wrote:
On Monday, 23 June 2014 at 16:33:13 UTC, Chris Cain wrote:
It's not really about the time complexity but the absolute
time it must take. But I showed the example that shows that
the fact that any stable sort must do extra work:
On Tuesday, 24 June 2014 at 16:37:06 UTC, Chris Cain wrote:
Of course, that's yet more playing around with restrictions.
Plus your proposed relaxed stable sort is also the same as
relaxed unstable sort so your restriction just made them
identically fast.
By relaxed here, I was thinking in
On Monday, 23 June 2014 at 17:26:47 UTC, Andrei Alexandrescu
wrote:
Corollary: the default sorting algorithm in std will always be
unstable, even if for certain data types and inputs it will
produce stable sorting. -- Andrei
I'd also like to note that this whole discussion about
restrictions
On Sunday, 22 June 2014 at 17:34:15 UTC, Nick Sabalausky wrote:
On 6/21/2014 1:40 AM, Tofu Ninja wrote:
On another note, if someArray.sort() calls the built in sort
even when
std.algorithm is imported, then most definitely built in sort
needs to
go, I can see plenty of times where people
On Sun, 22 Jun 2014 13:33:55 -0400, Nick Sabalausky
seewebsitetocontac...@semitwist.com wrote:
On 6/21/2014 1:40 AM, Tofu Ninja wrote:
On another note, if someArray.sort() calls the built in sort even when
std.algorithm is imported, then most definitely built in sort needs to
go, I can see
On Sat, 21 Jun 2014 07:50:29 -0400, Marc Schütz schue...@gmx.net wrote:
On Saturday, 21 June 2014 at 05:40:32 UTC, Tofu Ninja wrote:
On Saturday, 21 June 2014 at 03:52:54 UTC, logicchains wrote:
Blog author here, I've added a note that D's sort matches the speed of
C++'s when the stable sort
On Fri, 20 Jun 2014 23:52:52 -0400, logicchains
jonathan.t.barn...@gmail.com wrote:
Blog author here, I've added a note that D's sort matches the speed of
C++'s when the stable sort is used instead of the default unstable. I
don't think there's anything wrong with D's unstable sort
Steven Schveighoffer:
The only thing I can think of that won't work is sorting an
array of char or wchar, which std.algorithm.sort will not do
(right?).
The solution I have suggested is:
myString.representation.sort().release.unrepresentation
(Where unrepresentation is not yet present in
Steven Schveighoffer:
Do we need an unstable sort then? Or is this a corner case?
Probably is a corner case. And the current stable sort is good.
Bye,
bearophile
On Monday, 23 June 2014 at 15:19:15 UTC, Steven Schveighoffer
wrote:
Is it just me, or does this seem unintuitive? I would think a
stable sort requires extra care, i.e. extra time, to ensure
stability.
Do we need an unstable sort then? Or is this a corner case? I
am fully ignorant on these
How can this be proven?
Is it valid only for swap-based sorting algorithms?
For example, radix sort is stable and its complexity is O(kn). Is
there a faster unstable sort?
On Monday, 23 June 2014 at 15:38:25 UTC, Chris Cain wrote:
Technically, you can prove that there exists some unstable
Whoops, comparison based
On Monday, 23 June 2014 at 15:57:12 UTC, Andrea Fontana wrote:
How can this be proven?
Is it valid only for swap-based sorting algorithms?
For example, radix sort is stable and its complexity is O(kn).
Is there a faster unstable sort?
On Monday, 23 June 2014 at
On Mon, 23 Jun 2014 11:38:24 -0400, Chris Cain zsh...@gmail.com wrote:
On Monday, 23 June 2014 at 15:19:15 UTC, Steven Schveighoffer wrote:
Is it just me, or does this seem unintuitive? I would think a stable
sort requires extra care, i.e. extra time, to ensure stability.
Do we need an
On Monday, 23 June 2014 at 15:57:12 UTC, Andrea Fontana wrote:
How can this be proven?
Is it valid only for swap-based sorting algorithms?
For example, radix sort is stable and its complexity is O(kn).
Is there a faster unstable sort?
It's not really about the time complexity but the
Corollary: the default sorting algorithm in std will always be unstable,
even if for certain data types and inputs it will produce stable
sorting. -- Andrei
On Monday, 23 June 2014 at 17:25:13 UTC, Andrei Alexandrescu
wrote:
Second, there are known reasons and setups where Timsort and
derivatives fare better than classic quicksort-based
implementations, and generalizing them into some magic stable
sort is just better umbrella argument is just odd.
Sent: Monday, June 23, 2014 at 10:26 AM
From: Andrei Alexandrescu via Digitalmars-d digitalmars-d@puremagic.com
To: digitalmars-d@puremagic.com
Subject: Re: Optimizing Java using D
Corollary: the default sorting algorithm in std will always be unstable,
even if for certain data types
On 6/21/14, 8:28 AM, Xinok wrote:
On Saturday, 21 June 2014 at 09:19:19 UTC, Joseph Rushton Wakeling via
Digitalmars-d wrote:
I can't find the issue in bugzilla, but IIRC there was a problem with
unstable sort where it would produce worst-case-scenario behaviour in
the event of being given
On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu
wrote:
On 6/21/14, 8:28 AM, Xinok wrote:
That has since been fixed. I implemented heapsort as a fallback
algorithm, effectively making it an introsort.
Wait, when did that happen? I think a better solution would be
to take median
On 6/22/14, 7:47 AM, Xinok wrote:
On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu wrote:
On 6/21/14, 8:28 AM, Xinok wrote:
That has since been fixed. I implemented heapsort as a fallback
algorithm, effectively making it an introsort.
Wait, when did that happen? I think a better
On Sunday, 22 June 2014 at 15:51:13 UTC, Andrei Alexandrescu
wrote:
On 6/22/14, 7:47 AM, Xinok wrote:
On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu
wrote:
On 6/21/14, 8:28 AM, Xinok wrote:
That has since been fixed. I implemented heapsort as a
fallback
algorithm, effectively
On 6/21/2014 1:40 AM, Tofu Ninja wrote:
On another note, if someArray.sort() calls the built in sort even when
std.algorithm is imported, then most definitely built in sort needs to
go, I can see plenty of times where people would not even realize they
were calling the wrong sort or even that
On 6/22/14, 10:07 AM, Xinok wrote:
On Sunday, 22 June 2014 at 15:51:13 UTC, Andrei Alexandrescu wrote:
On 6/22/14, 7:47 AM, Xinok wrote:
On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu wrote:
On 6/21/14, 8:28 AM, Xinok wrote:
That has since been fixed. I implemented heapsort as
On Fri, 2014-06-20 at 23:59 +, bearophile via Digitalmars-d wrote:
Walter Bright:
If you could submit a bugzilla issue and include the faster
version, that would be great!
My faster version is also doing lot of memory swaps (so it's
not faster in all cases), and it's not generic
On 21/06/14 03:48, Peter Alexander via Digitalmars-d wrote:
On Saturday, 21 June 2014 at 01:07:20 UTC, safety0ff wrote:
std.algorithm.sort with SwapStrategy.unstable is considerably slower than his,
whereas builtin sort is abysmal.
I find that generally using SwapStrategy.stable performs
On Saturday, 21 June 2014 at 05:40:32 UTC, Tofu Ninja wrote:
On another note, if someArray.sort() calls the built in sort
even when std.algorithm is imported, then most definitely built
in sort needs to go, I can see plenty of times where people
would not even realize they were calling the
On Saturday, 21 June 2014 at 05:40:32 UTC, Tofu Ninja wrote:
On Saturday, 21 June 2014 at 03:52:54 UTC, logicchains wrote:
Blog author here, I've added a note that D's sort matches the
speed of C++'s when the stable sort is used instead of the
default unstable. I don't think there's anything
On Saturday, 21 June 2014 at 09:19:19 UTC, Joseph Rushton
Wakeling via Digitalmars-d wrote:
I can't find the issue in bugzilla, but IIRC there was a
problem with unstable sort where it would produce
worst-case-scenario behaviour in the event of being given input
that had only a few unsorted
On 21/06/14 17:28, Xinok via Digitalmars-d wrote:
That has since been fixed. I implemented heapsort as a fallback algorithm,
effectively making it an introsort.
Fantastic, thanks very much for that. :-)
http://www.reddit.com/r/programming/comments/28mp3m/the_magic_forest_problem_revisited_optimising/
The article indicates there may be a performance problem with std.algorithm.sort
Walter Bright:
The article indicates there may be a performance problem with
std.algorithm.sort
Yes, Phobos unstable sort is not fast (years ago I have shown
here a faster one). And the keySort of Phobos (my brain refuses
to learn its spelling) is even slower.
Bye,
bearophile
On 6/20/2014 4:42 PM, bearophile wrote:
Walter Bright:
The article indicates there may be a performance problem with std.algorithm.sort
Yes, Phobos unstable sort is not fast (years ago I have shown here a faster
one). And the keySort of Phobos (my brain refuses to learn its spelling) is even
Walter Bright:
If you could submit a bugzilla issue and include the faster
version, that would be great!
My faster version is also doing lot of memory swaps (so it's
not faster in all cases), and it's not generic enough for the
current ranges, and it doesn't switch to a safe O(n ln n) sort
On Friday, 20 June 2014 at 23:34:32 UTC, Walter Bright wrote:
http://www.reddit.com/r/programming/comments/28mp3m/the_magic_forest_problem_revisited_optimising/
The article indicates there may be a performance problem with
std.algorithm.sort
I get the feeling that, because he is utilizing
Xinok:
I get the feeling that, because he is utilizing UFCS, that it
is actually calling the built-in array sort and not
std.algorithm.sort. The built-in sort is 3-4x slower, so that
would explain why his naive quicksort implementation was faster.
Please deprecate/kill the built-in sort
On Saturday, 21 June 2014 at 00:47:23 UTC, bearophile wrote:
Xinok:
I get the feeling that, because he is utilizing UFCS, that it
is actually calling the built-in array sort and not
std.algorithm.sort. The built-in sort is 3-4x slower, so that
would explain why his naive quicksort
On Friday, 20 June 2014 at 23:34:32 UTC, Walter Bright wrote:
http://www.reddit.com/r/programming/comments/28mp3m/the_magic_forest_problem_revisited_optimising/
The article indicates there may be a performance problem with
std.algorithm.sort
2 lessons :
1. Kill the builtin sort function. He
On Saturday, 21 June 2014 at 00:56:32 UTC, deadalnix wrote:
On Friday, 20 June 2014 at 23:34:32 UTC, Walter Bright wrote:
http://www.reddit.com/r/programming/comments/28mp3m/the_magic_forest_problem_revisited_optimising/
The article indicates there may be a performance problem with
On Friday, 20 June 2014 at 23:34:32 UTC, Walter Bright wrote:
http://www.reddit.com/r/programming/comments/28mp3m/the_magic_forest_problem_revisited_optimising/
The article indicates there may be a performance problem with
std.algorithm.sort
I just tested his code, std.algorithm.sort with
safety0ff:
I just tested his code, std.algorithm.sort with
SwapStrategy.stable is much faster than his quicksort.
std.algorithm.sort with SwapStrategy.unstable is considerably
slower than his, whereas builtin sort is abysmal.
I find that generally using SwapStrategy.stable performs
Brad Anderson:
He and Dicebot documented the issues he came up against pretty
thoroughly here:
http://wiki.dlang.org/AA_Implementation_Issues
This looks like a bad idea, int[] != ubyte[]:
string[int[]] intAA;
ubyte[] key = [1,2,3];
intAA[key] = abc; // implicit convert ubyte[] - int[]
On Saturday, 21 June 2014 at 01:07:20 UTC, safety0ff wrote:
std.algorithm.sort with SwapStrategy.unstable is considerably
slower than his, whereas builtin sort is abysmal.
I find that generally using SwapStrategy.stable performs better.
This isn't universal though as there are cases where it
On Saturday, 21 June 2014 at 01:30:58 UTC, bearophile wrote:
The attention span of Reddit is excessively small, so
corrections often seem ignored, but if you have tested the D
code, then I suggest you to also compare the timings of the C++
version(s) on the same computer and post the two (or
On Saturday, 21 June 2014 at 01:54:45 UTC, safety0ff wrote:
See also:
https://github.com/logicchains/MagicForest/pull/2#issuecomment-46741029
Both using stable sorts : D version runs in 3s and C++ version
in 3.2s under similar conditions.
For input of 500 500 500
On Saturday, 21 June 2014 at 01:48:20 UTC, Peter Alexander wrote:
On Saturday, 21 June 2014 at 01:07:20 UTC, safety0ff wrote:
std.algorithm.sort with SwapStrategy.unstable is considerably
slower than his, whereas builtin sort is abysmal.
I find that generally using SwapStrategy.stable
Blog author here, I've added a note that D's sort matches the
speed of C++'s when the stable sort is used instead of the
default unstable. I don't think there's anything wrong with D's
unstable sort however, as the C++ version also performs worse
when using std::sort (unstable) instead of
On Saturday, 21 June 2014 at 03:52:54 UTC, logicchains wrote:
Blog author here, I've added a note that D's sort matches the
speed of C++'s when the stable sort is used instead of the
default unstable. I don't think there's anything wrong with D's
unstable sort however, as the C++ version also
71 matches
Mail list logo
