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:
| Approach | Pre-compile preprocessing | 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 | 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) |
For more context, see the individual sections below.
Note that the pre-compile preprocessing is ordinarily performed only a single time, unless the word list itself changes. This column might therefore be moot, and considered essentially zero-cost.
Therefore, this crate is an attempt to provide a solution with:
essentially no additional startup cost (unlike, say, constructing a HashSet at
runtime).
The program this crate was initially designed for 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.
It was found that the approaches using arrays and hash sets (via phf) absolutely
tanked developer experience, with compile times north of 20 minutes (!) for 30 MB word
lists, 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.
A simple array 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 array case apply: very long compile times, and considerable binary bloat from smart pointers. A hash set ultimately is an array 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. A trie would have to be either:
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.
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 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.