markov_rs

A simple and fast Markov chain generator in Rust.

By using the Walker's Alias Method, a weighted random sampling algorithm, the model can generate elements very quickly. The benchmark for this crate and the Markov chain using the Cumulative Sum Method is as follows.

Algorithm	Building model	Generation
Walker's Alias Method	117.15 ms	9.2078 ms
Cumulative Sum Method	8.3087 ms	168.02 ms

Building model
- The time to create a Markov chain model from a stored array of random values from 0 to 999 with a length of 10000.
Generation
- The time to generate 100,000 elements from the above model.
Environment
- OS: Windows 11 Home Insider Preview
- CPU: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
- RAM: 16.0 GB
- Rust version: rustc 1.56.1
- Source code: benchmark.rs

For details about the Walker's Alias Method, see ichi-h / weighted_rand.

Usage

Add this to your Cargo.toml:

[dependencies]
markov_rs = "0.1"

Example

use markov_rs::MarkovChain;

fn main() {
    let text = [
        "I", "think", "that", "that", "that", "that", "that", "boy", "wrote", "is", "wrong",
    ];
    let mut model = MarkovChain::from(&text);
    for _ in 0..20 {
        print!("{} ", model.next());
    }
}

Planned

Improve performance of model building.
Support for Nth-order Markov chain.

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution