Ensembles et tableaux en Python

Question

Je dois stocker une grande liste de nombres en mémoire. Je devrai ensuite vérifier l'appartenance à un groupe. Les tableaux sont meilleurs que les listes pour l'efficacité de la mémoire. Les ensembles sont meilleurs que les listes pour la vérification de l'appartenance. J'ai besoin des deux ! Mes questions sont donc les suivantes :

1) Dans quelle mesure les tableaux sont-ils plus efficaces en termes de mémoire que les ensembles ? (Pour l'inverse, voir mes résultats ci-dessous). 2) Existe-t-il une structure de données qui offre un meilleur équilibre entre les ensembles et les tableaux ? Quelque chose comme un ensemble avec un type entier signé ? Ou une construction numpy ?

J'ai vérifié la différence de temps d'adhésion avec le script ci-dessous. (Je sais que timeit est meilleur, mais la variance est suffisamment faible pour que time soit correct) :

import array
import time 

class TimerContext:
    def __enter__(self):
        self.t0 = time.time()
    def __exit__(self, *args, **kwargs):
        print(time.time()-self.t0)

SIZE = 1000000

l = list([i for i in range(SIZE)])
a = array.array('I', l)
s = set(l)

print(type(l))
print(type(a))
print(type(s))

with TimerContext():
    x = 99999 in l
with TimerContext():
    x = 99999 in a
with TimerContext():
    x = 99999 in s

Résultats :

<class 'list'>
<class 'array.array'>
<class 'set'>
0.0012176036834716797
0.0024595260620117188
1.430511474609375e-06

Les ensembles sont donc BEAUCOUP plus rapides pour la vérification de l'appartenance (veuillez noter la notation scientifique). Donc, si leur empreinte mémoire n'est pas si différente de celle d'un tableau, je préférerai utiliser un ensemble. Mais je ne sais pas comment vérifier l'empreinte mémoire.

Je dois également ajouter qu'il y a beaucoup de questions comparant les ensembles et les listes. Mais je n'ai pas vu de bonnes réponses comparant les tableaux et les ensembles.

Answer 1

Si c'est possible dans votre cas, bisect se rapproche de la performance de l set pour les contrôles d'appartenance (à la fois avec une liste et un tableau). Voir les résultats ci-dessous

import array
from bisect import bisect
import sys
import time

class TimerContext:
    def __enter__(self):
        self.t0 = time.time()

    def __exit__(self, *args, **kwargs):
        print(time.time() - self.t0)

def get_size_in_megabytes(iterable):
    return round(sys.getsizeof(iterable) / (1024 ** 2), 2)

SIZE = 1000000

l = list([i for i in range(SIZE)])
a = array.array("I", l)
s = set(l)

print(type(l), get_size_in_megabytes(l))
print(type(a), get_size_in_megabytes(a))
print(type(s), get_size_in_megabytes(s))

with TimerContext():
    x = 99999 in l
with TimerContext():
    x = 99999 in a
with TimerContext():
    x = 99999 in s

print("list bisect")
with TimerContext():
    bisect(l, 99999)

print("array bisect")
with TimerContext():
    bisect(a, 99999)

Résultats :

<class 'list'> 8.58
<class 'array.array'> 3.81
<class 'set'> 32.0
0.0024390220642089844
0.0053005218505859375
3.814697265625e-06
list bisect
9.298324584960938e-06
array bisect
6.198883056640625e-06

Crédits pour sys.getsizeof ussage à @CristiFati.