naive_opt

The optimized naive string-search algorithm.

Features

The naive string-searching algorithm
Enhanced with 1-byte search like the libc++ and the libstd++ string::find
Specializing in UTF-8 strings, which is a feature of rust
Support the zero overhead trait.
minimum support: rustc 1.41.1 (f3e1a954d 2020-02-24)

Compatibility

This crate is implemented to replace the rust std library. However, the method names are different, so please rewrite your code. It shouldn't be too difficult.

compatibility:

| rust std::str | this crate | |:-----------------------------|:---------------------------------------| | std::str::find() | naive_opt::Search::search() | | std::str::rfind() | naive_opt::Search::rsearch() | | std::str::contains() | naive_opt::Search::includes() | | std::str::match_indices() | naive_opt::Search::search_indices() | | std::str::rmatch_indices() | naive_opt::Search::rsearch_indices() |

Examples

Example function:

```rust use naiveopt::{stringsearch, stringrsearch}; use naiveopt::{stringsearchindices, stringrsearchindices};

let haystack = "111 a 111b"; let needle = "a"; let r = stringsearch(haystack, needle); asserteq!(r, Some(4));

asserteq!(stringsearch(haystack, "1"), Some(0)); asserteq!(stringrsearch(haystack, "1"), Some(8));

let v: Vec<_> = stringsearchindices("abc345abc901abc", "abc").collect(); asserteq!(v, [(0, "abc"), (6, "abc"), (12, "abc")]); let v: Vec<_> = stringrsearchindices("abc345abc901abc", "abc").collect(); asserteq!(v, [(12, "abc"), (6, "abc"), (0, "abc")]); ```

Example trait: Search

```rust use naive_opt::Search;

let haystack = "111 a 111b"; let needle = "a"; let r = haystack.search(needle); assert_eq!(r, Some(4));

asserteq!(haystack.search("1"), Some(0)); asserteq!(haystack.rsearch("1"), Some(8));

let v: Vec<_> = "abc345abc901abc".searchindices("abc").collect(); asserteq!(v, [(0, "abc"), (6, "abc"), (12, "abc")]); let v: Vec<_> = "abc345abc901abc".rsearchindices("abc").collect(); asserteq!(v, [(12, "abc"), (6, "abc"), (0, "abc")]); ```

Example trait: SearchIn

```rust use naive_opt::SearchIn;

let haystack = "111 a 111b"; let needle = "a"; let r = needle.searchin(haystack); asserteq!(r, Some(4));

asserteq!("1".searchin(haystack), Some(0)); asserteq!("1".rsearchin(haystack), Some(8)); ```

Benchmark

compile by rustc 1.52.0 (88f19c6da 2021-05-03)

| name | bench:en | bench:ja | musl:en | musl:ja | |:------------------------|------------:|------------:|------------:|------------:| | stdstrstr | 228.500 uc | 177.770 uc | 232.990 uc | 176.730 uc | | stdstringstring | 223.760 uc | 178.780 uc | 228.410 uc | 175.880 uc | | funcstrstr | 29.561 uc | 29.222 uc | 30.636 uc | 30.412 uc | | funcstringstring | 29.315 uc | 29.102 uc | 30.422 uc | 30.371 uc | | traitstrstr | 25.365 uc | 25.036 uc | 26.210 uc | 26.271 uc | | traitstringstring | 25.131 uc | 24.814 uc | 26.350 uc | 26.443 uc | | stdindices | 173.250 uc | 126.650 uc | 169.970 uc | 131.070 uc | | funcindices | 26.060 uc | 26.094 uc | 27.181 uc | 27.331 uc | | trait_indices | 26.083 uc | 26.097 uc | 27.223 uc | 27.366 uc |

compile by rustc 1.41.1 (f3e1a954d 2020-02-24)

| name | bench:en | bench:ja | musl:en | musl:ja | |:------------------------|------------:|------------:|------------:|------------:| | stdstrstr | 207.280 uc | 172.180 uc | 208.830 uc | 164.940 uc | | stdstringstring | 207.220 uc | 174.360 uc | 205.340 uc | 167.410 uc | | funcstrstr | 28.212 uc | 28.243 uc | 29.534 uc | 29.582 uc | | funcstringstring | 28.173 uc | 28.329 uc | 29.939 uc | 29.576 uc | | traitstrstr | 24.888 uc | 24.896 uc | 26.374 uc | 26.272 uc | | traitstringstring | 25.642 uc | 25.736 uc | 29.353 uc | 27.134 uc | | stdindices | 170.070 uc | 133.240 uc | 168.450 uc | 124.060 uc | | funcindices | 26.352 uc | 26.372 uc | 27.931 uc | 27.951 uc | | trait_indices | 26.491 uc | 26.515 uc | 28.357 uc | 28.468 uc |

std is std::str::find()
us is micro seconds
:en is english haystack.
:ja is japanese haystack.
musl is x86_64-unknown-linux-musl
bench on intel Q6600 @ 2.40GHz

Changelogs

This crate's changelog here.