digitalmars.D.bugs - [Issue 4584] New: std.algorithm.sort fails with SwapStrategy.stable
- d-bugmail puremagic.com (24/24) Aug 05 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (10/10) Jan 09 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (22/22) Oct 23 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (11/11) Oct 23 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (12/12) Aug 22 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (14/17) Aug 22 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (9/20) Aug 22 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (19/19) Sep 03 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (9/21) Sep 03 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (14/14) Oct 27 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
- d-bugmail puremagic.com (11/11) Dec 13 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4584
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Summary: std.algorithm.sort fails with SwapStrategy.stable
Product: D
Version: D2
Platform: Other
OS/Version: All
Status: NEW
Severity: normal
Priority: P2
Component: Phobos
AssignedTo: nobody puremagic.com
ReportedBy: johannespfau gmail.com
PDT ---
Created an attachment (id=704)
test case
When using SwapStrategy.stable with std.algorithms sort function, I get
partially wrong results. It works fine with SwapStrategy.unstable. It also
asserts: "core.exception.AssertError std.algorithm(4021): Assertion failure"
(the assert is "assert(isSorted!(lessFun)(r));")
Tested with dmd 2.047 and phobos 2.047.
A test case is attached.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 05 2010
d-bugmail puremagic.com
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Andrei Alexandrescu <andrei metalanguage.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |ASSIGNED
CC| |andrei metalanguage.com
AssignedTo|nobody puremagic.com |andrei metalanguage.com
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 09 2011
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Olivier Fabre <axel.foster-5bcwppg yopmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |axel.foster-5bcwppg yopmail
| |.com
17:34:22 PDT ---
I don't know if it helps, but I've got a similar failure with this program:
import std.algorithm;
void main() {
sort!("a<b", SwapStrategy.stable)(
[83, 42, 85, 86, 87, 22, 89, 30, 91, 46, 93, 94, 95, 6,
97, 14, 33, 10, 101, 102, 103, 26, 105, 106, 107, 6]
);
}
It returns:
core.exception.AssertError /usr/include/d/std/algorithm.d(6662): Failed to sort
range of type int[]. Actual result is: [6, 42, 85, 86, 87, 22, 89, 30]...
(With the git version of dmd2 and libphobos2 from 21 oct. 2011.)
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 23 2011
http://d.puremagic.com/issues/show_bug.cgi?id=4584 18:52:08 PDT --- Oh well, Johannes' test case actually works fine here, so my bug might be a different one. Unless the value of optimisticInsertionSortGetsBetter in sortImpl() was < 13 at the time... By experimenting with arrays of growing length filled with random numbers, it becomes clear that my bug happens for arrays of length 26 and never for a smaller length, which hints at a bug in the "pivot" (quick?) sort. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Oct 23 2011
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Dmitry Olshansky <dmitry.olsh gmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dmitry.olsh gmail.com
06:31:15 PDT ---
Hit this issue in my project. As part of normalization process codepoints are
_stably_ sorted by their canonical combining class.
Can dig up a bunch of cases if required but the end result is it rarely works.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584
bearophile_hugs eml.cc changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |bearophile_hugs eml.cc
Hit this issue in my project. As part of normalization process codepoints are
_stably_ sorted by their canonical combining class.
Can dig up a bunch of cases if required but the end result is it rarely works.
I have seen this:
https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e
So is this problem caused by a DMD bug? If this is true are you able to create
a minimal example of the bug?
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584 22:36:30 PDT ---No, it's just that $ works only with arrays (still). And in order for sort(zip(...)) to work I need this minor fix. The bug with stable sort was there for 2 years now and I don't realy know the cause. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------Hit this issue in my project. As part of normalization process codepoints are _stably_ sorted by their canonical combining class. Can dig up a bunch of cases if required but the end result is it rarely works.I have seen this: https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e So is this problem caused by a DMD bug? If this is true are you able to create a minimal example of the bug?
Aug 22 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Xinok <xinok live.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |xinok live.com
I've written a collection of sorting algorithms for D:
https://github.com/Xinok/XSort
I recommend using timsort.d or stablesort.d. mergesort.d is a generic
implementation. stablequicksort.d is not recommended.
I've extensively tested each of these modules and can confirm they're stable.
More so, they're many times faster than the stable sort in Phobos. Lastly,
there are no issues regarding the dollar token $ (range.length is used as
necessary).
I provide all of these modules to the public domain. That means anybody is free
to implement any of these modules into Phobos.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Sep 03 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584 14:14:23 PDT ---I've written a collection of sorting algorithms for D: https://github.com/Xinok/XSort I recommend using timsort.d or stablesort.d. mergesort.d is a generic implementation. stablequicksort.d is not recommended. I've extensively tested each of these modules and can confirm they're stable. More so, they're many times faster than the stable sort in Phobos. Lastly, there are no issues regarding the dollar token $ (range.length is used as necessary).Yeah, I recall you had some great stuff on this. Thanks for showing up.I provide all of these modules to the public domain. That means anybody is free to implement any of these modules into Phobos.Great, I'll look into making a pull request to do just that. With a proper attribution, of course. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Sep 03 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584
yebblies <yebblies gmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |pull
CC| |yebblies gmail.com
Platform|Other |All
AssignedTo|andrei metalanguage.com |dmitry.olsh gmail.com
Dmitry's pull:
https://github.com/D-Programming-Language/phobos/pull/787
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 27 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4584
Dmitry Olshansky <dmitry.olsh gmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
12:32:45 PST ---
Strangely it didn't pick up commits.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 13 2012