Почему 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?
- Программно добавлять имена столбцов в numpy ndarray
- Numpy с десятичными аргументами Python
- Как выбрать первое вхождение повторяющегося элемента в последовательности в списке с использованием традиционного питона или с помощью pandas / numpy / sciy
- Выровнять диагонали данных в столбцы?
- Простое распознавание знаков OCR в OpenCV-Python
Когда я изменяю ваш +=
на 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 ко всему массиву.
- Numpy: используйте бункеры с бесконечным диапазоном
- тип данных не понят
- Система уравнений solver pandas
- Оценка доверительных интервалов вокруг фильтра Калмана
- Как установить диапазон значений в numpy для nan?
- Numpy – проверить, принадлежат ли элементы массива другому массиву
- Как получить индексы k максимальных значений из многомерного массива numpy
- Случайная мутация случайных чисел
- Создание тензоров третьего порядка с питоном и numpy