sparse_vector_dot_product_dok_vs_structs.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct SparseVec {
    std::vector<int> values;
    std::vector<int> indices;
};

int sparseVecMultMap(const unordered_map<int, int>& map1, const unordered_map<int, int>& map2) {

    int result = 0;

    auto shorter = map1.size() < map2.size() ? map1 : map2;

    for (const auto& kv : shorter) {
        const auto found = map2.find(kv.first);
        if (found != map2.end()) {
            result += found->second * kv.second;
        }
    }
    return result;
}

int sparseVecMultCSV(const SparseVec& vec0, const SparseVec& vec1) {

    int result = 0;
    int idx0 = 0;
    int idx1 = 0;

    while (idx0 < vec0.indices.size() && idx1 < vec1.indices.size()) {
        auto aIdx = vec0.indices[idx0];
        auto bIdx = vec1.indices[idx1];
        if (aIdx == bIdx) {
            result += vec0.values[idx0] * vec1.values[idx1];
            idx0++;
            idx1++;
        } else if (aIdx < bIdx) {
            idx0++;
        } else {
            idx1++;
        }
    }

    return result;

}

int main() {

    unordered_map<int, int> vec01 = {{0, 5}, {4, 3}, {5, 2}, {8, 7}};
    unordered_map<int, int> vec02 = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {5, 2}, {8, 1}};

    SparseVec vec11;
    vec11.values = {5, 3, 2, 7};
    vec11.indices = {0, 4, 5, 8};

    SparseVec vec12;
    vec12.values = {1, 2, 3, 4, 2, 1};
    vec12.indices = {0, 1, 2, 3, 5, 8};


    cout << sparseVecMultMap(vec01, vec02) << endl;
    cout << sparseVecMultCSV(vec11, vec12) << endl;

    return 0;
}