Listing 6 in Section 2.8 does not test the contains operation

[DaveParillo]

Describe the bug Section 2.8 claims to compare vector and hash table "contains operations".

• There is no 'contains' for vector.
• The C++ example code does not produce the graph shown
• The C++ example code does not test anything related to contains or find operations, it measures filling the 2 containers
• If you compile and run the code 'as is', you find the vector is faster, even with push_back in a loop.

To Reproduce Steps to reproduce the behavior:

1. Go to analysis of hash table
2. Compile c++ listing 6 and run program
3. Observe the output does not match the text or the graph

Sample actual results.

Expected behavior Expected results

Recommendations

• Modify the text so that is is more appropriate for C++ - currently it's more of the original python description. For example: "we will confirm that the contains operator for vectors" should refer to find: std::find in the case of vector and std::unordered_map::find for the map.

• The listing line number references ("The difference is that on line 7 x is vector, and on line 9 x is a hash table." refer to the original python code, not the C++ in listing 6.

• The text says "Listing 6 implements this comparison. Notice that we are performing exactly the same operation, number in container. " - this is not the case for the C++ listing 6.

• The text says "then we will pick numbers at random and check to see if the numbers are in the vector."

  • There is no code in the program for this. The vector is not randomized. Personally, I think it is more compelling to show that even when the vector data is sorted the unordered map performance is far better. Even if you wrote your own binary search on the sorted vector data, the unordered map would still beat it.
  • The program fills the vector with monotonically increasing values and then tries to find all of them anyways. So randomizing them before the search would have no effect on the overall timing.

• Change the code to find values in each container and avoid timing container construct and fill operations.

• Consider replacing ctime with std::chrono

• Sample solution:

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    cout << std::setw(6) << "size\t"
         << std::setw(8) << "vector\t\t"
         << std::setw(8) << "hash table" << '\n';
    for(int a = 1000; a < 1e5; a += 1e4) {
        // vector Part
        vvector<int> avector (a);                        // reserve memory
        std::iota(avector.begin(), avector.end(), 0);    // fill vector
        // search vector
        auto begin = std::chrono::steady_clock::now();
        for( int i = 0; i < a; ++i){
            if(std::find(avector.begin(), avector.end(), i) == avector.end()) {
                std::cerr << "Failed to find an expected value! Halting.\n";
                return -1;
            }
        }
        auto end = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed_secs = end - begin;
        // Hash Table Part
        unordered_map<int, int> table;
        for( int j = 0; j < a; ++j ){
            table[j] = j;
        }
        auto begin_ht = std::chrono::steady_clock::now();
        // search hash table
        for( int j = 0; j < a; ++j){
            if(table.find(j) == table.end()) {
                std::cerr << "Failed to find an expected value! Halting.\n";
                return -2;
            }
        }
        auto end_ht = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed_secs_ht = end_ht - begin_ht;

        // Printing final output
        cout << std::setw(6) << a << '\t'
             << std::setw(8) << elapsed_secs.count() << '\t'
             << std::setw(8) << elapsed_secs_ht.count() << '\n';
    }
    return 0;
}

[pearcej]

@DaveParillo good idea! I welcome a pull-request... or I will have my students fix.

[DaveParillo]

I would be willing to work on this, but . . .

1. it's not clear to me where the fix should be implemented. This repo appears to contain a runestone and a pretext implementation.
2. When I build the runestone version of this book, I get a lot sphinx template stuff in rendered pages {{ if response.serve_ad and settings.adsenseid: }} {{ pass }} etc.
3. Not sure how the images were generated. I can make new images for the timing results, but they won't look like the other images in this book.

If you are OK with me simply making changes to AlgorithmAnalysis/HashTableAnalysis.rst and verifying those changes are valid, then I can do that.

I am assuming you would rather replace std::chrono calls with the C time functions you use in other examples.