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

Я хочу итеративно создавать разреженные матрицы и заметил, что в соответствии с документацией SciPy есть два подходящих варианта:

LiL-матрица :

class scipy.sparse.lil_matrix (arg1, shape = None, dtype = None, copy = False) [source] Строчная матрица связанных строк на основе строки

Это эффективная структура для постепенного построения разреженных матриц.

Матрица DoK :

class scipy.sparse.dok_matrix (arg1, shape = None, dtype = None, copy = False) [источник] Словарная база на основе разреженной матрицы.

Это эффективная структура для постепенного построения разреженных матриц.

Но когда я запускаю тесты по сравнению со построением словаря значений слова (который позже может быть легко преобразован в разреженную матрицу), последний оказывается примерно в 10-20 раз быстрее, чем с использованием любой из разреженных матричных моделей:

from scipy.sparse import dok_matrix, lil_matrix from timeit import timeit from collections import defaultdict def common_dict(rows, cols): freqs = defaultdict(lambda: defaultdict(int)) for row, col in zip(rows, cols): freqs[row][col] += 1 return freqs def dok(rows, cols): freqs = dok_matrix((1000,1000)) for row, col in zip(rows, cols): freqs[row,col] += 1 return freqs def lil(rows, cols): freqs = lil_matrix((1000,1000)) for row, col in zip(rows, cols): freqs[row,col] += 1 return freqs def benchmark(): cols = range(1000) rows = range(1000) res = timeit("common_dict({},{})".format(rows, cols), "from __main__ import common_dict", number=100) print("common_dict: {}".format(res)) res = timeit("dok({},{})".format(rows, cols), "from __main__ import dok", number=100) print("dok: {}".format(res)) res = timeit("lil({},{})".format(rows, cols), "from __main__ import lil", number=100) print("lil: {}".format(res)) 

Результаты:

 benchmark() common_dict: 0.11778324202168733 dok: 2.2927695910912007 lil: 1.3541790939634666 

Что вызывает такие накладные расходы для матричных моделей, и есть ли способ ускорить его? Существуют ли случаи, когда либо док, либо лил предпочитают более общий диктофон 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 ко всему массиву.