Обработка больших плотных матриц в Python

Question

В принципе, каков наилучший способ хранения и использования плотных матриц в python?

У меня есть проект, который генерирует метрики сходства между каждым элементом в массиве.

Каждый элемент является пользовательским классом и хранит указатель на другой класс и число, представляющее его "близость" к этому классу.

В настоящее время он прекрасно работает примерно до ~ 8000 элементов, после чего происходит сбой из-за нехватки памяти.
В основном, если вы предполагаете, что каждое сравнение использует ~ 30 (кажется точным, основываясь на тестировании) байтов для хранения подобия, это означает, что общая требуемая память составляет:
numItems^2 * itemSize = Memory
Таким образом, использование памяти является экспоненциальным в зависимости от количества элементов.
В моем случае объем памяти составляет ~ 30 байт на ссылку, поэтому:
8000 * 8000 * 30 = 1,920,000,000 bytes, or 1.9 GB
который находится на пределе памяти для одного потока.

Мне кажется, что должен быть более эффективный способ сделать это. Я смотрел на меммэппинг, но он уже требовал значительных вычислительных ресурсов только для генерации значений подобия, и узкое место в жестком диске кажется немного нелепым.

Редактировать
Я смотрел на Numpy и Scipy. К сожалению, они также не поддерживают очень большие массивы.

>>> np.zeros((20000,20000), dtype=np.uint16)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError
>>>

Далее Редактировать
Numpy, кажется, популярен. Тем не менее, NumPy не будет делать то, что я хочу, по крайней мере без другого уровня абстракции.

Я не хочу для хранения чисел, я хочу хранить ссылки на классы. Numpy поддерживает объекты, но это не решает проблемы размера массива. Я привел numpy просто в качестве примера того, что не работает.

Любой совет?

Редактировать Ну, я просто переписал всю логику, чтобы он больше не сохранял никаких избыточных значений, уменьшая использование памяти с O*n^2 до O*((n*(n-1))/2).

По сути, вся эта история является версией проблемы рукопожатия , поэтому я перешел от хранения всех ссылок только к одной версии каждой ссылки.

Это не полное решение, но у меня обычно нет достаточно больших наборов данных, чтобы переполнить его, поэтому я думаю, что это сработает. PyTables действительно интересны, но я не знаю SQL, и, похоже, не существует какого-либо приятного традиционного способа нарезки или индексации для доступа к данным таблицы. Я могу вернуться к этому вопросу в будущем.

Answer 1

Ну, я нашел свое решение:
h5py

Это библиотека, которая в основном представляет собой простой интерфейс, но использует сжатые файлы memmapped для хранения массивов произвольного размера (это в основном оболочка для HDF5).

PyTables построен на нем, и PyTables фактически привел меня к этому. Однако мне не нужны какие-либо функциональные возможности SQL, являющиеся основным предложением PyTables, а PyTables не предоставляет чистый похожий на массив интерфейс, который я действительно искал.

h5py в основном действует как массив numpy и просто хранит данные в другом формате.

Кажется, он также не имеет ограничений по размеру массива, кроме, возможно, дискового пространства. В настоящее время я провожу тестирование на массиве uint16 в количестве 100 000 * 100 000

Answer 2

PyTables может обрабатывать таблицы произвольного размера (миллионы столбцов!), Используя memmap и некоторые умные сжатия.

Якобы, он обеспечивает производительность, подобную SQL, для python. Это, однако, потребует значительных изменений кода.

Я не приму этот ответ, пока не проведу более тщательную проверку, чтобы убедиться, что он действительно может делать то, что я хочу. Или кто-то предлагает лучшее решение.

Answer 3

Что касается 20 000 x 20 000, то вы смотрите на 12 ГБ ОЗУ?

Не собираетесь ли вы оказаться в аду подкачки, пытаясь работать с 12 ГБ в win32, который искусственно ограничивает память, которую может ОСадрес?

Я бы искал операционную систему, которая может поддерживать 12 ГБ (32 bin bin 2003 server может, если вам нужно придерживаться 32-битных окон), но 64-битную машину с 64-битной ОС и 16 ГБ ОЗУможет показаться более подходящим.

Хорошее оправдание для обновления:)

64-битный Numpy может поддерживать вашу матрицу

Python 2.5.2 (r252:60911, Jan 20 2010, 23:14:04) 
[GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> np.zeros((20000,20000),dtype=np.uint16)
array([[0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       ..., 
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0]], dtype=uint16)

Answer 4

Если у вас есть N объектов, хранящихся в списке L, и вы хотите сохранить сходство между каждым объектом и каждым другим объектом, это O(N**2) сходство. При общих условиях, что similarity(A, B) == similarity(B, A) и similarity(A, A) == 0, все, что вам нужно, это треугольный массив S сходств. Количество элементов в этом массиве будет N*(N-1)//2. Вы должны быть в состоянии использовать array.array для этой цели. Сохранение вашего сходства с плавающей точкой займет всего 8 байтов. Если вы можете представить свое сходство как целое число в range(256), вы используете беззнаковый байт в качестве элемента array.array.

Это примерно 8000 * 8000/2 * 8, то есть около 256 МБ. Использование только байта для подобия означает только 32 МБ. Вы можете избежать медленного вычисления индекса S[i*N-i*(i+1)//2+j] треугольника, используя симуляцию квадратного массива, вместо этого используя S [i * N + j] `; объем памяти увеличится вдвое (512 МБ для числа с плавающей запятой, 64 МБ для байта)

Если вышеприведенное не устраивает вас, возможно, вы могли бы объяснить "" "Каждый элемент [в каком контейнере?] Является пользовательским классом и хранит указатель на другой класс и число, представляющее его" близость " этот класс. "" и "" "Я не хочу хранить числа, я хочу сохранить ссылку на классы" "". Даже после замены "class (es)" на "object (s)", я изо всех сил чтобы понять, что ты имеешь в виду.

Answer 5

Вы можете уменьшить использование памяти, используя uint8, но будьте осторожны, чтобы избежать ошибок переполнения. Для uint16 требуется два байта, поэтому минимальное требование к памяти в вашем примере составляет 8000 *8000* 30 * 2 байта = 3,84 Гб.

Если второй пример не удался, вам нужен новый компьютер. Требуемая память составляет 20000 * 20000 * 2 * байт = 800 МБ.

Я советую вам попытаться создать меньшие матрицы и использовать "top", "ps v" или системный монитор gnome для проверки памяти, используемой вашим процессом python. Начните с изучения одной нити с небольшой матрицей и выполните математику. Обратите внимание, что вы можете освободить память переменной x, написав del (x). Это полезно для тестирования.

Какая память у вас на машине? Сколько памяти использует pytables для создания таблицы 20000 * 20000? Сколько памяти использует numpy для создания таблицы 20000 * 20000 с использованием uint8?

Answer 6

Вы можете найти некоторые советы в документации NumPy (см. SciPy) (массивы / матрицы):

• http://www.scipy.org/NumPy_for_Matlab_Users
• http://www.scipy.org/Tentative_NumPy_Tutorial