Почему lil_matrix и dok_matrix настолько медленны по сравнению с обычным dict of dicts?

Когда я изменяю ваш += на just = для ваших 2 разреженных массивов:

 for row, col in zip(rows, cols): #freqs[row,col] += 1 freqs[row,col] = 1 

их соответствующие времена сокращаются наполовину. Наибольшее время занимает индексирование. С += он должен делать как __getitem__ и __setitem__ .

Когда документы говорят, что dok и lil лучше подходят для итеративного построения, они означают, что легче расширить свои базовые структуры данных, чем для других форматов.

Когда я пытаюсь сделать csr матрицу с вашим кодом, я получаю:

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690: SparseEfficiencyWarning: изменение структуры разреженности csr_matrix является дорогостоящим. lil_matrix более эффективен. SparseEfficiencyWarning)

и на 30 раз медленнее.

Таким образом, требования скорости относятся к форматам, таким как csr , а не к чистым структурам Python или numpy .

Вы можете посмотреть код Python для dok_matrix.__get_item__ и dok_matrix.__set_item__ чтобы узнать, что происходит, когда вы делаете freq[r,c] .

---

Более быстрый способ построить ваш dok будет:

 freqs = dok_matrix((1000,1000)) d = dict() for row, col in zip(rows, cols): d[(row, col)] = 1 freqs.update(d) 

пользуясь тем, что dok является подклассом словаря. Обратите внимание, что матрица dok не является словарем словарей. Его клавишами являются кортежи (50,50) .

Еще один быстрый способ построения такого же разреженного массива:

 freqs = sparse.coo_matrix((np.ones(1000,int),(rows,cols))) 

Другими словами, поскольку у вас уже есть массивы rows и cols (или диапазоны), вычислите соответствующий массив data , а THEN постройте разреженный массив.

Но если вы должны выполнять разреженные операции над своей матрицей между шагами постепенного роста, то dok или lil могут быть вашим лучшим выбором.

---

Для задач линейной алгебры были разработаны разреженные матрицы, такие как решение линейного уравнения с большой разреженной матрицей. Я использовал их много лет назад в MATLAB для решения задач с конечной разницей. Для этой работы расчет дружественного формата csr является конечной целью, а формат coo – удобным форматом инициализации.

Теперь многие из SO scipy редкие вопросы возникают из scikit-learn и текстового анализа. Они также используются в файлах биологической базы данных. Но все-таки лучше всего работает метод (data),(row,col) .

Такие разреженные матрицы никогда не предназначались для быстрого постепенного создания. Традиционные структуры Python, такие как словари и списки, намного лучше для этого.

---

Вот более быстрая итерация dok которая использует его словарные методы. update работает так же быстро, как в обычном словаре. get примерно в 3 раза быстрее эквивалентной индексации ( freq[row,col] ). Индексирование, вероятно, использует get , но должно иметь много накладных расходов.

 def fast_dok(rows, cols): freqs = dok_matrix((1000,1000)) for row, col in zip(rows,cols): i = freqs.get((row,col),0) freqs.update({(row,col):i+1}) return freqs 

Пропуская get , и просто делаю

  freqs.update({(row,col): 1) 

еще быстрее – быстрее, чем defaultdict примера defaultdict, и почти так же быстро, как простая инициализация словаря ( {(r, c):1 for r,c in zip(rows, cols)} )

Существуют различные причины, по которым ваш тест несправедлив. Во-первых, вы включаете накладные расходы на создание разреженных матриц как часть вашего тайм-цикла.

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