clean up rust bread and butter. h/t lopopolo

• run using cargo
• safe conversion to usize
• do not repeat the generate calls
• derive Default and Clone traits on Graph
• control debug printing via Cargo features
• run cargo fmt with check flag in CI
• run cargo clippy to fail on warnings in CI

track j_0 and k_0 cursors to the first vertices we need to consider for the directed and undirected edges.

now well under arbitrary goal of 1s for N=16 or 12.2M edges! done with all of the initial performance TODOs i had.

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	587.00ns
F(4)	4	5	0	1.55µs
F(6)	6	35	0	6.34µs
F(8)	8	319	0	37.51µs
F(10)	10	3559	0	314.48µs
F(12)	12	46841	3	3.91ms
F(14)	14	709601	52	52.95ms
F(16)	16	12156445	899	899.53ms

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	729.00ns
F(4)	4	5	0	2.33µs
F(6)	6	35	0	10.47µs
F(8)	8	319	0	63.37µs
F(10)	10	3559	0	509.20µs
F(12)	12	46841	6	6.69ms
F(14)	14	709601	69	69.19ms

F(16)	16	12156445	1176	1.18s

haha 🙃. obvious find upon first look at any Rust-specific performance tips. well, i hit my goal performance. prior work was still a good exercise in algorithmic and data access performance. need to take a closer look for other low hanging fruit.

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	570.00ns
F(4)	4	5	0	1.52µs
F(6)	6	35	0	6.46µs
F(8)	8	319	0	40.98µs
F(10)	10	3559	0	350.72µs
F(12)	12	46841	4	4.68ms
F(14)	14	709601	84	84.26ms


F(16)	16	12156445	1295	1.30s
F(18)	18	232349755	25600	25.60s

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	8.03µs
F(4)	4	5	0	13.64µs
F(6)	6	35	0	88.39µs
F(8)	8	319	0	757.44µs
F(10)	10	3559	7	7.83ms
F(12)	12	46841	76	76.42ms
F(14)	14	709601	1199	1.20s


F(16)	16	12156445	22036	22.04s

get better data locality. hit my arbitrary goal of >500K permutations per second! decently satisfied with that. lets timebox some attempts to get to 1M per second

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	4.98µs
F(4)	4	5	0	8.63µs
F(6)	6	35	0	53.44µs
F(8)	8	319	0	656.73µs
F(10)	10	3559	6	6.37ms
F(12)	12	46841	79	79.95ms
F(14)	14	709601	1281	1.28s


F(16)	16	12156445	23447	23.45s

no need to track prior state to restore during backtrack

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	15.69µs
F(4)	4	5	0	28.91µs
F(6)	6	35	0	153.20µs
F(8)	8	319	1	1.07ms
F(10)	10	3559	13	13.59ms
F(12)	12	46841	155	155.33ms
F(14)	14	709601	1929	1.93s


F(16)	16	12156445	34252	34.25s

undirected edges can only connect to unseen but connected vertices or single new unconnected vertex

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	14.20µs
F(4)	4	5	0	25.81µs
F(6)	6	35	0	139.61µs
F(8)	8	319	1	1.73ms
F(10)	10	3559	12	12.81ms
F(12)	12	46841	163	163.48ms
F(14)	14	709601	2220	2.22s


F(16)	16	12156445	38673	38.67s

we already only generate valid graphs! i initially expected work to be required to ensure that edges were wired up correctly due to the possibility of sink vertices being anywhere in the set.

case	n	result	dur_ms	dur_pretty
F(2)	2	1	0	11.31µs
F(4)	4	5	0	21.89µs
F(6)	6	35	0	137.53µs
F(8)	8	319	1	1.46ms
F(10)	10	3559	19	19.22ms
F(12)	12	46841	285	285.95ms
F(14)	14	709601	4737	4.74s

just documenting

// currently testing the solutions given in the example problem
let gs: Vec<Graph> = vec![
    // where N = 0
    Graph {
        vertices: vec![[Some(1), None, None], [None, Some(0), None]],
    },
    // where N = 2
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(2)],
            [Some(3), Some(1), Some(1)],
            [None, Some(2), None],
        ],
    },
    // where N = 4
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(2)],
            [Some(3), Some(1), Some(1)],
            [Some(4), Some(2), Some(4)],
            [Some(5), Some(3), Some(3)],
            [None, Some(4), None],
        ],
    },
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(3)],
            [Some(3), Some(1), Some(4)],
            [Some(4), Some(2), Some(1)],
            [Some(5), Some(3), Some(2)],
            [None, Some(4), None],
        ],
    },
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(4)],
            [Some(3), Some(1), Some(3)],
            [Some(4), Some(2), Some(2)],
            [Some(5), Some(3), Some(1)],
            [None, Some(4), None],
        ],
    },
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(3)],
            [None, Some(1), None],
            [Some(4), Some(5), Some(1)],
            [Some(5), Some(3), Some(5)],
            [Some(3), Some(4), Some(4)],
        ],
    },
    Graph {
        vertices: vec![
            [Some(1), None, None],
            [Some(2), Some(0), Some(4)],
            [Some(3), Some(1), Some(5)],
            [None, Some(2), None],
            [Some(5), Some(5), Some(1)],
            [Some(4), Some(4), Some(2)],
        ],
    },
];

for g in gs {
    let n = g.vertices.len() - 2;
    println!(
        "g(n={}) is_valid: {}, is_solution: {:?}!\t{:?}",
        n,
        g.is_valid(),
        g.is_solution(n as u16),
        g.vertices
    );
}

initial timings on 9/1:

case	n	result	dur_ms	dur_pretty
F(0)	0	0	0	11.16µs
F(2)	2	1	0	42.01µs
F(4)	4	5	0	108.55µs
F(6)	6	35	1	1.10ms
F(8)	8	319	12	12.55ms
F(10)	10	3559	161	161.66ms
F(12)	12	46841	2258	2.26s
F(14)	14	709601	40126	40.13s

Improvements made in PRs for N=16. Normalized for debug v. release builds. Measured using release build.

Run                                  ms       % faster    graphs/sec
--------------------------------------------------------------------
Initial run                          34112                356K/sec
Remove is_solution check (#3)        3449     889%        3.5M/sec
Check fewer undirected edges (#4)    1310     163%        9.3M/sec
Assign cell by cell (#5)             1294     1%          9.4M/sec
Tightly pack array (#7)              1310     -1%         9.3M/sec
j_0 and k_0 cursors (#12)            930      41%         13.1M/sec

Using a tightly packed multidimensional array instead of a vector of arrays was a meaningful performance improvement in debug mode but does not matter in release mode. Perhaps Rust compiler is already optimizing!

. . .