• d-bugmail puremagic.com (27/27) Jun 17 2013 http://d.puremagic.com/issues/show_bug.cgi?id=10392

d-bugmail puremagic.com writes:

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: -------