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

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

Чтобы представить все эти «корреляции» или значения поплавка, я попытался использовать 2D-массив, но поскольку У меня есть 100 000 и более узлов, которые соответствовали бы 40 ГБ памяти или около того.

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

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

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

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

источник

2011-02-09 janoliver

Что относительно хеша/карты, где находится ключ (строка x col)? Он будет иметь только столько элементов, сколько записей в матрице с ненулевым значением. –

Это не совсем конкретный вопрос ... Да, редкие матрицы. Посмотрите на некоторые алгоритмы ... Возможно, с некоторыми подробностями о проценте узлов nulll в матрице или более подробной информации о симуляции, может быть, кто-то может предложить другие решения, чем графовое представление. – pascal

... например, что вы хотите сделать с этой матрицей? – pascal

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

источник

2011-02-09 08:30:13

Это хорошая идея. Один узел в среднем связан с 0,2% других узлов. Это зависит от параметров. – janoliver

Я немного обеспокоен работой процесса поиска. Это на самом деле гораздо важнее, чем, например, создание матрицы/hashmap, поскольку последнее выполняется только один раз ... – janoliver

@janoliver Итак, это 200 из 100 000 узлов? На скорости: поиск хэша - O (1), но постоянное время может быть большим, особенно если у вас мало памяти. (Сколько у вас есть?) Возможно, лучше всего было бы массив узлов с каждым узлом, содержащий список соседних узлов, отсортированных по номеру узла; бинарный поиск займет около 9 сравнений для 200 узлов. Это легко реализовать, и вы можете начать с него, и только при необходимости подумайте над чем-то другим. –

разреженная матрица подход звучат идеально подходит для этого. В Wikipedia article on sparse matrices обсуждается несколько подходов к реализации.

источник

2011-02-09 08:01:18

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

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

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

источник

2011-02-09 08:02:23

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

источник

2011-02-09 08:03:54

Привет, Джим, спасибо за идею. После быстрого просмотра этих списков кажется, что простое значение float, на которое ссылаются два индекса, потребляет меньше памяти, чем один из этих элементов списка. – janoliver

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

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

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

источник

2011-02-09 08:51:38 Flinsch

Несомненно 2 (k-1), потому что узел не будет ссылаться на себя? См. Мой комментарий по основному вопросу, я согласен, что это способ его решения. – SlappyTheFish

Обратите внимание, что список в каждом узле, где каждая запись в списке содержит номер узла, а ненулевое расстояние - это разреженная матрица формы, где каждый список узлов представляет собой строку (или столбец). –

@SlappyTheFish Flinsch написал «k - количество ненулевых значений в виртуальной матрице» - диагональ - это все нули в виртуальной матрице, поэтому k уже исключает эти записи. Список фактически включает k записей, где каждая запись имеет два значения, номер узла и расстояние. –

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

ответ

Смежные вопросы