Vector map unordered set test

test_lookups.cpp

// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <map>
#include <chrono>
#include <unordered_map>
#include <array>
#include <string>
#include <functional>
#include <algorithm>

// Generates a random string of length between 5 and 20
std::string generateRandomString()
{
    std::string randomString;
    int length = rand() % 15 + 5;
    for (int i = 0; i < length; i++)
    {
        randomString += rand() % 26 + 65;
    }
    return randomString;
}

// Generates a vector of random strings, given an input length
std::vector<std::string> generateRandomStrings(uint64_t length)
{
    std::vector<std::string> randomStrings;
    for (int i = 0; i < length; i++)
    {
        randomStrings.push_back(generateRandomString());
    }

    // Sort the set, then remove duplicates.
    std::sort(randomStrings.begin(), randomStrings.end());
    randomStrings.erase(std::unique(randomStrings.begin(), randomStrings.end()), randomStrings.end());

    return randomStrings;
}

// Given an input length, generates a vector of random strings. Creates a map, an unordered_map, and a sorted vector of
// the strings.
void generateMaps(uint64_t length)
{
    std::vector<std::string> randomStrings = generateRandomStrings(length);
    std::map<std::string, int> map;
    std::unordered_map<std::string, int> unorderedMap;
    std::vector<std::string> sortedVector = randomStrings;
    std::sort(sortedVector.begin(), sortedVector.end());
    for (int i = 0; i < length; i++)
    {
        map[randomStrings[i]] = i;
        unorderedMap[randomStrings[i]] = i;
    }

    // Shuffle the input random strings vector
    std::random_shuffle(randomStrings.begin(), randomStrings.end());

    // Start a precise timer. Look up the strings in the map, and determine the time difference.
    std::chrono::high_resolution_clock::time_point map_start = std::chrono::high_resolution_clock::now();
    int sum = 0;
    for (auto& i : randomStrings)
    {
        sum += map.find(i)->second;
    }
    std::chrono::high_resolution_clock::time_point map_end = std::chrono::high_resolution_clock::now();
    std::cout << "Sum: " << sum << "\n";

    // Start a precise timer. Look up the strings in the unordered_map, and determine the time difference.
    std::chrono::high_resolution_clock::time_point unordered_map_start = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (auto& i : randomStrings)
    {
        sum += unorderedMap.find(i)->second;
    }
    std::chrono::high_resolution_clock::time_point unordered_map_end = std::chrono::high_resolution_clock::now();
    std::cout << "Sum: " << sum << "\n";

    // Start a precise timer. Look up the strings in the sorted vector, and determine the time difference.
    std::chrono::high_resolution_clock::time_point sorted_vector_start = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (auto& i : randomStrings)
    {
        auto it = std::lower_bound(sortedVector.begin(), sortedVector.end(), i);
        if ((it != sortedVector.end()) && (*it == i))
        {
            sum += std::distance(sortedVector.begin(), it);
        }
    }
    std::chrono::high_resolution_clock::time_point sorted_vector_end = std::chrono::high_resolution_clock::now();
    std::cout << "Sum: " << sum << "\n";

    // Output the time differences, and a "cycles per second" metric.

    std::chrono::duration<double> map_time = std::chrono::duration_cast<std::chrono::duration<double>>(map_end - map_start);
    std::chrono::duration<double> unordered_map_time = std::chrono::duration_cast<std::chrono::duration<double>>(unordered_map_end - unordered_map_start);
    std::chrono::duration<double> sorted_vector_time = std::chrono::duration_cast<std::chrono::duration<double>>(sorted_vector_end - sorted_vector_start);

    // Set the double-formatting output to be 15 characters long, with 2 decimal places.
    std::cout.precision(5);
    std::cout << std::fixed;
    std::cout << "Length: " << length << "\n";
    std::cout << "Map time: " << map_time.count() << "s, " << ((double)length / map_time.count()) << " cycles per second\n";
    std::cout << "Unordered map time: " << unordered_map_time.count() << "s, " << ((double)length / unordered_map_time.count()) << " cycles per second\n";
    std::cout << "Sorted vector time: " << sorted_vector_time.count() << "s, " << ((double)length / sorted_vector_time.count()) << " cycles per second\n";
}

int main()
{
    std::cout << "Hello World!\n";

    generateMaps(5);
    generateMaps(50);
    generateMaps(500);
    generateMaps(5000);
    generateMaps(5000000);
}