Binary Search Single Sorted String: Perform binary search on a single, delimited string slice of sorted but unevenly sized substrings.
View the docs for more information.
There are generally two ways to setup this crate: at compile-time, or at runtime. The
main (only...) method of interest is [SortedString::binary_search()]. View its
documentation for detailed context.
```rust use b4s::{AsciiChar, SortedString};
fn main() { match SortedString::newchecked("abc,def,ghi,jkl,mno,pqr,stu,vwx,yz", AsciiChar::Comma) { Ok(ss) => { match ss.binarysearch("ghi") { Ok(r) => println!("Found at range: {:?}", r), Err(r) => println!("Not found, last looked at range: {:?}", r), } } Err(e) => println!("Error: {:?}", e), } } ```
For convenience, there's also a const fn, usable statically. As a tradeoff, it's
potentially unsound.
```rust use b4s::{AsciiChar, SortedString};
static SS: SortedString = SortedString::new_unchecked("abc,def,ghi,jkl,mno,pqr,stu,vwx,yz", AsciiChar::Comma);
fn main() { match SS.binary_search("ghi") { Ok(r) => println!("Found at range: {:?}", r), Err(r) => println!("Not found, last looked at range: {:?}", r), } } ```
The source for the input string can be anything, for example a file prepared at compile time:
rust,ignore
static SS: SortedString =
SortedString::new_unchecked(include_str!("path/to/file"), AsciiChar::LineFeed);
This is convenient if a delimited (\n, ...) file is already at hand. It only needs to
be sorted once previously, and is then available for string containment checks at good,
albeit not perfect, runtime performance, at essentially no startup cost.
The itch to be scratched is the following:
build.rs)A couple possible approaches come to mind. The summary table, where n is the number of
words, is (for more context, see the individual sections below):
| Approach | Pre-compile preprocessing[^1] | Compile time | Runtime lookup | Binary size |
| ------------------------------------------------------------------------------------------------------------------------ | ----------------------------- | ------------------ | -------------------------------------------------------------------------------------------------- | ----------- |
| b4s | Sort, O(n log n) | Single ref: O(1) | Bin. search: O(log n) | O(n) |
| array | Sort, O(n log n) | Many refs: O(n) | Bin. search: O(log n) | ~ O(3n) |
| phf/HashSet | None | Many refs: O(n) | Hash: O(1) | ~ O(3n) |
| padded &str | Sort + Pad, ~ O(n log n) | Single ref: O(1) | Bin. search: O(log n) | ~ O(n) |
This crate is an attempt to provide a solution with:
HashSet at
runtime)[^2],It was found that approaches using slices and hash sets (via phf) absolutely tanked
developer experience, with compile times north of 20 minutes (!) for 30 MB word lists
(even on fast hardware), large binaries, and
clippy imploding, taking the IDE with it.
This crate was born as a solution. Its main downside is suboptimal runtime
performance. If that is your primary goal, opt for phf or similar crates. This crate
is not suitable for long-running applications, where initial e.g. HashSet creation is
a fraction of overall runtime costs.
The following alternatives might be considered, but were found unsuitable for one reason or another.
A simple slice is an obvious choice, and can be generated in a build script.
```rust static WORDS: &[&str] = &["abc", "def", "ghi", "jkl"];
fn main() { match WORDS.binary_search(&"ghi") { Ok(i) => println!("Found at index: {:?}", i), Err(i) => println!("Not found, could be inserted at: {:?}", i), } } ```
There are two large pains in this approach:
binary size becomes large.
The words are much shorter than the &str they are contained in. On 64-bit
hardware, a &str is 16
bytes, with a
usize address pointer and a usize
length. For large word
lists, this leads to incredible bloat for the resulting binary.
Regular HashSets are
not available at compile time. Crates like phf
change that:
```rust use phf::{phf_set, Set};
static WORDS: Set<&'static str> = phf_set! { "abc", "def", "ghi", "jkl" };
fn main() { if WORDS.contains(&"ghi") { println!("Found!"); } else { println!("Not found!"); } } ```
Similar downsides as for the slices case apply: very long compile times, and considerable binary bloat from smart pointers. A hash set ultimately is a slice with computed indices, so this is expected.
Another approach could be to use a single string (saving pointer bloat), but pad all words to the longest occurring length, facilitating easy binary search (and increasing bloat to some extent):
```rust static WORDS: &str = "abc␣␣def␣␣ghi␣␣jklmn";
// Perform binary search... ```
The binary search implementation is then straightforward, as the elements are of known, fixed lengths (in this case, 5). This approach was found to not perform well.
In certain scenarios, one might reach for more sophisticated approaches, such as tries. This is not a case this crate is designed for. Such a structure would have to be either:
built at runtime, for example as
```rust use trie_rs::TrieBuilder;
let mut builder = TrieBuilder::new(); builder.push("abc"); builder.push("def"); builder.push("ghi"); builder.push("jkl"); let trie = builder.build(); // Takes time
assert!(trie.exact_match("def")); ```
or alternatively
While tools like bincode are fantastic, the latter approach is still numbingly slow at application startup, compared to the (much more ham-fisted) approach the crate at hand takes.
This is only included here and in the benchmarks as a sanity check and baseline. Linear search like
rust
static WORDS: &[&str] = &["abc", "def", "ghi", "jkl"];
assert!(WORDS.contains(&"ghi"));
is $O(n)$, and slower by a couple orders of magnitude for large lists. If your current implementation relies on linear search, this create might offer an almost drop-in replacement with a significant performance improvement.
The below benchmarks show a performance comparison. The benchmarks run a search for representative words (start, middle, end, shortest and longest words found in the pre-sorted input list), on various different input word list lengths.
Sets are unsurprisingly fastest, but naive binary search (the built-in one) seems
incredibly optimized and just as fast. b4s is slower by a factor of 5 to 10. The
"padded string" variant is slowest. One can observe how, as the input lists get longer
("within X entries"), b4s becomes slower.
In the context of this crate's purpose, the slowness might not be an issue: if application startup is measured in milliseconds, and lookups in nanoseconds (!), one can perform in the rough ballpark of, say, 100,000 lookups before the tradeoff of this crate (fast startup) becomes a problem (this crate would be terrible for a web server).
The benchmark plot including linear search is largely illegible, as the linear horizontal axis scaling dwarfs all other search methods. It is therefore linked separately, but paints a clear picture.
The benchmarks were run on a machine with the following specs:
The benchmarks are not terribly scientific (low sample sizes etc.), but serve as a rough
guideline and sanity check. Run them yourself from the repository root with cargo
install just && just bench.
time*, unless the word list itself changes. This column might therefore be moot, and considered essentially zero-cost. This viewpoint benefits this crate. for](https://github.com/alexpovel/betterletters) is sensitive to startup-time, as the program's main processing is *rapid. Even just 50ms of startup time would be very noticeable, slowing down a program run by a factor of about 10.
