Как экономно сымитировать двусвязный список на Python?

Question

[Валерий Рябошапко]

Приветствую.

Мне нужно с каждым элементом последовательности выполнить те или иные действия. Действия зависят от значения предыдущего и следующего элементов в последовательности. Как это сделать красиво и по-питонски?

Городить ради этого полновесный связный список (как это рекомендует Google) не очень-то хочется, особенно если речь идёт о последовательности каких-нибудь скромных целых или коротких строк. После нескольких экспериментов соорудил генератор, чем-то похожий на встроенный enumerate(): принимает последовательность и на каждую итерацию возвращает кортеж из предыдущего, текущего и следующего элементов. Соответственно, если предыдущего или следующего нет, то вместо них возвращается None.

def linked(sequence):
    """
    >>> list(linked([1]))
    [(None, 1, None)]
    >>> list(linked([1, 2]))
    [(None, 1, 2), (1, 2, None)]
    >>> list(linked([1, 2, 3]))
    [(None, 1, 2), (1, 2, 3), (2, 3, None)]
    """
    index = 0
    while index < len(sequence):
        yield (sequence[index - 1] if index else None,
               sequence[index],
               sequence[index + 1] if index + 1 < len(sequence) else None)
        index += 1
    raise StopIteration

Но мне это решение не очень нравится, как-то слишком уж низкоуровнево, отдаёт каким-то Си.

Как это сделать лучше? Есть ли готовые решения?

Answer 1

[Артём Клименко]

def previous_and_next(some_iterable):
    prevs, items, nexts = tee(some_iterable, 3)
    prevs = chain([None], prevs)
    nexts = chain(islice(nexts, 1, None), [None])
    return izip(prevs, items, nexts)

Comments

[angru]

а зачем tee в этой реализации?

from itertools import chain, islice


linked_iter = lambda seq: zip(
    chain([None], seq), seq, chain(islice(seq, 1, None), [None])
)

[Артём Клименко]

angru: и правда не надо, итераторы и сами по себе возьмутся.

з.ы. do not assign a lambda expression ^^
з.з.ы. seq наверно тоже не совсем подходит, тут достаточно просто возможности итерироваться, а чтоб объект подходил под collections.Sequence требуется гораздо больше ограничений

[angru]

Артём Клименко: боевой код так не пишу, это с checkio привычка, там было задание решить задачу использовав минимум символов. lambda чтобы return не писать, c seq то же самое - короче, чем iterable. Но спасибо за наводку, что между ними есть различия, надо покурить.

[Артём Клименко]

angru: tee нужен Как экономно сымитировать двусвязный список на Python?

[angru]

Артём Клименко: действительно

Answer 2

[nirvimel]

def prev_cur_next(list_arg):
    extended_list = [None]
    extended_list.extend(list_arg)
    extended_list.append(None)
    return [extended_list[i - 1:i + 2] for i in xrange(1, len(extended_list) - 1)]

UPD: Сравнительный бенчмакр всех предложенных решений - https://ideone.com/bDogvY
К моему удивлению, мое отстает от решений Артём Клименко и angru ,. Признаю их победу.

Comments

[Валерий Рябошапко]

Интересное решение, но, имхо, тоже не по-питонски это. Обращаться к списку по индексу, полученному от range — это болезнь новичков, пришедших из PHP. И xrange, кстати, отлично дополняется yield. Без него он выглядит странно.

[nirvimel]

Валерий Рябошапко: Бенчмарк показал, что мой вариант отстает по скорости от решений Артём Клименко и angru , но опережает ваш оригинальный вариант. Думаю дело тут не в range, а в "цене" создания объектов tuple против среза list и в крутой низкоуровневой оптимизации itertools.

[Артём Клименко]

nirvimel: https://ideone.com/vZoNIc в вашем варианте заменил генератор списка на генератор, а в варианте angru zip на izip (раз речь о втором питоне), для более корректного сравнения.

Также понял, что использование tee всётки необходимо, дело в том что даже если на вход подать итератор, то tee от итератора вернёт разные итераторы.
https://ideone.com/Qi9aBB