Ograniczanie pamięci używanej przez dużego dicta

Question

Potrzebuję utworzyć obiekt w pamięci zawierający klucze składające się z 9-cyfrowej liczby całkowitej i wartości logicznej przypisanej do każdego klucza. Używam dict jak w uproszczonym przykładzie poniżej:

#!/usr/bin/python 
from __future__ import print_function 
import sys 

myDict = {} 
for n in range(56000): 
     myDict[n] = True 

print('Count:',len(myDict),' Size:', sys.getsizeof(myDict)) 

muszę być w stanie wyszukać i pobrać wartość logiczną powiązanych z każdym klawiszem. Problemem jest rozmiar dyktatu. Używając Pythona 2.7 na 64-bitowym systemie Linux i powyższym przykładzie, rozmiar dyktatury wynosi 3,1 megabajty zgodnie z sys.getsizeof(). (około 56 bajtów na hasło do zapisu 9 cyfr plus wartość boolowska)

Potrzebuję zapisać stan boolowski (około) 55.000 wpisów w dyktafonie. Każdy klucz dyktujący jest 9 cyfrową liczbą całkowitą. Próbowałem używać liczb całkowitych i str (theInteger) jako kluczy bez zmiany wielkości dyktatu.

Czy istnieje jakiś inny rodzaj struktury danych lub metodologii, których powinienem używać, aby oszczędzać pamięć przy tak dużym zbiorze danych?

Answer 1

Jeśli przyjrzeć się swoją logiczną za pomocą klucza całkowitą, a zakres kluczy zaczyna się od 0 i jest ciągła, nie ma naprawdę żadnego powodu nie używać listę:

my_list = [] 
for n in range(56000): 
     my_list[n] = True 

lub lepiej:

my_list = [True for n in range(5600]) 

Jeśli to nie wystarczy, spróbuj moduł array i wykorzystywać jeden bajt za bool:

import array 
my_array = array.array("b", (True for n in range(56000))) 

A jeśli to nie wystarczy, wypróbuj wersję bitarray module on PyPi.

Innym pomysłem jest użycie set: Powiedzmy, że masz dużo więcej False niż True, wystarczy mieć zestaw:

my_true_numbers = {0, 2323, 23452} # just the True ones 

i sprawdzić z

value = number in my_true_numbers 

Jeśli masz więcej True niż False Zrób to na odwrót.

Answer 2

Przyjęta odpowiedź Python: Reducing memory usage of dictionary zawiera wniosek, że niewiele można z tym zrobić i zgadzam się z nią. Ogólny nakład na pamięć słownika jest niewielki, ale liczba par klucz-wartość twojego przykładu podnosi ślad pamięci.

Może się wydawać, że to możliwe: jeśli klucze są zawsze liniowe, można utworzyć listę booleans bezpośrednio lub lepiej użyć bitarray. Klucze byłyby wówczas niejawne. Ale jeśli jest to tylko w twoim przypadku, nie możesz wiele zrobić.

Answer 3

Dlaczego nie użyć gigantycznego bitfield? Tworzysz dane na dwóch bitach, ponieważ potrzebujesz co najmniej trzech wartości: true, false i not_init/UB. Całkowita używana pamięć to 55.000*2 bits = 110 000 bits = 13 kBytes.

Zestaw flag jest tutaj, aby upewnić się, że wartość został prawidłowo ustawiony przez użytkownika (nie jest to konieczne), a drugi nieco zawiera wartość.

Używanie 64 bit unsigned integers z nich wymaga tylko 203 do przechowywania całej tablicy.

Następnie można uzyskać do niego dostęp za pomocą indeksu bitów: załóżmy, że chcesz uzyskać dostęp do wartości w indeksie 123. będziesz musiał uzyskać dostęp do bit #246 ans #247 (jeden dla zestawu bool, a drugi dla wartości).

Od 246 i 247 są gorsze od 2**64, są przechowywane na first uint. Aby uzyskać do nich dostęp:

return (((1<<246) & array[0]) >> 246) 

aby uzyskać dostęp do dowolnego bitu:

return (((1<<n) & array[ n/(2**64) ]) >> n) 

(nie testowałem bitowy akcesor)

Ustaw bit:

array[ n/(2**64) ] = array[ n/(2**64) ] | (1<<n) 

operacje bitowe są trudne (przesunięcie arytmetyczne vs logiczne) i niełatwe do debugowania, ale mogą być niezwykle potężne.

Answer 4

Jeśli „klucz nie znaleziono” nie jest ważny stan dla Ciebie (tj jesteś OK z leczenia nie kluczy w tablicy jako False), można użyć set zamiast przechowywać tylko odwzorowanie elementów do True. Wymaga to około 30% mniej miejsca, ponieważ każdy wpis składa się z zaledwie dwóch 64-bitowych ilości (hash i klucz) zamiast trzech ilości (hash, klucz, wartość).

Należy pamiętać, że sys.getsizeof(dict) mówi tylko o rozmiarze samego dict, a nie o obiektach w nim zawartych. Tworzenie kluczy ma również własny koszt: 24 bajty na liczbę całkowitą (wskaźnik typu, refcount, wartość). To będzie samo w sobie 1,3MB, oprócz pamięci wziętej przez słownik.

Aby naprawdę zaoszczędzić miejsce, można użyć NumPy sprężonego rzadki wierszowi matrycy:

from scipy.sparse import lil_matrix # linked-list matrix, used to construct the csr matrix 
vals = lil_matrix((1,1000000000), dtype='int8')) 
# We will use 0 = no such key, 1 = True, 2 = False 
for n in myIndices: 
    vals[n] = 1 
vals = vals.tocsr() 

Wykorzystanie pamięci vals jest bardzo mała: 56kb dla danych, 224KB dla indeksów, a mniej niż 1 KB na inne konstrukcje. Całkowity rozmiar jest zatem mniejszy niż 281KB (10 razy mniejszy niż dyktatura), bez dodatkowych przydzielonych liczb całkowitych. Wyszukiwanie elementów i zmiana niezerowych elementów jest bardzo szybkie (wyszukiwanie binarne w posortowanej tablicy), ale wstawienie nowej niezerowej wartości lub wyzerowanie istniejącej niezerowej wartości są kosztownymi operacjami.

Answer 5

W zależności od Twoich potrzeb możesz użyć listy do przechowywania swoich wartości. Spowoduje to użycie około 16% przestrzeni używanej przez słownik, ale niektóre operacje, takie jak wyszukiwanie i wstawianie, będą (prawdopodobnie dużo) wolniejsze.

values = list(range(56000)) 

Jeśli używasz modułu bisect i przechowywanie wartości w liście posortowanej, odpytywanie nadal będzie wolniejsze niż z dict, ale znacznie szybciej niż naiwnego x in my_list czeku.

Lista musi być zawsze uporządkowana w porządku posortowanym.Aby sprawdzić, czy wartość znajduje się na liście, można użyć tej funkcji:

def is_in_list(values, x): 
    i = bisect_left(values, x) 
    return i != len(values) and values[i] == x 

działa tak:

>>> is_in_list([2, 4, 14, 15], 4) 
True 
>>> is_in_list([2, 4, 14, 15], 1) 
False 
>>> is_in_list([2, 4, 14, 15], 13) 
False 

Metoda ta zmniejsza zużycie pamięci znacząco, ale - compared to a dict or set - wyszukiwanie zajmuje O (log n) zamiast czasu O (1), a wstawienie zajmuje O (n) zamiast O (1).