Умножение большой матрицы в Python - что является лучшим вариантом?

Question

У меня есть две булевы разреженные квадратные матрицы c. 80 000 x 80 000, генерируемых из 12BM данных (и я, вероятно, буду иметь порядок больших матриц, когда я использую GBs данных).

Я хочу их умножить (что создает треугольную матрицу - однако я не получаю это, так как я не ограничиваю произведение точек на треугольную матрицу).

Мне интересно, какой лучший способ их умножения (по памяти и по скорости) - я собираюсь выполнить вычисления на экземпляре m2.4xlarge AWS, который имеет> 60 ГБ ОЗУ. Я бы предпочел сохранить calc в RAM по причинам скорости.

Я ценю, что SciPy имеет разреженные матрицы, а также h5py, но у них нет опыта.

Какой вариант лучше всего подходит?

Заранее спасибо

UPDATE: разреженности булевых матриц < 0,6%

Answer 1

Если матрицы относительно пусто было бы целесообразно кодирующими их в качестве структуры данных не-ложных значений. Произнесите список кортежей, описывающих расположение значений, отличных от False. Или словарь с кортежами в качестве ключей.

Если вы используете, например, список кортежей, вы можете использовать понимание списка, чтобы найти элементы во втором списке, которые можно умножить на элемент из первого списка.

a = [(0,0), (3,7), (5,2)] # et cetera 
b = ... # idem 

for r, c in a: 
    res = [(r, k) for j, k in b if k == j] 

Answer 2

- отредактирован УДОВЛЕТВОРИТЬ НИЖЕ COMMENT/DOWNVOTER -

Вы спрашиваете, как умножать матрицы легко и быстро.

РЕШЕНИЕ 1: Это решаемая проблема: используйте numpy. Все эти операции легки в numpy, и поскольку они реализованы на C, они довольно быстро развиваются.

• http://www.numpy.org/
• http://www.scipy.org

также смотрите:

• Very large matrices using Python and NumPy
• http://docs.scipy.org/doc/scipy/reference/sparse.html

SciPy и Numpy имеют разреженные матрицы и умножение матрицы. Он не использует много памяти, поскольку (по крайней мере, если я написал его на языке C), он, вероятно, использует связанные списки и, следовательно, будет использовать только память, необходимую для суммы данных, а также некоторые накладные расходы. И это почти наверняка будет невероятно быстрым по сравнению с чистым решением python.

РЕШЕНИЕ 2

Другой ответ здесь предполагает хранение значений в качестве кортежей (х, у), предполагая значение ЛОЖЬ, если оно не существует, то это правда.Альтернативой этому является числовая матрица с (x, y, value) кортежами.

НЕЗАВИСИМО: Умножив это будет Настя времени мудро: найти один элемент, решить, какой другой элемент массива, чтобы умножить, а затем искать весь набор данных для этого конкретного кортежа, и если он существует, умножать и вставить результат в матрицу результатов.

РЕШЕНИЕ 3 (PREFERRED против решения 2, ИМХО)

Я предпочел бы это, потому что это проще/быстрее.

Представьте свою разреженную матрицу с набором словарей. Матрица представляет собой один ДИКТ с элементом в точке (х, у) и значение (об существа с x1, y1, x2, y2 и т.д.):

matrixDictOne = { 'x1:y1' : v1, 'x2:y2': v2, ... } 
matrixDictTwo = { 'x1:y1' : v1, 'x2:y2': v2, ... } 

Поскольку Python ДИКТ поиска является O (1) (хорошо, на самом деле, вероятно, ближе к log (n)), это быстро. Это не требует поиска всех данных второй матрицы для присутствия элемента перед умножением. Итак, это быстро. Легко написать многократно и легко понять представления.

РЕШЕНИЕ 4 (если вы мазохист)

код это решение с помощью отображенного в память файла требуемого размера. Инициализируйте файл с нулевыми значениями требуемого размера. Вычислите смещения самостоятельно и напишите в соответствующие места в файле, как вы делаете умножение. Linux имеет VMM, который будет загружаться и выходить за вас с небольшими накладными расходами или работать с вашей стороны. Это решение для очень, очень больших матриц, которые НЕ SPARSE и, следовательно, не поместится в памяти.

Примечание: решает жалобу нижнего подателя жалобы, что она не поместится в памяти. Тем не менее, OP действительно сказал редкий, что подразумевает очень мало фактических данных, распространенных в гигантских массивах, и Numpy/SciPy обрабатывают это изначально и, следовательно, красиво (много людей в Fermilab регулярно используют Numpy/SciPy, я уверен, что редкий матричный код хорошо протестирован).