Verflachen einer flachen Liste in Python

Question

Gibt es eine einfache Möglichkeit, eine Liste von iterables mit einer Liste Verständnis zu glätten, oder in Ermangelung dessen, was würden Sie alle betrachten, um den besten Weg zu glätten eine flache Liste wie diese, Ausgleich Leistung und Lesbarkeit?

Ich habe versucht, eine solche Liste mit einem verschachtelten Listenverständnis zu glätten, etwa so:

[image for image in menuitem for menuitem in list_of_menuitems]

Aber ich gerate in Schwierigkeiten durch die NameError Vielfalt dort, weil die name 'menuitem' is not defined . Nachdem ich gegoogelt und mich auf Stack Overflow umgesehen hatte, erhielt ich die gewünschten Ergebnisse mit einem reduce Erklärung:

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

Aber diese Methode ist ziemlich unleserlich, denn ich brauche die list(x) Aufruf dort, weil x ein Django ist QuerySet Objekt.

Schlussfolgerung :

Vielen Dank an alle, die zu dieser Frage beigetragen haben. Hier ist eine Zusammenfassung von dem, was ich gelernt habe. Ich mache dies auch zu einem Gemeinschafts-Wiki, falls andere diese Beobachtungen ergänzen oder korrigieren möchten.

Meine ursprüngliche Aussage zur Reduzierung ist redundant und sollte besser so formuliert werden:

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

Dies ist die korrekte Syntax für ein verschachteltes Listenverständnis (Brillante Zusammenfassung dF !):

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

Aber keine dieser Methoden ist so effizient wie die Verwendung von itertools.chain :

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

Und wie @cdleary bemerkt, ist es wahrscheinlich besser, die Magie des Operators * zu vermeiden, indem man chain.from_iterable etwa so:

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

Answer 1

Wenn Sie nur über eine reduzierte Version der Datenstruktur iterieren wollen und keine indizierbare Sequenz benötigen, sollten Sie itertools.chain und Unternehmen .

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

Es funktioniert mit allem, was iterabel ist, was auch Djangos iterable einschließen sollte QuerySet s, die Sie anscheinend in Ihrer Frage verwenden.

Edita: Dies ist wahrscheinlich genauso gut wie ein reduce, weil reduce den gleichen Overhead hat, der beim Kopieren der Elemente in die Liste entsteht, die erweitert wird. chain entsteht dieser (gleiche) Overhead nur, wenn Sie list(chain) am Ende.

Meta-Edit: Eigentlich ist es weniger Aufwand als die in der Frage vorgeschlagene Lösung, weil Sie die temporären Listen, die Sie erstellen, wegwerfen, wenn Sie das Original mit dem temporären erweitern.

Edita: Als J.F. Sebastian sagt itertools.chain.from_iterable vermeidet das Auspacken und Sie sollten das nutzen, um zu vermeiden * Magie, sondern die timeit-App zeigt einen vernachlässigbaren Leistungsunterschied.

Answer 2

Sie haben es fast geschafft! Die verschachtelte Listenauffassungen zu machen ist es, die for Anweisungen in der gleichen Reihenfolge, wie sie in normalen verschachtelten for Erklärungen.

Daher ist diese

for inner_list in outer_list:
    for item in inner_list:
        ...

entspricht

[... for inner_list in outer_list for item in inner_list]

Sie wollen also

[image for menuitem in list_of_menuitems for image in menuitem]

Answer 3

@S.Lott : Du hast mich dazu inspiriert, eine timeit-App zu schreiben.

Ich dachte mir, dass es auch von der Anzahl der Partitionen (Anzahl der Iteratoren innerhalb der Containerliste) abhängen würde - in Ihrem Kommentar wurde nicht erwähnt, wie viele Partitionen es von den dreißig Elementen gab. In diesem Diagramm werden in jedem Durchlauf tausend Elemente mit einer unterschiedlichen Anzahl von Partitionen abgeflacht. Die Elemente sind gleichmäßig auf die Partitionen verteilt.

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()

Edita: Beschlossen, es zu einem Gemeinschafts-Wiki zu machen.

Nota: METHODS sollte wahrscheinlich mit einem Dekorator akkumuliert werden, aber ich denke, so ist es für die Leute einfacher zu lesen.

Answer 4

sum(list_of_lists, []) würde es platt machen.

l = [['image00', 'image01'], ['image10'], []]
print sum(l,[]) # prints ['image00', 'image01', 'image10']

Answer 5

Diese Lösung funktioniert für beliebige Verschachtelungstiefen - nicht nur für die "Liste von Listen"-Tiefe, auf die einige (alle?) der anderen Lösungen beschränkt sind:

def flatten(x):
    result = []
    for el in x:
        if hasattr(el, "__iter__") and not isinstance(el, basestring):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

Es ist die Rekursion, die eine beliebige Verschachtelungstiefe ermöglicht - bis man natürlich die maximale Rekursionstiefe erreicht...