Large matrix with lots of repetitive fields (C++)

Question

I wrote a timetabling program and I have been using a matrix to check for clashes between courses. Index (i, j) in the matrix tells us how many people are in both courses i and j.

My previous Matrix was just using nested vectors:

std::vector<std::vector<int>> clashes;

This would throw std::bad_alloc because the matrix is of dimension 18000 x 18000.

Since many of the entries would be 0, I made my own matrix class using unordered maps. This preserves a lot of data as it uses a default value for all of entries that have not been given a value.

template <typename T>
class UMapMatrix
{
public:

UMapMatrix(T default_val) : default_val(default_val) {
}

T get(const int& a, const int& b) const {
    int x, y;
    if (a < b) {
        x = a;
        y = b;
    }
    else {
        x = b;
        y = a;
    }

    auto search = data.find(x);
    if (search != data.end()) {
        auto search2 = search->second.find(y);
        if (search2 != search->second.end()) {
            return search2->second;
        }
    }
    return default_val;
}

void set(const int& a, const int& b, T val) {
    if (a < b) data[a][b] = val;
    else data[b][a] = val;
}

private:
T default_val;
std::unordered_map<int, std::unordered_map<int, T>> data;
};

Are there any significant improvements that could be made to the memory usage and/or speed? Are there any other data structures that could be used here?

One possibility to consider would be "Compressed Row Storage", "Compressed Sparse Row" or "Yale format" (all different names for the same thing).Quite efficient for a variety of purposes, so it's pretty widely used. — Jerry Coffin
– Jerry Coffin, Commented Sep 12, 2019 at 0:14
Is there a reason you are nesting containers instead of using a single key that combines both numbers? — anon
– anon, Commented Sep 12, 2019 at 10:14

Loki Astari · Accepted Answer · 2019-09-12 20:49:01Z

Why have nested unordered_maps. Just use a single unordreed map using a key that is the x and y coordinates?

One enhancement I would add is using the operator[][] to access the elements.

#include <unordered_map>
#include <utility>
#include <iostream>
#include <functional>


template <typename T>
class UMapMatrix
{
    public:

        UMapMatrix(T const& default_val = T())
            : default_val(default_val)
        {   
        }   

        T const& get(int a, int b) const
        {   
            auto key    = getKey(a, b); 
            auto search = data.find(key);
            return (search != data.end())
                       ? search->second;
                       : default_val;
        }   

        void set(int a, int b, T const& val)
        {   
            data.insert(std::make_pair(getKey(a,b), val));
        }   
        void set(int a, int b, T&& val)
        {   
            data.insert(std::make_pair(getKey(a,b), std::move(val)));
        }

        class Row 
        {   
            UMapMatrix const* parent;
            int a;

            public:
            Row(UMapMatrix const* parent, int a)
                : parent(parent)
                , a(a)
            {}  
            T const& operator[](int b) const
            {   
                return parent->get(a, b); 
            }   
        };  
        Row operator[](int a) const {
            return Row{this, a}; 
        }   


    private:
        T default_val;
        using Key = std::pair<int, int>;
        struct PairHash
        {   
            std::size_t operator()(Key const& key) const
            {   
                return std::hash<int>()(key.first) ^ std::hash<int>()(key.second);
            }   
        };  


        Key getKey(int a, int b) const {

            int x = std::min(a, b); 
            int y = std::max(a, b); 
            return std::make_pair(x, y); 
        }   

        std::unordered_map<Key, T, PairHash>  data;
};

int main()
{
    UMapMatrix<int>     data;

    std::cout << data.get(1500, 3000) << "\n";
    data.set(1500, 3000, 234);

    std::cout << data[1500][3000] << "\n";
}

A minor suggestion: we can use std::minmax instead in getKey to save a comparison. — Juho
– Juho, Commented Sep 14, 2019 at 13:11

user555045 · Accepted Answer · 2019-09-13 07:42:47Z

There are some sparse matrix formats that are commonly used in linear algebra settings. However, they are not optimized for random access, they are optimized for various linear algebra tasks. So whether they make sense to use (and which of them makes the most sense) depends on how you use your matrix. The code so far only implements random access, but since it is common to prematurely abstract in that way, that does not necessarily tell me that you also primarily use the matrix in random access mode.

Similarly, a single hashmap with a pair as key could be used. That saves a level of indirection so it is useful for random access, but it would also mean that the data structure no longer automatically tracks the number of items in a row (which could be useful information for a constraint satisfaction algorithm, to quickly zero in on courses with the most conflicts), it's not unambiguously better. If you do this, the hash of the pair shouldn't be just the XOR of the coordinates, because it will collide any two pairs with swapped coordinates ((1,2) with (2,1) etc), and even more on top of that ((0,3) and (5,6) and (4,7) and (8,11) and (9,10) and (12,15) and their swapped versions also all on top of (1,2)).

Unfortunately an other significant issue is that std::unordered_map is just not a great hash map, there are many benchmarks (exhibit 1, exhibit 2, exhibit 3) and not only that, the existence of the bucket interface mandated by the standard bars efficient implementations. There are many nearly-drop-in replacements without the bucket interface that waste less memory and are faster for small keys/elements.

Stack Exchange Network

Large matrix with lots of repetitive fields (C++)

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Large matrix with lots of repetitive fields (C++)

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions