Video Introduction to the STL, Parts 6 and 7

Video Introduction to the STL, Parts 6 and 7

  • Comments 1

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 output of hypothetical contradiction analysis, copying the output of top-level analysis is pointless.

 

1.7 (10/20/2010) - Significantly accelerated Grid::confined() by using a linear vector<Flag>.

 

Take a look at the source code to see what's changed!

 

Stephan T. Lavavej

Visual C++ Libraries Developer

  • pls tell me what Visual C++ is. I show 4 different years on my computer????????????  Ruth Amore  

Page 1 of 1 (1 items)