Algorithms

cat~algorithms

This category covers Rust implementations of core algorithms, such as sorting and random value generation, that are not covered in separate chapters.

Compression, cryptography, data structures, mathematics, scientific algorithms, search, strings, and text processing are discussed elsewhere but are briefly mentioned below.

Random Value Generation

RecipeCratesCategories
Generate Random Numbersrandcat~algorithms
Generate Random Numbers Within a Rangerandcat~algorithms
Generate Random Numbers Within a Given Distributionrand rand_distrcat~algorithms
Generate Random Values of a Custom Typerandcat~algorithms
Create Random Passwords from a Set of Alphanumeric Charactersrandcat~algorithms cat~os
Create Random Passwords from a Set of User-defined Charactersrandcat~algorithms cat~os
Generate Random Numbers with fastrandfastrandcat~algorithms

Sorting

RecipeCratesCategories
Sort a Vector of Integersstdcat~algorithms
Sort a Vector of Floatsstdcat~algorithms
Sort a Vector of Structsstdcat~algorithms

Hashing

RecipeCratesCategories
Calculate the SHA-256 Digest of a Filering data-encodingcat~algorithms
Hash with sha2sha2cat~algorithms
Hash with sha1sha1cat~algorithms
Hash with md-5md-5cat~algorithms
Hash with blake3blake3cat~algorithms
Cryptograhic Algorithmscat~algorithms
foldhashcat~algorithms
Legacy Hashing Algorithmscat~algorithms
Use General-purpose Hashing Algorithmscat~algorithms

Compression Algorithms

For compression, use:

  • flate2 for deflate, gzip, and zlib compression,
  • zip for zip files,
  • tar for tar archives,
  • zstd for Zstandard compression,
  • bzip2,
  • xz2,
  • snap for Snappy compression.
  • brotli for Brotli compression.

Data Structures

For common data structures (Vec↗, HashMap↗, etc.), you will use std::collections↗. You may also consider:

  • im↗ for immutable data structures,
  • indexmap for maps that keep track of insertion order,
  • arrayvec, smallvec and tinyvec for stack-allocated arrays,
  • petgraph↗ for graphs,
  • dashmap and papaya for concurrent data structures,
  • parking_lot for mutexes,
  • crossbeam-channel, flume, tokio, and postage for channels.

Worth a mention: fst provides fast, memory-efficient, immutable set and map data structures for storing and searching (very) large collections of strings and associated values. It is based on finite state transducers (FSTs). The capabilities of ordered sets and maps mirror that of BTreeSet and BTreeMap found in the standard library. The key difference is that sets and maps in fst are immutable, keys are byte sequences, and values, in the case of maps, are always unsigned 64 bit integers.

See vector hash maps, other maps, Binary Heap within the Data Structures section for more details.

Recursive Algorithms

  • stacker is a stack growth library useful when implementing deeply recursive algorithms that may accidentally blow the stack.

Search Algorithms

For small-scale tasks, like filtering a list of items in memory, reach first for the standard library:

  • slice::binary_search* for slices and vectors,

  • std::iter::Iterator::find for iterators,

  • str::find, str::rfind for strings.

  • argminmax provides efficient argmin & argmax (in 1 function) with SIMD for floats and integers.

  • bytecount count occurrences of a given byte, or the number of UTF-8 code points, in a byte slice, fast.

meilisearch↗ and tantivy↗ are full-text search engines written in Rust, similar to what you'd expect from Elasticsearch or Algolia.

String Algorithms and Text Processing

For Strings, use:

  • regex↗ for regular expressions,
  • fancy-regex if you need features, such as backtracking, which regex doesn't support,
  • aho-corasick↗ for finding occurrences of many patterns at once,
  • strsim↗ for string similarity.

See also String Concat, String Encoding, String Parsing, and Text Processing.

Numerical and Mathematical Algorithms

For Mathematics, use the following crates for general numerical tasks:

  • Abstracting over different number types:
    • num-traits,
    • num↗.
  • Additional Numeric Types:
    • num-bigint and rug for big integers.
    • rust_decimal for big decimals.
    • ordered-float for sortable floats.
  • Complex Numbers.
  • Linear Algebra:
  • Data frames:
    • polars.
    • datafusion.
  • Statistics,
  • Trigonometry.
  • Others
    • rustfft for Fast Fourier Transforms.
    • roots for numerical root finding.

References