[Issue 5514] New: Erroneous documentation and lacking randomization for topN

[d-bugmail at puremagic.com]

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: nobody at puremagic.com
        ReportedBy: magnus at hetland.org


--- Comment #0 from Magnus Lie Hetland <magnus at 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: -------