Reduzieren einer flachen Liste in Python [duplicate]

Gibt es eine einfache Möglichkeit, eine Liste von Iterables mit einem Listenverständnis zu glätten, oder was würden Sie alle als den besten Weg betrachten, um eine flache Liste wie diese zu glätten und Leistung und Lesbarkeit in Einklang zu bringen?

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

[image for image in menuitem for menuitem in list_of_menuitems]

Aber ich bekomme Ärger von der NameError Abwechslung da, denn die name 'menuitem' is not defined. Nachdem ich gegoogelt und mich auf Stack Overflow umgesehen hatte, bekam ich die gewünschten Ergebnisse mit a reduce Aussage:

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

Aber diese Methode ist ziemlich unlesbar, weil ich das brauche list(x) rufen Sie dort auf, weil x ein Django ist QuerySet Objekt.

Fazit:

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

Meine ursprüngliche Anweisung zum Reduzieren ist überflüssig und wird besser so geschrieben:

>>> 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 itertools.chain:

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

Und wie @cdleary anmerkt, ist es wahrscheinlich besser, *-Operatormagie durch Verwendung zu vermeiden chain.from_iterable so:

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

Wenn Sie nur über eine abgeflachte Version der Datenstruktur iterieren möchten und keine indizierbare Sequenz benötigen, sollten Sie dies in Betracht ziehen 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 iterierbar ist, einschließlich Djangos iterable QuerySets, die Sie anscheinend in der Frage verwenden.

Bearbeiten: Dies ist wahrscheinlich sowieso so gut wie ein Reduzieren, da Reduzieren den gleichen Overhead haben wird, wenn die Elemente in die Liste kopiert werden, die erweitert wird. chain wird nur diesen (gleichen) Overhead verursachen, wenn Sie laufen list(chain) Am Ende.

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

Bearbeiten: Wie JF Sebastian sagt itertools.chain.from_iterable vermeidet das Auspacken und das sollten Sie vermeiden * Magic, aber die Timeit-App zeigt einen vernachlässigbaren Leistungsunterschied.

Sie haben es fast! Das Möglichkeit, verschachtelte Listenverständnisse zu machen ist die zu setzen for Anweisungen in der gleichen Reihenfolge, in der sie regulär verschachtelt werden würden for Aussagen.

Also das

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

entspricht

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

Also du möchtest

[image for menuitem in list_of_menuitems for image in menuitem]

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

Ich dachte, es würde auch basierend auf der Anzahl der Partitionen (Anzahl der Iteratoren innerhalb der Containerliste) variieren – Ihr Kommentar erwähnte nicht, wie viele Partitionen es von den dreißig Elementen gab. Dieser Plot flacht in jedem Durchlauf tausend Elemente mit unterschiedlicher Anzahl von Partitionen ab. Die Artikel werden 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()

Bearbeiten: Beschlossen, daraus ein Community-Wiki zu machen.

Notiz: METHODS sollte wahrscheinlich mit einem Dekorateur gesammelt werden, aber ich denke, es wäre einfacher für die Leute, auf diese Weise zu lesen.

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

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

Diese Lösung funktioniert für beliebige Verschachtelungstiefen – nicht nur für die Tiefe der “Liste der Listen”, 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 Tiefenverschachtelung ermöglicht – natürlich bis Sie die maximale Rekursionstiefe erreichen …

Verwenden Sie in Python 2.6 chain.from_iterable():

>>> from itertools import chain
>>> list(chain.from_iterable(mi.image_set.all() for mi in h.get_image_menu()))

Es vermeidet die Erstellung einer Zwischenliste.

Leistungsergebnisse. Überarbeitet.

import itertools
def itertools_flatten( aList ):
    return list( itertools.chain(*aList) )

from operator import add
def reduce_flatten1( aList ):
    return reduce(add, map(lambda x: list(x), [mi for mi in aList]))

def reduce_flatten2( aList ):
    return reduce(list.__add__, map(list, aList))

def comprehension_flatten( aList ):
    return list(y for x in aList for y in x)

Ich habe eine zweistufige Liste mit 30 Elementen 1000 Mal reduziert

itertools_flatten     0.00554
comprehension_flatten 0.00815
reduce_flatten2       0.01103
reduce_flatten1       0.01404

Reduzieren ist immer eine schlechte Wahl.