[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

--- Comment #6 from github-bugzi...@puremagic.com ---
Commit pushed to stable at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/10da3381c1d8d92ba8f0ef96e157beb1ada83f49
Merge pull request #3921 from andralex/15553

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

Ivan Kazmenko  changed:

   What|Removed |Added

 CC||ga...@mail.ru

--- Comment #5 from Ivan Kazmenko  ---
(In reply to Andrei Alexandrescu from comment #3)
> BTW uniform() isn't the problem; replacing it with r.length / 2 keeps things
> slow.

Can uniform() call be returned, then?  Otherwise, topN can now show quadratic
performance on a pre-generated input:
https://issues.dlang.org/show_bug.cgi?id=15583

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

--- Comment #4 from github-bugzi...@puremagic.com ---
Commit pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/10da3381c1d8d92ba8f0ef96e157beb1ada83f49
Merge pull request #3921 from andralex/15553

Fix Issue 15553 - topN very inefficient [slower than sort, even for topN(0)]
but should be O(n)

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

--- Comment #1 from Timothee Cour  ---
haven't profiled, but:
could uniform be slow
https://github.com/D-Programming-Language/phobos/commit/7291d2e47d4a7fb17565a7d7cd04ba8f893c1a27

not sure if those could help: #5514 

Maybe this is most relevant: [std.algorithm: implement deterministic topN]
https://issues.dlang.org/show_bug.cgi?id=12141


At the very least, it shouldn't be slower than sort

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

Timothee Cour  changed:

   What|Removed |Added

 CC||ilyayaroshe...@gmail.com,
   ||timothee.co...@gmail.com
   Assignee|nob...@puremagic.com|and...@erdani.com
 OS|Mac OS X|All

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

--- Comment #2 from Andrei Alexandrescu  ---
https://github.com/D-Programming-Language/phobos/pull/3921

--

[Issue 15553] topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

--- Comment #3 from Andrei Alexandrescu  ---
BTW uniform() isn't the problem; replacing it with r.length / 2 keeps things
slow.

--