Aplatissement d’une liste peu profonde en Python

Question

Est-il un moyen simple pour aplatir une liste de iterables avec une compréhension de liste, ou, à défaut, que feriez-vous tous, la meilleure façon de les aplatir un peu la liste de ce genre, l'équilibrage de la performance et de la lisibilité?

J'ai essayé de les aplatir cette liste avec une liste imbriquée de compréhension, comme ceci:

[image for image in menuitem for menuitem in list_of_menuitems]

Mais j'ai des ennuis de l' NameError variété, parce que l' name 'menuitem' is not defined. Après googler et autour de la recherche sur Stack Overflow, j'ai obtenu les résultats désirés avec un reduce déclaration:

reduce(list.__add__, map(lambda x: list(x), list_of_menuitems))

Mais cette méthode est assez illisible parce que j'ai besoin qu' list(x) appeler de là, parce que x est un Django QuerySet objet.

Conclusion:

Merci à tous ceux qui ont contribué à cette question. Voici un résumé de ce que j'ai appris. Je suis aussi ce qui en fait un wiki de la communauté dans le cas où d'autres veulent ajouter ou corriger ces observations.

Mon original de réduire déclaration est redondant et c'est mieux écrit de cette manière:

>>> reduce(list.__add__, (list(mi) for mi in list_of_menuitems))

C'est la syntaxe correcte pour une liste imbriquée compréhension (Brillant résumé dF!):

>>> [image for mi in list_of_menuitems for image in mi]

Mais aucune de ces méthodes sont aussi efficaces que les itertools.chain:

>>> from itertools import chain
>>> list(chain(*list_of_menuitems))

Et comme @cdleary notes, c'est probablement mieux de style à éviter * l'opérateur de la magie en utilisant chain.from_iterable comme:

>>> chain = itertools.chain.from_iterable([[1,2],[3],[5,89],[],[6]])
>>> print(list(chain))
>>> [1, 2, 3, 5, 89, 6]

Answer 1

Si vous êtes simplement à la recherche d'itérer sur une version aplatie de la structure de données et n'ont pas besoin d'un indexables séquence, pensez à itertools.de la chaîne et de l'entreprise.

>>> list_of_menuitems = [['image00', 'image01'], ['image10'], []]
>>> import itertools
>>> chain = itertools.chain(*list_of_menuitems)
>>> print(list(chain))
['image00', 'image01', 'image10']

Il va travailler sur tout ce qui est itératif, qui devrait inclure Django itérable QuerySets, il semble que vous utilisez dans la question.

Edit: C'est sans doute aussi bon que un à réduire toute façon, parce que réduire aura la même surcharge de copier les éléments dans la liste qui est en cours d'extension. chain n'engagera cette (même) les frais généraux si vous exécutez list(chain) à la fin.

Méta-Edit: en Fait, c'est moins de frais généraux que la question de la solution proposée, parce que vous jetez la temporaire de listes que vous créez lorsque vous étendez l'original avec le temporaire.

Edit: Comme J. F. Sebastian, dit - itertools.chain.from_iterable évite le déballage et vous devriez l'utiliser pour éviter * de la magie, mais la timeit app montre négligeable différence de performances.

Answer 2

Vous l’avez presque ! Le faire imbriqué la liste silencieuse est de mettre le des déclarations dans le même ordre comme ils iraient regular imbriqués déclarations.

Ainsi, cela

correspond à

Si vous voulez

Answer 3

@S. Lott: Vous m'a inspiré à écrire un timeit app.

J'ai pensé qu'il serait également varier en fonction du nombre de partitions (nombre de itérateurs de la liste des conteneurs) -- votre commentaire n'a pas mentionné le nombre de partitions qu'il y avait des trente articles. Cette parcelle est mise à plat d'un milliers d'articles dans chaque course, avec le nombre de variables de partitions. Les articles sont répartis de façon égale entre les partitions.

Code (Python 2.6):

#!/usr/bin/env python2.6

"""Usage: %prog item_count"""

from __future__ import print_function

import collections
import itertools
import operator
from timeit import Timer
import sys

import matplotlib.pyplot as pyplot

def itertools_flatten(iter_lst):
    return list(itertools.chain(*iter_lst))

def itertools_iterable_flatten(iter_iter):
    return list(itertools.chain.from_iterable(iter_iter))

def reduce_flatten(iter_lst):
    return reduce(operator.add, map(list, iter_lst))

def reduce_lambda_flatten(iter_lst):
    return reduce(operator.add, map(lambda x: list(x), [i for i in iter_lst]))

def comprehension_flatten(iter_lst):
    return list(item for iter_ in iter_lst for item in iter_)

METHODS = ['itertools', 'itertools_iterable', 'reduce', 'reduce_lambda',
           'comprehension']

def _time_test_assert(iter_lst):
    """Make sure all methods produce an equivalent value.
    :raise AssertionError: On any non-equivalent value."""
    callables = (globals()[method + '_flatten'] for method in METHODS)
    results = [callable(iter_lst) for callable in callables]
    if not all(result == results[0] for result in results[1:]):
        raise AssertionError

def time_test(partition_count, item_count_per_partition, test_count=10000):
    """Run flatten methods on a list of :param:`partition_count` iterables.
    Normalize results over :param:`test_count` runs.
    :return: Mapping from method to (normalized) microseconds per pass.
    """
    iter_lst = [[dict()] * item_count_per_partition] * partition_count
    print('Partition count:    ', partition_count)
    print('Items per partition:', item_count_per_partition)
    _time_test_assert(iter_lst)
    test_str = 'flatten(%r)' % iter_lst
    result_by_method = {}
    for method in METHODS:
        setup_str = 'from test import %s_flatten as flatten' % method
        t = Timer(test_str, setup_str)
        per_pass = test_count * t.timeit(number=test_count) / test_count
        print('%20s: %.2f usec/pass' % (method, per_pass))
        result_by_method[method] = per_pass
    return result_by_method

if __name__ == '__main__':
    if len(sys.argv) != 2:
        raise ValueError('Need a number of items to flatten')
    item_count = int(sys.argv[1])
    partition_counts = []
    pass_times_by_method = collections.defaultdict(list)
    for partition_count in xrange(1, item_count):
        if item_count % partition_count != 0:
            continue
        items_per_partition = item_count / partition_count
        result_by_method = time_test(partition_count, items_per_partition)
        partition_counts.append(partition_count)
        for method, result in result_by_method.iteritems():
            pass_times_by_method[method].append(result)
    for method, pass_times in pass_times_by_method.iteritems():
        pyplot.plot(partition_counts, pass_times, label=method)
    pyplot.legend()
    pyplot.title('Flattening Comparison for %d Items' % item_count)
    pyplot.xlabel('Number of Partitions')
    pyplot.ylabel('Microseconds')
    pyplot.show()

Edit: a Décidé de rendre wiki de la communauté.

Remarque: METHODS devrait probablement être cumulé avec un décorateur, mais je me dis qu'il serait plus facile pour les gens à lire de cette façon.

Answer 4

somme (liste de listes, []) aurait l’aplatir

Answer 5

Cette solution fonctionne pour les profondeurs imbrication arbitraires - pas seulement la profondeur de la « liste des listes » que certains (tous ?) des autres solutions sont limitées à :

C’est la récursivité qui permet pour la nidification de profondeur arbitraire - jusqu'à ce que vous frappez la profondeur de récursivité maximale, bien sûr...