Python: сгладить вложенные списки с индексами

Ответ 1

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

def flatten(l):
    stack = [enumerate(l)]
    path = [None]
    while stack:
        for path[-1], x in stack[-1]:
            if isinstance(x, list):
                stack.append(enumerate(x))
                path.append(None)
            else:
                yield x, tuple(path)
            break
        else:
            stack.pop()
            path.pop()

Я сохраняю текущие "активные" списки в стеке итераторов enumerate, а текущий путь указателя - в качестве другого стека. Затем в цикле while я всегда пытаюсь взять следующий элемент из текущего списка и обработать его соответствующим образом:

• Если следующий элемент - это список, то я нажимаю его итератор enumerate в стеке и освобождаю место для более глубокого индекса в стеке пути индекса.
• Если следующий элемент - это число, то я даю его вместе со своим путем.
• Если в текущем списке не было следующего элемента, я удаляю его (или, скорее, его итератор) и его индексное пятно из стеков.

Демо:

>>> L = [[[1, 2, 3], [4, 5]], [6], [7,[8,9]], 10]
>>> for entry in flatten(L):
        print(entry)

(1, (0, 0, 0))
(2, (0, 0, 1))
(3, (0, 0, 2))
(4, (0, 1, 0))
(5, (0, 1, 1))
(6, (1, 0))
(7, (2, 0))
(8, (2, 1, 0))
(9, (2, 1, 1))
(10, (3,))

Обратите внимание, что если вы обрабатываете записи "на лету", как это делает печать, вы можете просто указать путь в качестве списка, т.е. использовать yield x, path. Демо-ролик:

>>> for entry in flatten(L):
        print(entry)

(1, [0, 0, 0])
(2, [0, 0, 1])
(3, [0, 0, 2])
(4, [0, 1, 0])
(5, [0, 1, 1])
(6, [1, 0])
(7, [2, 0])
(8, [2, 1, 0])
(9, [2, 1, 1])
(10, [3])

Таким образом, итератору требуется только время O (n) для всей итерации, где n - общее количество объектов в структуре (оба списка и числа). Конечно, печать увеличивает сложность, так же как и создание кортежей. Но это тогда вне генератора и "ошибка" печати или что бы вы ни делали с каждым путем. Если вы, например, смотрите только длину пути, а не его содержимое, которое принимает O (1), то все это даже на самом деле является O (n).

Все, что сказал, опять же, я думаю, что ваше собственное решение в порядке. И явно проще, чем это. И, как я прокомментировал в @naomik ответ, я думаю, что ваше решение, не способное обрабатывать списки глубин около 1000 или более, не имеет значения. Во-первых, даже такого списка не нужно. Если это так, то это ошибка, которая должна быть исправлена. Если список также может быть широк, как в вашем случае, и сбалансирован, то даже с коэффициентом ветвления всего 2 вы исчерпали бы память на глубине менее 100, и вы не достигнете около 1000. Если список не может быть широким, тогда вложенные списки - неправильный выбор структуры данных, плюс вам не будет интересовать путь индекса в первую очередь. Если он может расширяться, но не работает, я бы сказал, что алгоритм создания следует улучшить (например, если он представляет отсортированное дерево, добавьте балансировку).

О моем решении снова: помимо его способности обрабатывать произвольно глубокие списки и его эффективность, я нахожу, что некоторые из его деталей интересны:

• Вы редко когда-либо видите объекты enumerate, которые где-то хранятся. Обычно они просто используются в циклах & Co непосредственно, например for i, x in enumerate(l):.
• Точка path[-1] готова и записана в нее с помощью for path[-1], x in ....
• Используя for -loop с немедленной ветвью break и else, чтобы выполнить итерацию по следующему одиночному значению, и дескриптор заканчивается изящно без try/except и без next и по умолчанию.
• Если вы выполняете yield x, path, т.е. не включаете каждый путь в кортеж, вам действительно нужно обработать его непосредственно во время итерации. Например, если вы делаете list(flatten(L)), вы получаете [(1, []), (2, []), (3, []), (4, []), (5, []), (6, []), (7, []), (8, []), (9, []), (10, [])]. То есть "все" указательные пути будут пустыми. Конечно, потому что на самом деле существует только один объект пути, который я обновляю и возвращаю снова и снова, и в конце концов его пуст. Это очень похоже на itertools.groupby, где, например, [list(g) for _, g in list(groupby('aaabbbb'))] дает вам [[], ['b']]. И это не плохо. Недавно я писал об этом.

Более короткая версия с одним стеком, содержащим как индексы, так и enumerate объекты поочередно:

def flatten(l):
    stack = [None, enumerate(l)]
    while stack:
        for stack[-2], x in stack[-1]:
            if isinstance(x, list):
                stack += None, enumerate(x)
            else:
                yield x, stack[::2]
            break
        else:
            del stack[-2:]

Ответ 2

Начиная с переменных прямой рекурсии и состояния со значениями по умолчанию,

def flatten (l, i = 0, path = (), acc = []):
  if not l:
    return acc
  else:
    first, *rest = l
    if isinstance (first, list):
      return flatten (first, 0, path + (i,), acc) + flatten (rest, i + 1, path, [])
    else:
      return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ])

print (flatten (L))
# [ (1, (0, 0, 0))
# , (2, (0, 0, 1))
# , (3, (0, 0, 2))
# , (4, (0, 1, 0))
# , (5, (0, 1, 1))
# , (6, (1, 0))
# , (7, (2, 0))
# , (8, (2, 1, 0))
# , (9, (2, 1, 1))
# , (10, (3,))
# ]

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

def identity (x):
  return x

# tail-recursive, but still not stack-safe, yet
def flatten (l, i = 0, path = (), acc = [], cont = identity):
  if not l:
    return cont (acc)
  else:
    first, *rest = l
    if isinstance (first, list):
      return flatten (first, 0, path + (i,), acc, lambda left:
        flatten (rest, i + 1, path, [], lambda right:
          cont (left + right)))
    else:
      return flatten (rest, i + 1, path, acc + [ (first, path + (i,)) ], cont)


print (flatten (L))
# [ (1, (0, 0, 0))
# , (2, (0, 0, 1))
# , (3, (0, 0, 2))
# , (4, (0, 1, 0))
# , (5, (0, 1, 1))
# , (6, (1, 0))
# , (7, (2, 0))
# , (8, (2, 1, 0))
# , (9, (2, 1, 1))
# , (10, (3,))
# ]

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

def identity (x):
  return x

def flatten (l):
  def loop (l, i = 0, path = (), acc = [], cont = identity):  
    if not l:
      return cont (acc)
    else:
      first, *rest = l
      if isinstance (first, list):
        return call (loop, first, 0, path + (i,), acc, lambda left:
          call (loop, rest, i + 1, path, [], lambda right:
            cont (left + right)))
      else:
        return call (loop, rest, i + 1, path, acc + [ (first, path + (i,)) ], cont)

  return loop (l) .run ()

class call:
  def __init__ (self, f, *xs):
    self.f = f
    self.xs = xs

  def run (self):
    acc = self
    while (isinstance (acc, call)):
      acc = acc.f (*acc.xs)
    return acc

print (flatten (L))
# [ (1, (0, 0, 0))
# , (2, (0, 0, 1))
# , (3, (0, 0, 2))
# , (4, (0, 1, 0))
# , (5, (0, 1, 1))
# , (6, (1, 0))
# , (7, (2, 0))
# , (8, (2, 1, 0))
# , (9, (2, 1, 1))
# , (10, (3,))
# ]

Почему это лучше? Объективно говоря, это более полная программа. Просто потому, что он кажется более сложным, это не значит, что он менее эффективен.

Код, предоставленный в вопросе, терпит неудачу, когда входной список вложен более чем на 996 уровней (в python 3.x)

depth = 1000
L = [1]
while (depth > 0):
  L = [L]
  depth = depth - 1

for x in flatten (L):
  print (x)

# Bug in the question code:
# the first value in the tuple is not completely flattened
# ([[[[[1]]]]], (0, 0, 0, ... ))

Хуже того, когда depth увеличивается примерно до 2000, код, предоставленный в вопросе, генерирует ошибку времени выполнения GeneratorExitException.

При использовании моей программы он работает для входов любого размера, вложенных в любую глубину и всегда производит правильный вывод.

depth = 50000
L = [1]
while (depth > 0):
  L = [L]
  depth = depth - 1

print (flatten (L))
# (1, (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49990 more...))

print (flatten (range (50000)))
# [ (0, (0,))
# , (1, (1,))
# , (2, (2,))
# , ...
# , (49999, (49999,))
# ]

У кого будет такой глубокий список? Одним из таких распространенных случаев является связанный список, который создает глубокие древовидные структуры

my_list = [ 1, [ 2, [ 3, [ 4, None ] ] ] ]

Такая структура является общей, потому что самая внешняя пара дает нам легкий доступ к двум семантическим частям, о которых мы заботимся: первый элемент и остальные элементы. Связанный список может быть реализован с использованием кортежа или dict.

my_list = ( 1, ( 2, ( 3, ( 4, None ) ) ) )

my_list = { "first": 1
          , "rest": { "first": 2
                    , "rest": { "first": 3
                              , "rest": { "first": 4
                                        , "rest": None
                                        }
                              }
                    }
          }

Выше мы видим, что разумная структура потенциально создает значительную глубину. В Python [], () и {} позволяют вам гнездиться бесконечно. Почему наш общий flatten ограничивает эту свободу?

Я считаю, что если вы собираетесь разработать общую функцию типа flatten, мы должны выбрать реализацию, которая работает в большинстве случаев и имеет наименьшие сюрпризы. Тот, который внезапно терпит неудачу только потому, что используется некоторая (глубокая) структура, является плохим. Используемый в моем ответе flatten не самый быстрый ^[1] но он не удивляет программиста странными ответами или сбоями программы.

^[1] Я не измеряю производительность, пока это не имеет значения, и поэтому я не сделал ничего, чтобы настроить flatten выше. Еще одно преуменьшенное преимущество моей программы заключается в том, что вы можете ее настроить, потому что мы ее написали. С другой стороны, если for, enumerate и yield вызвали проблемы в вашей программе, что бы вы сделали, чтобы "исправить" ее? Как это сделать быстрее? Как мы будем работать на входы большего размера или глубины? Какая польза от Ferrari после обертывания вокруг дерева?

Ответ 3

Рекурсия - хороший подход для сглаживания глубоко вложенных списков. Ваша реализация также хорошо проделана. Я бы предложил изменить его с помощью этого аналогичного рецепта следующим образом:

код

from collections import Iterable


def indexed_flatten(items):
    """Yield items from any nested iterable."""
    for i, item in enumerate(items):
        if isinstance(item, Iterable) and not isinstance(item, (str, bytes)):
            for item_, idx in indexed_flatten(item):
                yield item_, (i,) + idx
        else:
            yield item, (i,)


lst = [[[1, 2, 3], [4, 5]], [6], [7, [8, 9]], 10]
list(indexed_flatten(lst))

Выход

[(1, (0, 0, 0)),
 (2, (0, 0, 1)),
 (3, (0, 0, 2)),
 (4, (0, 1, 0)),
 (5, (0, 1, 1)),
 (6, (1, 0)),
 (7, (2, 0)),
 (8, (2, 1, 0)),
 (9, (2, 1, 1)),
 (10, (3,))]

Это надежно работает со многими типами элементов, например. [[[1, 2, 3], {4, 5}], [6], (7, [8, "9"]), 10].