Python-сообщество

Например на диске лежит бинарный файл большого размера, который не может полностью поместиться в память, т.е. его нельзя загрузить полнсотью целиком.
Какие существуют методы работы с такими файлами в питоне?
По идее можно просто сместиться от начала файла и прочитать требуемый кусок памяти?
Но если я хочу работать с файлом как с array т.е. например узнать его размерность типа arr.shape (теоретически можно эту информацию хранить в хедере от файла, но возможно есть какой то метод из коробки?)


Существуют ли билиотеки которые позволяют например перемножить 2 матрицы которые не помещаются в память?

mmap?

идея такого алгоритма очень простая - делается блочное перемножение матриц.
http://facultyfp.salisbury.edu/taanastasio/COSC490/Fall03/Lectures/FoxMM/example.pdf
Непосредственной реализации на питоне не знаю, но думаю можно найти в документации по hdf5
http://www.pytables.org/docs/LargeDataAnalysis.pdf

У этой библиотеки можно настроить размер блочного хранения матриц так что он будет хорошо работать при перемножении.

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

А с hdf5 вы можете перемножать матрицы которые и на жесткий диск не влезают - просто делаете распределенное по кластеру хранилище :)

doza_and
А с hdf5 вы можете перемножать матрицы которые и на жесткий диск не влезают - просто делаете распределенное по кластеру хранилище

Просто любопытства ради, а в каких задачах возникают такие матрицы?

s0rg
mmap?

Если ОС 32 бит, то максимальный размер файла 2 Гб.

Отредактировано alexbadaloff (Апрель 19, 2013 09:16:18)

mmap?

linux only?

не знаю стоит ли связываться с hdf5? для каких задач это используется?
Может быть стоит посмотреть сразу в сторону каких то пакетов для Large-scale Data Mining тогда уж.


вообще у меня задача такая, что есть матрица nxm(n сэмплов m длина вектора) она не помещается в память, а надо сделать knn search по ней, найти например для данного вектора 10 ближайших.
Можно грузить кусками которые влезают в память и искать тупо попарно(тут только время поиска) или строить дерево и искать чуть быстрее(хотя тут будет уже время на построение дерева+ время поиска), хотя есть еще и knn на cuda (тут получается загрузка с диска+загрузка в память GPU + сам процесс).
Можно придумать какое то специальное дерево, листья которого лежат на диске, а верхушка в памяти, но писать самому такое не очень хочется, возможно есть что то готовое?

кстати насчёт матриц, я та кпонял что этот метод блочного перемножения используется когда матрица не помещается в L2 кэш.
например пробовал в матлабе делать PCA для матрицы(наверно там делается через SVD) например для матрицы 100000х10 делается довольно быстро, т.е. проблемы с тем что много сэмплов не возникает(не помню как зависит от самой длины вектора), а если матрица не помещается в память, то либо получаем out of memory,но если своп большой, то всё работает и так, т.е. всё ложится на плечи винды, но работает очень долго.
(есть вроде методы типа batch PCA, которые позволяют обрабатывать данные кусками, но вопрос тут больше стоит в том как работать с большими матрицами, т.е. оптимально ли полагаться что система всё сама разрулит кидая всё в своп)
кстати есть какой то алгоритм для SVD если не влезает полностью в память? это опять же полезно и для GPU у которого тоже ограниченная память.
если поставить вопрос более глобально есть ли матричные библиотеки, которые могут работать с матрицами которые не помещаются в память?

Отредактировано mrgloom (Апрель 19, 2013 09:39:06)

PooH
Просто любопытства ради, а в каких задачах возникают такие матрицы?

Погода, исследование течений.
Ну и, наверное, космос, ЦЕРН и прочие наукоемкие исследования с большим количество данных.

mrgloom
linux only?

C чего бы это?

mrgloom
вообще у меня задача такая,

Вы написали уже понятнее, но мне этого все равно не достаточно чтобы дать дельный совет.
размер матрицы m*n - какой характерный размер? 100000000 * 3 это или 10000*10000 алгоритм будет совсем разный (можно только догадываться что n ==10).
Насколько я понял есть множество элементов линейного метрического пространства. Насколько долго вычисляется расстояние по сравнению с временем дискового доступа к элементам?
Поиск однократный или выполняется много раз? Что для вас существеннее, время построения индекса или время поиска?

PooH
Просто любопытства ради, а в каких задачах возникают такие матрицы?

Не только из церна ветер дует. Сейчас такие задачи часто встречаются и очень прозаические. Например с чем приходилось сталкиваться:
1 есть б.д. преступников 100000 фото - сравнить новое лицо с базой.
2 есть небольшое предприятие хим завод, атомная станция и т.п. логи системы АСУТП порядка 10000-100000 значений добавление данных раз в несколько секунд. Характерное время накопления год. Поиск характерных состояний системы…
3 Аналогично биометрические показатели - ЭЭГ ЭКГ Поиск характерных состояний системы… Тут частота записи существенно выше а каналов меньше. Времена часы сутки. Но пациентов может быть много.
4 Найти магазин с молоком около моей текущей позиции - классика.

Судя по описанию тут подойдет RTree.

Ни разу не встречался с тем, чтобы своп дал приемлемое решение. Более того ни разу не было чтобы просто лобовая матричная запись тоже дала что-то приемлемое.

Отредактировано doza_and (Апрель 20, 2013 06:32:36)

Насколько долго вычисляется расстояние по сравнению с временем дискового доступа к элементам?

ну в общем случае хотелось бы адаптивный) типа тестируем железо и на основе этого уже делаем какую то структуру.
В общем случае кол-во сэмплов много больше чем длина вектора.
Сейчас тестирую на 100к сэмплов и длина вектора примерно 1к. (а хочется чтобы сэмплов было пару мильёнов)

Поиск однократный или выполняется много раз? Что для вас существеннее, время построения индекса или время поиска?

Поиск выполняется много раз и важно время поиска.

Опять же длина вектора вполне себе изменяемая величина, т.к. есть разные техники fеature selection/dimensionality reduction.
Но тут проблема опять упирается в память ,т.к. даже для простейшего PCA надо загружать всё в память(правда тут вроде как есть тоже выходы когда данные обрабатываются порциями).
Т.е. снижая размерность вектора мы можем ускорять поиск, тут главное правильно выбрать размерность до которой снижать ибо можно потерять и в точности.

Судя по описанию тут подойдет RTree.

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


вот например задачка БД 37 Гб
http://people.csail.mit.edu/jxiao/SUN/