filtrage de la compréhension de liste - "le piège set ()"

Question

Raisonnablement une opération commune est de filtrer une list basé sur un autre list. Les gens à trouver rapidement que cela:

[x for x in list_1 if x in list_2]

est lente pour les grandes entrées - il est O(n*m). Beurk. Comment pouvons-nous accélérer le processus? Utiliser un set pour effectuer le filtrage des recherches O(1):

s = set(list_2)
[x for x in list_1 if x in s]

Cela donne ensemble de nice O(n) le comportement. J'ai cependant souvent voir même vétéran des codeurs de tomber dans Le Piège™:

[x for x in list_1 if x in set(list_2)]

Ack! C'est encore O(n*m) depuis le python s'appuie set(list_2) tous les temps, et pas seulement une fois.

---

Je pensais que c'était la fin de l'histoire - python ne peut pas optimiser pour seulement de construire la set une fois. Juste être conscient du piège. Dois vivre avec elle. Hmm.

#python 3.3.2+
list_2 = list(range(20)) #small for demonstration purposes
s = set(list_2)
list_1 = list(range(100000))
def f():
    return [x for x in list_1 if x in s]
def g():
    return [x for x in list_1 if x in set(list_2)]
def h():
    return [x for x in list_1 if x in {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}]

%timeit f()
100 loops, best of 3: 7.31 ms per loop

%timeit g()
10 loops, best of 3: 77.4 ms per loop

%timeit h()
100 loops, best of 3: 6.66 ms per loop

Hein, python (3.3) peut optimiser loin un ensemble de littéraux. C'est même plus rapide que l' f() dans ce cas, sans doute parce qu'il arrive à remplacer un LOAD_GLOBAL avec un LOAD_FAST.

#python 2.7.5+
%timeit h()
10 loops, best of 3: 72.5 ms per loop

Python 2 notamment ne pas faire cette optimisation. J'ai essayé d'enquêter sur ce python3 est en train de faire, mais malheureusement, dis.dis ne peut pas sonder les entrailles de la compréhension des expressions. En gros tout intéressant se transforme en MAKE_FUNCTION.

Alors maintenant, je me demande - pourquoi python 3.x optimiser loin l'ensemble littérale construire seulement une fois, mais pas set(list_2)?

Answer 1

Afin d’optimiser set(list_2) , l’interprète doit prouver que list_2 (et tous ses éléments) ne change pas entre les itérations. C'est un problème difficile dans le cas général et cela ne me surprendrait pas si l'interprète ne tente même pas de le résoudre.

D'autre part, un littéral d'ensemble ne peut pas changer sa valeur entre les itérations, donc l'optimisation est connue pour être sûre.

Answer 2

De Quoi de neuf dans Python 3.2 :

L’optimiseur de judas de Python reconnaît désormais les motifs tels que x in {1, 2, 3} comme un test d’appartenance à un ensemble de constantes. L'optimiseur convertit l'ensemble en tant que frozenset et stocke la constante pré-construite.

Answer 3

Alors maintenant, je me demande - pourquoi python 3.x optimiser loin le jeu littéral de construire seulement une fois, mais pas ensemble(fine list_2)?

Personne n'a mentionné cette question encore: comment savez-vous set([1,2,3]) et {1, 2, 3} sont la même chose?

>>> import random
>>> def set(arg):
...     return [random.choice(range(5))]
... 
>>> list1 = list(range(5))
>>> [x for x in list1 if x in set(list1)]
[0, 4]
>>> [x for x in list1 if x in set(list1)]
[0]

Vous ne pouvez pas l'ombre d'un littéral; vous pouvez l'ombre set. Donc, avant de vous pouvez envisager de levage, vous avez besoin de savoir non seulement qu' list1 n'est pas affecté, vous devez être sûr qu' set est ce que vous pensez qu'elle est. Parfois, vous pouvez le faire, soit dans des conditions restrictives au moment de la compilation ou de façon plus pratique au moment de l'exécution, mais il est certainement pas négligeable.

C'est marrant: souvent, quand la suggestion de faire des optimisations comme cela vient, un refoulement est que comme ils sont sympa, il est plus difficile de raisonner sur ce que Python performance va ressembler, même de manière algorithmique. Votre question fournit la preuve de cette objection.

Answer 4

Trop long pour un commentaire

Cela ne parle pas à l'optimisation de détails ou v2 vs v3 différences. Mais quand je rencontre ce dans certaines situations, je trouve de faire un gestionnaire de contexte de l'objet de données est utile:

class context_set(set):
    def __enter__(self):
        return self
    def __exit__(self, *args):
        pass

def context_version():
    with context_set(list_2) as s:
        return [x for x in list_1 if x in s]

À l'aide de ce que je vois:

In [180]: %timeit context_version()
100 loops, best of 3: 17.8 ms per loop

et, dans certains cas, il offre une belle bouche-trou entre la création de l'objet avant la compréhension vs création dans la compréhension, et permet de personnalisé le démontage de code si vous le souhaitez.

Plus version générique peut être faite à l'aide de contextlib.contextmanager. Voici un quick-and-dirty version de ce que je veux dire.

def context(some_type):
    from contextlib import contextmanager
    generator_apply_type = lambda x: (some_type(y) for y in (x,))
    return contextmanager(generator_apply_type)

Ensuite, on peut faire:

with context(set)(list_2) as s:
    # ...

ou tout aussi facilement

with context(tuple)(list_2) as t:
    # ...

Answer 5

La raison fondamentale en est qu'un littéral vraiment ne peut pas changer, alors que si c'est une expression comme set(list_2), il est possible que l'évaluation de l'expression de la cible ou de l'objet iterable la compréhension pourrait changer la valeur de set(list_2). Par exemple, si vous avez

[f(x) for x in list_1 if x in set(list_2)]

Il est possible qu' f modifie list_2.

Même pour un simple [x for x in blah ...] expression, il est théoriquement possible que l' __iter__ méthode de blah pourrait modifier list_2.

J'imagine qu'il est possible d'optimisations, mais le comportement de l'actuelle garde les choses simples. Si vous commencez à ajouter des optimisations pour des choses comme "il n'est évaluée une seule fois si l'expression de la cible est un seul nu nom et l'itérable est un builtin liste ou dict..." vous faites, il est beaucoup plus compliqué à comprendre ce qui se passe dans une situation donnée.