Я ищу эффективную структуру данных для представления очень большой матрицы целых чисел в 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 на самом деле не использует ничего из того, что мог бы предоставить Cython.Есть ли более цитоническое решение для этого?К сожалению, 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 раз, стоимость выполнения в 10000 раз для моих реальных экспериментов.
Редактировать 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