Быстрый доступ к элементам разреженной матрицы Compressed Sparse Row (CSR)

У вас есть так называемый триплетный разреженный формат. Создание CRS, включая удаление повторяющихся записей и суммирование значений, может быть реализовано очень эффективно. Прежде чем программировать его самостоятельно, ознакомьтесь с библиотекой SuiteSparse. Он написан на C, но я уверен, что вы поймете принцип. Что вас интересует, так это файл cholmod_triplet.c, в котором реализована нужная вам функциональность.

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

Редактировать Если вы хотите полностью пропустить явное создание формата триплета, вы можете сделать это, сгенерировав (row, col) связности на лету и добавив их в динамическую разреженную структуру. Я обычно делаю это с помощью сортировки вставками и отсортированных списков, что на практике является самым быстрым. Это также быстрее, чем преобразование триплета в CRS, и использует гораздо меньше памяти. Метод выглядит следующим образом:

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

  static_lists_cols[row] = malloc(sizeof(int)*expected_number_of_non_zeros) static_lists_vals[row] = malloc(sizeof(double)*expected_number_of_non_zeros)

• Если вы этого не знаете, вы выбираете начальный размер и перераспределяете по мере необходимости (используя некоторый размер блока, достаточно большой, чтобы избежать накладных расходов на перераспределение), когда списки строк заполнены.

• для каждой пары (row, col) вы вставляете col в отсортированный список, соответствующий row, используя сортировку вставками. Для небольших (до нескольких сотен) ненулевых значений в строке линейный поиск является самым быстрым. Для большего количества ненулевых значений в строке вы можете использовать деление пополам, чтобы найти правильное место для вставки индекса col.
• col вставляется в rowth отсортированный список путем перемещения ненулевых записей с более высоким индексом столбца в отсортированном списке. Это удобно для кеша, так как на практике строки достаточно малы, чтобы поместиться в любой кеш.
• После того, как вы закончите, вам нужно собрать отдельные отсортированные списки в допустимую структуру CRS, скопировав отдельные списки строк в окончательный columns. То же и с ценностями.
• На самом деле вы можете избежать последнего шага, предварительно выделив статический «массив списков», если вы согласны с тем, что некоторые строки могут иметь нулевые записи. Следовательно, у вас будет постоянное количество записей в строке, некоторые из которых могут быть нулевыми. Иногда это нормально.

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

• создание формата триплетов требует времени, и вам нужно записать триплеты в память
• преобразование в CRS требует чтения и записи триплетов по крайней мере один раз для их сортировки (на самом деле чуть больше одного раза, если вы посмотрите на алгоритм. Вы сортируете дважды, и вам нужны вспомогательные структуры данных).
• в зависимости от структуры связности у вас может получиться большое количество (row, col) дубликатов в формате триплета, которые удаляются во время сборки путем добавления соответствующих значений. Эти накладные расходы отсутствуют в приведенном выше методе — если col уже существует в списке строк, вы просто обновляете соответствующее значение.
• обновление отсортированных списков можно выполнять параллельно, если вы назначаете диапазоны строк отдельным рабочим процессам. Ни связи, ни синхронизации не требуется. Обеспечение балансировки нагрузки — это отдельная история…

Взгляните на сравнение производительности при использовании этих двух методов (рис. 1) для треугольных элементов в 2D. Обратите внимание, что разница в производительности зависит от отношения количества элементов в триплете к собранному формату разреженной матрицы (таблица 2). Но в целом метод никогда не бывает хуже, чем преобразование триплетов в crs, и триплеты нужно создавать в первую очередь. Вы также можете загрузить MEX-функцию MATLAB sparse_create, которая является частью пакета mutils (см. раздел загрузок).

Ваш вопрос, кажется, смешивает 2 довольно разных вопроса:

1. Как быстро создать матрицу в форме CSR?
2. Есть ли более быстрый способ чтения значений из матрицы, уже сохраненной в форме CSR? (Быстрее, чем описанный вами простой подход)

Итак, вот 2 ответа:

1. Как правило, считайте сетевые данные из любой формы, в которой они находятся, во что-то вроде словаря ключей ( доступны и другие промежуточные формы, которые могут быть более привлекательными для вас из-за скорости или по другим причинам); затем превратите эту промежуточную структуру в CSR-форму матрицы. Подробнее об этом ниже.
2. Я так не думаю, не с матрицей, хранящейся в форме CSR. Эта относительная медлительность доступа является частью цены, которую вы платите за экономию места. Вы обменяли время на пространство или пространство на время, в зависимости от вашей точки зрения.

Ваше описание ваших входных данных предполагает, что вам следует подумать о разработке собственной промежуточной формы для маршалинга необработанных данных. Поскольку ваша матрица смежности симметрична, вам нужно хранить в любой форме только ее половину. Кроме того, вам, вероятно, не нужно хранить элементы вдоль главной диагонали — я предполагаю, что либо узел i всегда связан с узлом i, либо никогда, так что характер сети определяет значение, хранящееся в (i,i). Я немного не уверен в информации, которую вы хотите хранить в каждом узле матрицы, это количество соединений между i и j или что-то еще?