Как реализовать огромную матрицу на С

Question

Я пишу программу для численного моделирования на C. Частью моделирования являются пространственно фиксированные узлы, которые имеют некоторое значение с плавающей точкой для каждого другого узла. Это как ориентированный граф. Однако, если два узла находятся слишком далеко, (дальше, чем некоторая длина отсечки a), это значение равно 0.

Чтобы представить все эти "корреляции" или значения с плавающей точкой, я попытался использовать двумерный массив, но, поскольку у меня 100 000 и более узлов, это будет соответствовать 40 ГБ памяти или около того.

Теперь я пытаюсь придумать разные решения этой проблемы. Я не хочу сохранять все эти значения на жестком диске. Я также не хочу рассчитывать их на лету. Одной из идей была какая-то разреженная матрица, например та, которую можно использовать в Matlab.

Есть ли у вас другие идеи, как хранить эти значения?

Я новичок в C, поэтому, пожалуйста, не ожидайте слишком много опыта.

Спасибо и всего наилучшего, Ян Оливер

Answer 1

Сколько узлов в среднем находятся на расстоянии отсечки для данного узла, определяет ваши требования к памяти и говорит вам, нужно ли вам перелистывать на диск. Решение, использующее наименьшее количество памяти, вероятно, представляет собой хеш-таблицу, которая отображает пару узлов на расстояние. Поскольку расстояние одинаково во всех отношениях, вам нужно ввести его в хеш-таблицу только один раз для пары - поместите два номера узлов в числовом порядке, а затем объедините их, чтобы сформировать ключ хеш-функции. Вы можете использовать функции Posix hsearch / hcreate / hdestroy для хеш-таблицы, хотя они не идеальны.

Answer 2

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

Answer 3

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

Answer 4

Вы также можете хранить список для каждого узла, который содержит другие узлы, с которыми связан этот узел.Тогда общее число записей в списке будет равно 2 * k , где k - число ненулевых значений в виртуальной матрице.

РеализацияОжидается, что вся система как комбинация хешей / наборов / карт все еще будет приемлемой с точки зрения скорости / производительности по сравнению с «реальной» матрицей, допускающей произвольный доступ.

edit : Это решениеявляется одной из возможных форм реализации разреженной матрицы.(См. Также примечание Джима Балтера ниже. Спасибо, Джим.)

Answer 5

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

Если у вас есть доступ к matlab, это определенно будет лучше банкомат.

Без использования разреженной матрицы вы могли бы подумать об использовании массивов на основе memap, чтобы вам не требовалось 40 ГБ ОЗУ, но это все равно будет медленным и имеет смысл, только если у вас низкая степень разреженности ( скажем, если в 10-20% вашей матрицы 100000x100000 есть элементы, то полные массивы будут на самом деле быстрее и, возможно, даже будут занимать меньше места, чем разреженные матрицы).