Структура данных Python для разреженного списка координат х / у

Question

Рассмотрим список координат х / у и число байтов. x / y будет иметь диапазон от 0 до 5000, что составляет 25 миллионов ячеек.

Однако данные будут довольно малочисленными, их будет не более нескольких тысяч, а большинство координат будут иметь нулевые записи.

Структура будет иногда просматриваться / добавляться (например, если есть что-то в x = 5 и y = 10, то ++), но чаще конвертируется в список x / y / count (сортировка не важна)

Самая быстрая структура данных для поиска - это, очевидно, двумерный массив, но вы смотрите на 24 МБ памяти или около того, итерация для вывода списка может быть дорогой. Для дискового хранилища вы можете реализовать сжатие в стиле gif, где 0 байт, за которыми следует другой байт, указывает на x пустых ячеек, а все остальное является значением ячейки - но это не помогает ситуации с памятью.

Словарь словарей, вероятно, будет хорошим балансом между скоростью поиска / итерации и использованием памяти.

Существуют ли другие подходящие структуры данных, которые я должен рассмотреть (встроенные в Python, существующие библиотеки или более общие структуры данных?

Answer 1

Словарь, снабженный точкой (то есть 2-кортеж), звучит хорошо для меня.Это O (1), как массив, и значительно более компактный.До тех пор, пока вам не нужно выполнять запросы диапазона или тому подобное, все должно быть в порядке.

# increment
p = (x, y)
counts[p] = counts.get(p, 0) + 1

# list
for (p, count) in counts.iteritems():
    x, y = p
    print x, y, count

Answer 2

scipy имеет диапазон различных разреженных массивов

Существует семь доступных типов разреженных матриц:
csc_matrix: формат сжатого разреженного столбца
csr_matrix: сжатый формат разреженной строки
bsr_matrix: формат блока разреженных строк
lil_matrix: формат списка списков
dok_matrix: формат словаря ключей
coo_matrix: формат COOrdinate (он же IJV, триплетный формат)
dia_matrix: DIAgonal формат

Answer 3

Это должно быть похоже на работу с разреженными матрицами размера вашего диапазона данных, здесь есть много вещей, которые нужно пережевать http://en.wikipedia.org/wiki/Sparse_matrix