D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 10392 - Implement std.algortihm.find with sub-range in O(N) time
Summary: Implement std.algortihm.find with sub-range in O(N) time
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P2 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-06-17 10:10 UTC by Dmitry Olshansky
Modified: 2020-03-21 03:56 UTC (History)
0 users

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this issue.
Description Dmitry Olshansky 2013-06-17 10:10:51 UTC 
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