Video Introduction to the STL, Parts 6 and 7

Visual C++

October 25th, 2010

Part 6 and Part 7 of my video lecture series introducing the Standard Template Library are now available; they cover algorithms and functors.

Previous parts:

Part 1 (sequence containers)

Part 2 (associative containers)

Part 3 (smart pointers)

Part 4 (Nurikabe solver introduction)

Part 5 (Nurikabe solver conclusion)

My Nurikabe solver, available here, demonstrates how I use the STL components that I’ve talked about. I’ve continued to optimize it; there’s more work to do, but I’ve already obtained dramatic speedups:

Puzzle Time (v1.1) Time (v1.7) Speedup wikipedia_hard 87.1 ms 5.9 ms 14.8x wikipedia_easy 36.1 ms 3.2 ms 11.4x nikoli_1 18.5 ms 1.6 ms 11.9x nikoli_2 13.2 ms 1.9 ms 7.1x nikoli_3 16.8 ms 2.2 ms 7.8x nikoli_4 108.1 ms 5.9 ms 18.3x nikoli_5 89.7 ms 7.3 ms 12.3x nikoli_6 87.5 ms 5.7 ms 15.3x nikoli_7 2123.97 seconds 496.0 ms 4282.3x nikoli_8 2784.7 ms 316.7 ms 8.8x nikoli_9 13518.2 seconds 32.8 seconds 412.4x nikoli_10 11811.8 seconds 8.5 seconds 1397.5x

Here’s the changelog:

1.0 (8/24/2010) – First version, appearing in Channel 9’s Video Introduction to the STL, Part 4.

1.1 (9/1/2010) – Added 1 more puzzle from Wikipedia and 10 puzzles from Nikoli. Improved time formatting with microseconds/milliseconds/seconds. The time taken by initial construction and each step of analysis is now recorded.

1.2 (9/1/2010) – Massively accelerated hypothetical contradiction analysis by guessing cells in a deterministic but pseudorandomized order.

1.3 (9/8/2010) – Reorganized Grid::solve() into smaller member functions. Thanks, Corrector2!

1.4 (9/24/2010) – Accelerated hypothetical contradiction analysis further by prioritizing guesses near white cells. Thanks, Michael B.!

1.5 (10/19/2010) – Increased performance by making Grid::confined() use vector<vector<Flag>> instead of set<pair<int, int>>. Further increased performance by postponing Grid::detect_contradictions() until just before Grid::analyze_confinement().

1.6 (10/20/2010) – Removed Grid::analyze_isolated_unknown_regions(), which was successful exactly once (on wikipedia_hard), during both top-level analysis and hypothetical contradiction analysis. Removed Grid::operator=()’s definition and entirely removed Grid::swap(), as they were unused. Avoided copying m_output in Grid’s private copy ctor, as it isn’t needed during hypothetical contradiction analysis. Even if, in the future, the solver is extended to capture the outp