Как пройти по связанному списку, используя понимание списка? - PullRequest
Новая
       42

Как пройти по связанному списку, используя понимание списка?

1 голос
/ 20 июня 2009

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

В основном, я хочу преобразовать этот код: 

p = self.parent
names = []
while p:
  names.append(p.name)
  p = p.parent
print ".".join(names)

в одну строку, как: 

print ".".join( [o.name for o in <???>] )

Я не уверен, как сделать обход в части ???, хотя, в общем виде (если это вообще возможно). У меня есть несколько структур с похожими атрибутами типа .parent, и я не хочу, чтобы для каждого была написана функция выдачи.

Edit:

Я не могу использовать методы __iter__ самого объекта, потому что он уже используется для перебора значений, содержащихся в самом объекте. Большинство других ответов, кроме liori, жестко задают имя атрибута, чего я хочу избежать.

Вот моя адаптация, основанная на ответе Лиори: 

import operator
def walk(attr, start):
  if callable(attr):
    getter = attr
  else:
    getter = operator.attrgetter(attr)

  o = getter(start)
  while o:
    yield o
    o = getter(o)

Ответы [ 4 ]

6 голосов
/ 20 июня 2009

Самое близкое, что я могу придумать, - это создать родительский генератор: 

# Generate a node's parents, heading towards ancestors
def gen_parents(node):
   node = node.parent
   while node:
      yield node
      node = node.parent

# Now you can do this
parents = [x.name for x in gen_parents(node)]
print '.'.join(parents)
2 голосов
/ 20 июня 2009

Если вы хотите, чтобы ваше решение было общим, используйте общую технику. Это генератор с фиксированной запятой: 

def fixedpoint(f, start, stop):
    while start != stop:
        yield start
        start = f(start)

Он вернет генератор, дающий начало, f (начало), f (f (начало)), f (f (f (начало))), ..., если ни одно из этих значений не равно остановке .

Использование: 

print ".".join(x.name for x in fixedpoint(lambda p:p.parent, self, None))

Моя личная библиотека помощников имеет подобную функцию с фиксированной точкой в ​​течение многих лет ... она очень полезна для быстрых взломов.

1 голос
/ 20 июня 2009

Ваш LinkedList должен быть повторяемым, чтобы он работал правильно.

Вот хороший ресурс по этому вопросу. (Предупреждение в формате PDF) Он очень глубокий как для итераторов, так и для генераторов.

Как только вы это сделаете, вы сможете просто сделать это: 

print ".".join( [o.name for o in self] )
1 голос
/ 20 июня 2009

Понимание списка работает с объектами, которые являются итераторами (имеют метод next ()). Вам нужно определить итератор для вашей структуры, чтобы иметь возможность повторять его таким образом.

...