haskell / haskell/bytestring

Search algorithms

Open
#307 7 comments 1 reaction 0 assignees View on GitHub
discussion/rfc
Dominant language
Haskell
Stars
301
Forks
144
Avg merge
7d 22h
Merged PRs (30d)
1

Description

I've been thinking about `splitOn` and `replace` for `ByteString`. They can be expressed in terms of [`breakSubstring`](http://hackage.haskell.org/package/bytestring-0.11.0.0/docs/Data-ByteString.html#v:breakSubstring), but the more I look at the latter the more doubts I get about its implementation.

https://github.com/haskell/bytestring/blob/bd5412c1b7fac3f63cc1d2ea4e75bdf45c04b541/Data/ByteString.hs#L1596-L1613

What's the reason for Karp-Rabin here? It is great to search for multiple patterns at once, but this is not our case. I suspect that for non-pathological cases even a naive loop with `memcmp` could very well be faster. And for pathological inputs Karp-Rabin is _O(mn)_ anyways. If we want to fix the worst case scenario, we should employ Knuth-Moris-Pratt or Boyer-Moore.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.