Aby odpowiedzieć na pytanie o dict vs list trzeba by dać dokładnie informacje o liczbie elementów, liczba brakujących elementów etc, więc tha możemy oszacować dokładnie zużycie pamięci struktury dwóch danych i spróbuj przewidzieć i/lub sprawdzić swoją wydajność.
Na ogół dict z N par klucz-wartość wymaga nieco więcej pamięci niż list z N wartości:
dict musi śledzić klawiszydict jest nie więcej niż 2/3 pełne. Gdy tak się stanie, przydzielona pamięć jest podwojona (wymagane jest to, aby O (1) amortyzował operacje czasowe na dict).
Jednak istnieje alternatywa do tych struktur danych, które powinny zapewnić bardzo dobrą wydajność: blist. Pakiet blist zapewnia interfejs, który odpowiada interfejsowi list, ale jest zaimplementowany przy użyciu B-drzew. Potrafi wydajnie obsługiwać rzadkie listy. Większość operacji ma czas O(1) lub O(log n), więc są dość wydajne.
Na przykład można najpierw utworzyć rzadki blist robi:
from blist import blist
seq = blist([None])
seq *= 2**30 # create a 2**30 element blist. Instantaneous!
A potem można ustawić tylko indeksy, które mają wartość:
for i, value in zip(indices, values):
seq[i] = value
Pełna dokumentacja jest here.
Należy zauważyć, że blist też inne wydajne operacji, takich jak:
- Połączenie dwóch
blist e się O(log n) czas
- Biorąc
[i:j] segment zajmuje O(log n) czasu
- Wkładanie elementu w danej indeksu,
O(log n) operacji
- Popping element (z każdej pozycji) zajmuje
O(log n) operacji
Skoro dał kilka numerów, oto jak to porównać do dict s:
>>> from blist import blist
>>> b = blist([None])
>>> b *= 5000
>>> for i in range(100):b[i] = i
...
>>> b.__sizeof__()
2660
>>> d = dict()
>>> for i in range(100):d[i] = i
...
>>> d.__sizeof__()
6216
>>> b = blist([None])
>>> b *= 750
>>> for i in range(30):b[i] = i
...
>>> b.__sizeof__()
1580
>>> d = dict()
>>> for i in range(30):d[i] = i
...
>>> d.__sizeof__()
1608
W obu przypadkach blist zajmuje mniej pamięci (w pierwszym przypadku potrzebny 1/3 pamięci równoważnego dict). Należy pamiętać, że pamięć podjęta przez blist zależy również od tego, czy indeksy są sąsiadujące (sąsiadujące jest lepsze). Jednak nawet przy użyciu indeksów losowych:
>>> b = blist([None])
>>> b *= 5000
>>> import random
>>> for i in range(100):b[random.randint(0, 4999)] = i
...
>>> b.__sizeof__()
2916
To wciąż znacznie lepsze niż dict.
Nawet lookup czasy są lepsze:
In [1]: from blist import blist
...: import random
...:
In [2]: b = blist([None])
In [3]: b *= 5000
In [4]: for i in range(100):b[random.randint(0, 4999)] = i
In [5]: %timeit b[0]
10000000 loops, best of 3: 50.7 ns per loop
In [6]: d = dict()
In [7]: for i in range(100):d[random.randint(0, 4999)] = i
In [10]: %timeit d[1024] # 1024 is an existing key in this dictionary
10000000 loops, best of 3: 70.7 ns per loop
In [11]: %timeit b[1024]
10000000 loops, best of 3: 50.7 ns per loop
Uwaga że list trwa około 47 ns do wyszukiwania indeksu na moim komputerze, więc blist jest naprawdę bardzo blisko list pod względem wydajności przeglądowej na małych list jak co masz.
O ile nie jest to kod niezwykle wrażliwy na wydajność, nie martwiłbym się. Użyj "dyktatu" - jest semantycznie dużo bliżej tego, co próbujesz osiągnąć. – sapi