search

Quuxplusone / LLVMBugzillaTest

0 stars 0 forks source link

Optimizing std::search function #34586

Open Quuxplusone opened 6 years ago

Quuxplusone commented 6 years ago
Bugzilla Link PR35613
Status NEW
Importance P enhancement
Reported by Alexander Zaitsev (zamazan4ik@tut.by)
Reported on 2017-12-10 13:22:01 -0800
Last modified on 2017-12-10 13:47:28 -0800
Version unspecified
Hardware PC All
CC hfinkel@anl.gov, llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

std::search can be optmized for Random Access Iterators by implementing inside search algorithm like Boyer-Moore or Boyer-Moore-Horspool or Musser-Nishanov algorithm (or smth faster). For Bidirectional iterators AFAIK Crochemore-Perrin algorithm is very good.

AFAIK, now std::search use only naive search algortihm. Can be it improved?

P.S. I know about changes in C++17 new search algorithms, but i suggest use the most efficient version for every type of iterators.

P.S.S Efficient algorithms you can find in Seqan library and in Boost.Algorithm.

Quuxplusone commented 6 years ago

I know the only one reason: Boyer-Moore and Boyer-Moore-Horspool are a little bit complex and have state. Constructing these search engines isn't so cheap. But they work much faster than naive search.