Flattening a shallow list in Python [duplicate]

Существует ли простой способ сгладить список итераций с пониманием списка, или, если это не удастся, какой, по вашему мнению, лучший способ сгладить такой неглубокий список, сбалансировав производительность и читабельность?

Я попытался выровнять такой список с помощью понимания вложенного списка, вот так:

[image for image in menuitem for menuitem in list_of_menuitems]

Но у меня возникают проблемы с NameError разнообразием там, потому что name 'menuitem' is not defined. Погуглив и покопавшись в Stack Overflow, я получил желаемые результаты с помощью reduce инструкции:

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

Но этот метод довольно нечитаемый, потому что мне нужен этот list(x) вызов там, потому что x - это объект Django QuerySet.

Заключение:

Спасибо всем, кто внес свой вклад в этот вопрос. Вот краткое изложение того, что я узнал. Я также делаю это вики сообщества на случай, если другие захотят дополнить или исправить эти наблюдения.

Мой оригинальный оператор reduce избыточен и лучше написан таким образом:

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

Это правильный синтаксис для понимания вложенного списка (блестящее резюме dF!):

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

Но ни один из этих методов не так эффективен, как использование itertools.chain:

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

И, как отмечает @cdleary, вероятно, лучше избегать * магии оператора, используя chain.from_iterable вот так:

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

Если вы просто хотите выполнить итерацию по упрощенной версии структуры данных и вам не нужна индексируемая последовательность, рассмотрите itertools.chain и company.

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

Это будет работать со всем, что можно повторить, что должно включать iterable от Django QuerySets, который, похоже, вы используете в вопросе.

Редактировать: В любом случае, это, вероятно, так же хорошо, как и reduce , потому что reduce будет иметь те же накладные расходы на копирование элементов в расширяемый список. chain повлечет за собой такие же накладные расходы, только если вы запустите list(chain) в конце.

Мета-правка: На самом деле, это требует меньше накладных расходов, чем предлагаемое решение вопроса, потому что вы отбрасываете временные списки, которые создаете, когда расширяете оригинал временными.

Редактировать: Как говорит Дж. Ф. Себастьян, itertools.chain.from_iterable позволяет избежать распаковки, и вам следует использовать это, чтобы избежать * магии, но приложение timeit показывает незначительную разницу в производительности.

У вас почти получилось! Способ сделать понимание вложенного списка заключается в том, чтобы расположить for операторы в том же порядке, в каком они шли бы в обычных вложенных for операторах.

Таким образом, это

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

соответствует

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

Итак, вы хотите

[image for menuitem in list_of_menuitems for image in menuitem]

@S.Лотт: Вы вдохновили меня на написание приложения timeit.

Я полагал, что это также будет зависеть от количества разделов (количества итераторов в списке контейнеров) - в вашем комментарии не указано, сколько разделов было из тридцати элементов. На этом графике выравнивается тысяча элементов за каждый запуск с различным количеством разделов. Элементы равномерно распределены между разделами.

Код (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()

Правка: Решил сделать это вики сообщества.

Примечание: METHODS вероятно, его следует накапливать с помощью декоратора, но я полагаю, что людям будет легче читать таким образом.

sum(list_of_lists, []) приведет к его выравниванию.

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