digitalmars.D.bugs - [Issue 10392] New: Implement std.algortihm.find with sub-range in O(N) time
- d-bugmail puremagic.com (27/27) Jun 17 2013 http://d.puremagic.com/issues/show_bug.cgi?id=10392
http://d.puremagic.com/issues/show_bug.cgi?id=10392 Summary: Implement std.algortihm.find with sub-range in O(N) time Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: dmitry.olsh gmail.com 10:10:51 PDT --- Per Adnrei's request I'm filing this in case somebody has the time to do it. It have long bugged me that Phobos std.algorithm.find is slow. Far slower then strstr (esp on *nix where it competes against GLIBC[1]). The current state of the art in searching substring with O(1) space requirement is Two-Way algorithm: http://www-igm.univ-mlv.fr/~lecroq/string/node26.html which is linear in time. I could imagine it would be interesting to implement a generic version as well. [1] See a relevant bug report and discussion e.g on glibc http://sourceware.org/bugzilla/show_bug.cgi?id=5514 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 17 2013