Эффективная структура для элементарного доступа к очень большой разреженной матрице (Python/Cython)

Я ищу эффективную структуру данных для представления очень большой матрицы целых чисел в Python/Cython с акцентом на элементарные операции.

В настоящее время я создаю модель, которая требует много элементарных операций на большой, очень разреженной матрице (около 50 бит на чтение/запись на матрице 2MMx500k). Раньше я запускал эксперименты с меньшими данными и использовал Python с массивами Cython и Numpy и в идеале хотел бы продолжать использовать некоторые части существующей инфраструктуры.

Несколько вариантов, которые я просмотрел/реализовал до сих пор. Они могут быть не полностью оптимизированы, но все реализации должны быть достаточно хорошими, чтобы дать реалистичное представление о потенциале каждого подхода. Я тестировал, создав матрицу 2MMx500k, добавив 25MM-элементов, а затем снова удалив их. Это отражает те операции, которые мне нужны.

29 minutes: Cython lists to fill scipy.sparse.coo -> sparse.dok 
10 minutes: Cython lists to fill scipy.sparse.coo -> sparse.lil 
 3 minutes: Dict, s.t. A["%d_%d" % (i,j)] contains M[i][j]
 3 minutes: Dict, s.t. A[(i,j)] contains M[i][j]
<1 minute:  Dict, s.t. A[i*N,j] contains M[i][j]
<1 minute:  <std::map> using Cython

Взлом команды dict вместе лучше всего работает до сих пор, но все еще довольно медленный. Также он чувствует себя слишком сильно из-за взлома, поэтому я предполагаю, что там должен быть более эффективный метод, особенно учитывая, что решение dict не использует ни один из возможных возможностей Cython. Для этого существует более Cythonic решение? Google был не очень полезен, к сожалению (или у меня не было правильных ключевых слов для поиска).

Любые предложения о том, как это сделать, будут очень признательны!

Изменить 1

Разница между двумя словарными решениями заключается в том, что вариант A [ "% d_% d" % (i, j)] является более быстрым для доступа, тогда как вариант A [(i, j)] является более быстрым для установки.

                                                  Setup    Execution
Dict, s.t. A["%d_%d" % (i,j)] contains M[i][j]    180s      30s
Dict, s.t. A[(i,j)] contains M[i][j]               66s     104s
Dict, s.t. Dict, s.t. A[i*N,j] contains M[i][j]    40s       8s

В то время как A [ "% d_% d" % (i, j)] в текущем тесте будет немного медленнее, было бы предпочтительным в долгосрочной перспективе, поскольку стоимость установки увеличится только в 10 раз, выполнение для моих реальных экспериментов стоить в 10 000 раз.

Изменить 2

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

cdef unsigned int key(int a, int b): return a * 10000000 + b

По-прежнему возможно дальнейшее улучшение скорости, оптимизируя dict или перемещая структуру данных на C, но это должно быть достаточно быстро для моих целей. Однако любые другие предложения будут очень приветствуемы! Будет отчитываться, если я найду более эффективное решение, используя stl-карту или аналогичные структуры данных.

Изменить 3

Следуя советам коллеги, я также внедрил систему, используя <std::map> через интерфейс Cython для хранения данных на карте <int,int>. Реализация на самом деле медленнее, чем реализация dict, когда у нас есть большие объемы данных, причем ключевое различие заключается в скорости доступа:

                  Small data (25MM elements)         Large data (250MM elements)
          Time    total    setup    read/write       total    setup    read/write
Dict[int keys]      40s      25s       8s             369s     269s      72s
<std::map>          26s      11s      12s             376s     169s     177s

Ответы

Ответ 1

Если вы не выполняете доступа на основе строк или столбцов, вы можете использовать dict с ключом кортежа, например A[(i,j)].