Эффективный подход к использованию unordered_map для представления симметричной разреженной матрицы - PullRequest
Новая
       30

Эффективный подход к использованию unordered_map для представления симметричной разреженной матрицы

0 голосов
/ 02 февраля 2019

Я использую unordered_map контейнеры для представления симметричной разреженной матрицы.Это потому, что мне не нужно вычислять все позиции, и я могу использовать координаты как ключ для быстрого поиска данных.Моя карта выглядит следующим образом: 

typedef std::size_t coord1D;
typedef std::pair<coord1D,coord1D> coord2D;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};
typedef std::unordered_map<coord2D, std::shared_ptr<double>, pair_hash> my_map;

Дело в том, что каждый раз, когда я определяю установленное значение ключа, мне нужно указывать одно и то же значение для двух ключей ( например, . Пара ij иji) из-за треугольной природы матрицы это представляет, поэтому: 

my_map example;
example [std::make_pair(0,1)] = std::make_shared<double> (0.5);
example [std::make_pair(1,0)] = std::make_shared<double> (0.5);

Я думал о вспомогательной функции (поскольку operator= здесь не может быть переопределено), чтобы избежать избыточности кода, но яМне также интересно, есть ли более эффективный способ справиться с этой задачей.Я думаю, что используемый контейнер является наилучшим из возможных (поскольку unordered_multimap не требуется).

1 Ответ

0 голосов
/ 02 февраля 2019

Построение вашего матричного типа на typedef из unordered_map, похоже, не обеспечивает хорошую инкапсуляцию.Конечно, на первый взгляд, это, кажется, предлагает очень бережливое решение.Но, в конце концов, проблема с operator= является прекрасной демонстрацией того, как этот вид конструкции конфликтует с принципом открытия / закрытия .

Поэтому мое предложение будет заключаться в том, чтобы обернуть базовую структуру данных в класс для улучшения инкапсуляции (для простоты я использую double вместо общего указателя): 

using coord1D = std::size_t;    // time to forget about typedef ? 
using coord2D = std::pair<coord1D,coord1D>;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};
class matrix {
    std::unordered_map<coord2D, double, pair_hash> m; 
public: 
    auto& operator[] (pair<int,int> p) { 
        if (p.first>p.second)
            p = make_pair(p.second, p.first);
        return m[p];
    }
};

В этом случаеВы можете преобразовать параметр в operator[], чтобы сделать матрицу треугольной по конструкции, избегая избыточного кода и избыточного хранилища.

Демо: 

matrix m;
m[make_pair(1,5)] = 27.2;
cout << m[make_pair(1,5)]<<" "<<m[make_pair(5,1)]<<endl;

Онлайн демо

Конечно, лучшим способом было бы определить общую матрицу и вывести ее в формуспециализированная треугольная матрица, в которой происходит преобразование координат.

...