Video Introduction to the STL, Parts 6 and 7

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