www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5514] New: Erroneous documentation and lacking randomization for topN

reply d-bugmail puremagic.com writes:
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 puremagic.com
        ReportedBy: magnus hetland.org


--- Comment #0 from Magnus Lie Hetland <magnus 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: -------
Feb 01 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5514


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: -------
Feb 01 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5514



--- Comment #1 from github-bugzilla puremagic.com 2013-02-24 16:49:26 PST ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/7291d2e47d4a7fb17565a7d7cd04ba8f893c1a27
issue 5514

https://github.com/D-Programming-Language/phobos/commit/299cf68ecc6ee7e81c1e6a45f747c80b46fa0184
Merge pull request #1167 from andralex/5514

Fix Issue 5514 - Erroneous documentation and lacking randomization for topN

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5514


Alex Rønne Petersen <alex lycus.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
                 CC|                            |alex lycus.org
         Resolution|                            |FIXED


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 24 2013