http://d.puremagic.com/issues/show_bug.cgi?id=5514
Summary: Erroneous documentation and lacking randomization for
topN
Product: D
Version: unspecified
Platform: Other
OS/Version: Mac OS X
Status: NEW
Severity: normal
Priority: P2
Component: Phobos
AssignedTo: nob...@puremagic.com
ReportedBy: mag...@hetland.org
--- Comment #0 from Magnus Lie Hetland <mag...@hetland.org> 2011-02-01 07:57:21
PST ---
The topN function in std.algorithm is documented as having a running time of
Ο(r.length), if stable. This should be an *expected* (or average-case) running
time of O(r.length), with a worst-case running time of O(r.length^^2), based on
the current implementation, which is the Randomized-Select algorithm.
Also, the implementation should probably use randomization (as in the standard
formulation of the algorithm), rather than consistently picking the middle
element. This will entail a slight overhead in picking the pivot, but this will
(on average) only be done a logarithmic number of times, so the cost should be
negligible. The gain from this is, of course, that consistent worst-case
behavior in the face of certain inputs is avoided.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
