Array vs Hash loopup relative speeds

.md

Python version

import time
import random

N = 100_000_000      # Size of array and dict
LOOKUPS = 10_000_000 # Number of random lookups

# Set up the data structures
arr = [(i, i) for i in range(N)]
dct = {i: i for i in range(N)}

# Prepare random indices
random_indices = [random.randint(0, N-1) for _ in range(LOOKUPS)]

def test_array_random(arr, indices):
    s = 0
    for i in indices:
        s += arr[i][1]
    return s

def test_dict_random(dct, indices):
    s = 0
    for i in indices:
        s += dct[i]
    return s

print("Testing array of tuples with random lookups...")
start = time.time()
print("Array sum:", test_array_random(arr, random_indices))
print("Array time:", time.time() - start)

print("\nTesting dict with random lookups...")
start = time.time()
print("Dict sum:", test_dict_random(dct, random_indices))
print("Dict time:", time.time() - start)

Results:

Testing array of tuples with random lookups...
Array sum: 499982475280328
Array time: 2.8302018642425537

Testing dict with random lookups...
Dict sum: 499982475280328
Dict time: 4.755800724029541

C++ version

#include <iostream>
#include <vector>
#include <unordered_map>
#include <random>
#include <chrono>

int main() {
    using namespace std;
    using namespace std::chrono;

    const int N = 100'000'000;         // Array and map size
    const int LOOKUPS = 10'000'000;    // Number of random lookups

    // Set up the data structures
    cout << "Allocating vector..." << endl;
    vector<pair<int, int>> arr;
    arr.reserve(N);
    for (int i = 0; i < N; ++i)
        arr.emplace_back(i, i);

    cout << "Allocating unordered_map..." << endl;
    unordered_map<int, int> dct;
    dct.reserve(N); // Reserve for efficiency, but unordered_map is not required to not rehash

    for (int i = 0; i < N; ++i)
        dct[i] = i;

    // Prepare random indices
    cout << "Generating random indices..." << endl;
    vector<int> random_indices(LOOKUPS);
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, N - 1);
    for (int i = 0; i < LOOKUPS; ++i)
        random_indices[i] = dist(rng);

    // Test vector (array of tuples)
    cout << "Testing vector of pairs with random lookups..." << endl;
    auto start = high_resolution_clock::now();
    long long arr_sum = 0;
    for (int i = 0; i < LOOKUPS; ++i) {
        arr_sum += arr[random_indices[i]].second;
    }
    auto end = high_resolution_clock::now();
    cout << "Array sum: " << arr_sum << endl;
    cout << "Array time: "
         << duration_cast<duration<double>>(end - start).count() << " seconds" << endl;

    // Test unordered_map (dict)
    cout << "\nTesting unordered_map with random lookups..." << endl;
    start = high_resolution_clock::now();
    long long dict_sum = 0;
    for (int i = 0; i < LOOKUPS; ++i) {
        dict_sum += dct[random_indices[i]];
    }
    end = high_resolution_clock::now();
    cout << "Dict sum: " << dict_sum << endl;
    cout << "Dict time: "
         << duration_cast<duration<double>>(end - start).count() << " seconds" << endl;

    return 0;
}

Results:

Allocating vector...
Allocating unordered_map...
Generating random indices...
Testing vector of pairs with random lookups...
Array sum: 499888961017249
Array time: 0.102858 seconds

Testing unordered_map with random lookups...
Dict sum: 499888961017249
Dict time: 2.49473 seconds