DjangoBB LoFi version

Полная версия: Поиск повторяющихся элементов в большом кол-ве списков

Начало » Python для экспертов » Поиск повторяющихся элементов в большом кол-ве списков

1 2 3

PooH

Июль 9, 2017 05:58:28

py.user.next
То, что словарь не поместится в памяти, можно обойти через реализацию словаря через таблицу в базе данных. Есть такая возможность в sqlite3 сделать базу данных прямо в памяти.

База в памяти займет меньше места, чем словарь?

py.user.next

Июль 9, 2017 06:57:34

PooH
База в памяти займет меньше места, чем словарь?

Это искусственное ограничение питона для словарей. Пишет о нехватке памяти не потому, что там памяти не хватило.

  
>>> import pympler.asizeof
>>> 
>>> dct = {k: k for k in range(1000000)}
>>> 
>>> pympler.asizeof.asized(dct).format()
'{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6....99997, 999998: 999998, 999999: 999999} size=41165872 flat=25165872'
>>> 
>>> pympler.asizeof.asized(12345).format()
'12345 size=16 flat=16'
>>>

Хотя в любом случае получится 14Gb, если 3500 * 100000 брать. Наверное, питон просто вычисляет, хватит ли памяти, поэтому быстро выдаёт MemoryError, не заполняя всё до конца.

PooH

Июль 9, 2017 14:39:31

py.user.next
pympler

О! Клевая либа. Дзенкую!

artexcite

Июль 11, 2017 00:55:47

Спасибо всех за помощь.
Вариант с noSQL и со словарем мне очень понравился/
Скрипт работает. Все-таки 3 500 списков длиной от 7 тыс. до 100 тыс. элементов я так и не смог обработать, но 2 000 все-таки удалось и результат хороший.
Буду дальше разбираться.
Еще раз все спасибо.

py.user.next

Июль 11, 2017 02:21:12

artexcite
Все-таки 3 500 списков длиной от 7 тыс. до 100 тыс. элементов я так и не смог обработать,

Через оперативку не обработаешь, надо сохранять на диск все пары (число, количество вхождений). Оно только по скорости упадёт. Рассматриваем наихудший случай - это когда все числа во всех списках разные. При этом по памяти они займут 14Gb. А словарь всегда весь нужен, потому что одинаковые числа могут находиться на разных концах - в первом элементе первого списка и в последнем элементе последнего списка.

Можешь сделать словарь, который под капотом будет иметь общение с sqlite3, но снаружи это не будет видно. Просто скорость будет медленная, так как sqlite-базу надо будет на диске держать, а операции обращения к диску медленее, чем операции обращения к оперативке.

И в зависимости от количества элементов можешь передавать либо такой словарь для хранения пар, либо такой. Для 1000 строк в оперативке обрабатывать обычным словарём, а больше 1000 строк - уже на диске обрабатывать словарём на базе БД какой-нибудь быстрой.

PooH

Июль 11, 2017 05:14:03

А чем все таки плох вариант с таблицей счетчиков? Зачем вводить лишние сущности без нужды

py.user.next

Июль 11, 2017 08:15:53

PooH
А чем все таки плох вариант с таблицей счетчиков?

PooH
А если такой вариант, схему данных оставляем как есть, добавляем таблицу <id элемента> - <счетчик вхождений>. Конечно это не нормальная форма, но раз схема и была денормализованной. Существующие данные, конечно, довольно долго будет обрабатывать, но зато вполне кусками, прочитали кусок таблицы, обновили счетчики. После вполне можно на триггеры повесить обновление таблицы со счетчиками.

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

artexcite

Июль 11, 2017 09:01:00

Я поставил MongoDB и все данные перенес в нее в том числе и мои огромные списки.
Коллекция содержит данные в json формате и соответственно данные будут храниться следующим образом:

{ _id: 1, item: [41234567, 5678909, 64563223, 74456785, 8456788] }
{ _id: 2, item: [65645656, 5765767, 645645645, 654645, 56456456] }
{ _id: 3, item: [86778678, 675676, 675675675, 76465546, 6544656] }
и т. д.

Во время обработки списков я хочу использовать еще одну коллекцию (таблицу) этой БД:

{ _id: 1, item: 1223232, count: 1 }
{ _id: 2, item: 1454644, count: 2 }
{ _id: 3, item: 1345452, count: 4 }
и т. д.

Получается я избавляюсь от словарей и от потребности использовать много оперативки.
Ну а потом одним запросом можно получить результат.
Что касаемо скорости: 1000 списков я обработал за 2 минуты. В целом для моих потребностей эта скорость меня устраивает.
Конечно если использоваться БД, то скорость работы упадет, т.к. будет много обращений в нее.
Данный скрипт разрабатывается для использования только мною.