Ответ 1
Если вы не выполняете доступа на основе строк или столбцов, вы можете использовать dict с ключом кортежа, например A[(i,j)]
.
Я ищу эффективную структуру данных для представления очень большой матрицы целых чисел в 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
Если вы не выполняете доступа на основе строк или столбцов, вы можете использовать dict с ключом кортежа, например A[(i,j)]
.