Comment diviser une liste en fonction d'une condition ?

Question

Quelle est la meilleure façon, à la fois esthétiquement et du point de vue des performances, de diviser une liste d'éléments en plusieurs listes sur la base d'une condition ? L'équivalent de :

good = [x for x in mylist if x in goodvals]
bad  = [x for x in mylist if x not in goodvals]

Existe-t-il une manière plus élégante de procéder ?

Voici le cas d'utilisation réel, pour mieux expliquer ce que j'essaie de faire :

# files looks like: [ ('file1.jpg', 33L, '.jpg'), ('file2.avi', 999L, '.avi'), ... ]
IMAGE_TYPES = ('.jpg','.jpeg','.gif','.bmp','.png')
images = [f for f in files if f[2].lower() in IMAGE_TYPES]
anims  = [f for f in files if f[2].lower() not in IMAGE_TYPES]

Answer 1

Je pense qu'une généralisation de la division d'un itérable en fonction de N conditions est pratique.

from collections import OrderedDict
def partition(iterable,*conditions):
    '''Returns a list with the elements that satisfy each of condition.
       Conditions are assumed to be exclusive'''
    d= OrderedDict((i,list())for i in range(len(conditions)))        
    for e in iterable:
        for i,condition in enumerate(conditions):
            if condition(e):
                d[i].append(e)
                break                    
    return d.values()

Par exemple :

ints,floats,other = partition([2, 3.14, 1, 1.69, [], None],
                              lambda x: isinstance(x, int), 
                              lambda x: isinstance(x, float),
                              lambda x: True)

print " ints: {}\n floats:{}\n other:{}".format(ints,floats,other)

 ints: [2, 1]
 floats:[3.14, 1.69]
 other:[[], None]

Si l'élément peut satisfaire à plusieurs conditions, supprimer la rupture.

Answer 2

Si cela ne vous dérange pas d'utiliser une bibliothèque externe, il y en a deux que je connais qui implémentent nativement cette opération :

>>> files = [ ('file1.jpg', 33, '.jpg'), ('file2.avi', 999, '.avi')]
>>> IMAGE_TYPES = ('.jpg','.jpeg','.gif','.bmp','.png')

• iteration_utilities.partition :

  >>> from iteration_utilities import partition
  >>> notimages, images = partition(files, lambda x: x[2].lower() in IMAGE_TYPES)
  >>> notimages
  [('file2.avi', 999, '.avi')]
  >>> images
  [('file1.jpg', 33, '.jpg')]

• more_itertools.partition

  >>> from more_itertools import partition
  >>> notimages, images = partition(lambda x: x[2].lower() in IMAGE_TYPES, files)
  >>> list(notimages)  # returns a generator so you need to explicitly convert to list.
  [('file2.avi', 999, '.avi')]
  >>> list(images)
  [('file1.jpg', 33, '.jpg')]

Answer 3

Inspiré par l'article de @gnibbler excellente (mais laconique !) réponse nous pouvons appliquer cette approche à la cartographie de plusieurs partitions :

from collections import defaultdict

def splitter(l, mapper):
    """Split an iterable into multiple partitions generated by a callable mapper."""

    results = defaultdict(list)

    for x in l:
        results[mapper(x)] += [x]

    return results

Entonces splitter peut alors être utilisé comme suit :

>>> l = [1, 2, 3, 4, 2, 3, 4, 5, 6, 4, 3, 2, 3]
>>> split = splitter(l, lambda x: x % 2 == 0)  # partition l into odds and evens
>>> split.items()
>>> [(False, [1, 3, 3, 5, 3, 3]), (True, [2, 4, 2, 4, 6, 4, 2])]

Cela fonctionne pour plus de deux partitions avec un mappage plus compliqué (et aussi pour les itérateurs) :

>>> import math
>>> l = xrange(1, 23)
>>> split = splitter(l, lambda x: int(math.log10(x) * 5))
>>> split.items()
[(0, [1]),
 (1, [2]),
 (2, [3]),
 (3, [4, 5, 6]),
 (4, [7, 8, 9]),
 (5, [10, 11, 12, 13, 14, 15]),
 (6, [16, 17, 18, 19, 20, 21, 22])]

Ou l'utilisation d'un dictionnaire pour cartographier :

>>> map = {'A': 1, 'X': 2, 'B': 3, 'Y': 1, 'C': 2, 'Z': 3}
>>> l = ['A', 'B', 'C', 'C', 'X', 'Y', 'Z', 'A', 'Z']
>>> split = splitter(l, map.get)
>>> split.items()
(1, ['A', 'Y', 'A']), (2, ['C', 'C', 'X']), (3, ['B', 'Z', 'Z'])]

Answer 4

Encore une autre solution à ce problème. J'avais besoin d'une solution aussi rapide que possible. Cela signifie une seule itération sur la liste et de préférence O(1) pour l'ajout de données à l'une des listes résultantes. Cette solution est très similaire à celle fournie par sastanine sauf qu'il est beaucoup plus court :

from collections import deque

def split(iterable, function):
    dq_true = deque()
    dq_false = deque()

    # deque - the fastest way to consume an iterator and append items
    deque((
      (dq_true if function(item) else dq_false).append(item) for item in iterable
    ), maxlen=0)

    return dq_true, dq_false

Vous pouvez ensuite utiliser la fonction de la manière suivante :

lower, higher = split([0,1,2,3,4,5,6,7,8,9], lambda x: x < 5)

selected, other = split([0,1,2,3,4,5,6,7,8,9], lambda x: x in {0,4,9})

Si vous n'êtes pas d'accord avec le résultat deque vous pouvez facilement le convertir en list , set ou ce que vous voulez (par exemple list(lower) ). La conversion est beaucoup plus rapide que la construction directe des listes.

Cette méthode permet de conserver l'ordre des éléments, ainsi que les éventuels doublons.

Answer 5

Par exemple, diviser la liste par pair et impair

arr = range(20)
even, odd = reduce(lambda res, next: res[next % 2].append(next) or res, arr, ([], []))

Ou en général :

def split(predicate, iterable):
    return reduce(lambda res, e: res[predicate(e)].append(e) or res, iterable, ([], []))

Avantages :

• Le chemin le plus court possible
• Le prédicat ne s'applique qu'une seule fois pour chaque élément

Inconvénients

• Nécessite une connaissance du paradigme de la programmation fonctionnelle.