Список индексов низкого объема памяти в Python - PullRequest
Новая
       6

Список индексов низкого объема памяти в Python

0 голосов
/ 06 февраля 2020

У меня есть следующий код: 

l = []
for i in range(A):
    for j in range(B):
        if predicate(i,j): 
            l.append((i, j))

Предположим, A и B являются очень очень большими числами [~ 10e7], поэтому l потенциально может иметь огромный размер A * B в худшем случае. Предположим, что функция predicate является общей функцией, которая решает, брать или не принимать кортеж (i,j).

. Мне бы хотелось решение, которое:

  1. Уменьшает объем памяти, необходимый для сохранения l
  2. Позволяет эффективную случайную разыменование элементов в l, т. Е. Мы выбираем случайный индекс k в range(len(l)) и вернуть l[k] быстро .
  3. Строит список l довольно быстро (может быть, append не подходит для использования?)

Я просто ничего, что ясно, что (1) , (2) и (3) может кла sh, и, возможно, python list не является правильным путем к go. Кто-нибудь может предложить другой метод?

Спасибо !!

1 Ответ

1 голос
/ 07 февраля 2020

Вместо кортежей и повторяющихся i, вы можете в основном просто хранить j -значения: 

l = []
prefixsum = [0]
for i in range(A):
    J = [j for j in range(B) if predicate(i,j)]
    l.append(J)
    prefixsum.append(prefixsum[-1]) + len(J))

Затем для заданного k, выполнить бинарный поиск в prefixsum, чтобы получить i, а затем найдите j в списке.

Кроме того, вместо списков int объектов вы также можете использовать Python массивы из 4-байтов. int (или 3-байтовые int с некоторой дополнительной работой). NumPy массивов, которые также могут ускорить все вычисления.

Грубый тест, игнорирующий некоторые издержки, на 64-битном Python: 

# A list of 100 tuples takes 888 bytes (just the list object)
> l = [(10**6, 10**6 + j) for j in range(100)]
> l = [(10**l.__sizeof__()
888

# The tuples take 4000 bytes
> l = [(10**sum(t.__sizeof__() for t in l)
4000

# The i-value takes 28 bytes
> l[0][0].__sizeof__()
28

# The j-values take 2800 bytes
sum(j.__sizeof__() for _, j in l)
2800

Так что это 7716 байт для списка 100 кортежей 2-х целых. Теперь array из j -значений: 

> a = array.array('I', (j for i, j in l))
> a = array.a.__sizeof__()
472

Это в 16 раз меньше памяти.

...