Двунаправленный перебор списка в Python

Я написал короткую функцию для итерации по списку, начиная с заданного индекса, с последующим переключением между левым и правым значениями.

import itertools
from typing import Generator


def bidirectional_iterate(lst: list, index: int) -> Generator:
    for left, right in itertools.zip_longest(reversed(lst[:index]), lst[index:]):
        if right is not None:
            yield right
        if left is not None:
            yield left


arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#      ^  ^  ^  ^  ^  ^  ^  ^  ^  ^
#      7  5  3  1  0  2  4  6  8  9   <- Expected order of iteration

print(list(bidirectional_iterate(arr, 4)))

Выход:

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

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

Это была самая лучшая реализация Pythonic, которую я мог придумать. Единственное улучшение, которое я могу внести в эту реализацию, — это способ дифференцировать None перечислить элементы из None значения возвращены в панель itertools.zip_longest().

Есть ли лучшие / более быстрые способы или какие-либо библиотеки, которые могут это сделать?

Мне нравится ваш код, но я думаю, что самая большая потенциальная проблема с ним заключается в том, что в каждая итерация петли, оба left и right нужно проверить, не None. Как отметил @FMc, другая проблема заключается в том, что ваш reversed(lst[:index]) и lst[index:] Оба списка должны быть встроены в память еще до того, как вы начнете итерацию. Если вы имеете дело с очень большими списками, это может быть невозможно и уж точно неэффективно.

Вот еще один альтернативный подход, который использует roundrobin рецепт в конце itertools документы. Вместо проверки каждая итерация исчерпал ли генератор, roundrobin удаляет пустой генератор из последовательности генераторов, как только этот генератор поднимает StopIteration. (Если вас устраивает сторонний импорт, вы можете просто импортировать его из more_itertools и это сэкономит вам несколько строк кода). Я также использовал выражения-генераторы вместо списков, которые вы создали в памяти, и немного поработал с вашими подсказками типа, чтобы сделать их более выразительными в отношении того, чего достигает код.

from itertools import cycle, islice
from typing import Iterator, Iterable, TypeVar, Sequence

T = TypeVar("T")

def roundrobin(*iterables: Iterable[T]) -> Iterator[T]:
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))


def bidirectional_iterate(xs: Sequence[T], index: int) -> Iterator[T]:
    left = (xs[i] for i in range((index - 1), -1, -1))
    right = (xs[i] for i in range(index, len(xs)))
    yield from roundrobin(right, left)

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(list(bidirectional_iterate(arr, 4)))

Другой вариант — убрать вызов функции и объединить две функции в одну:

from itertools import cycle, islice
from typing import Iterator, TypeVar, Sequence

T = TypeVar("T")

def bidirectional_iterate(xs: Sequence[T], index: int) -> Iterator[T]:
    """Incorporates the 'roundrobin'  recipe from the itertools docs, credited to George Sakkis"""
    left = (xs[i] for i in range((index - 1), -1, -1))
    right = (xs[i] for i in range(index, len(xs)))
    num_active = 2
    nexts = cycle(iter(it).__next__ for it in (right, left))
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(list(bidirectional_iterate(arr, 4)))

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

from more_itertools import interleave_longest

def bidirectional_iterate(xs, index):
    left = range(index - 1, -1, -1)
    right = range(index, len(xs), 1)
    return [xs[i] for i in interleave_longest(right, left)]

Предупреждение: это, вероятно, не лучше — жонглирование индексами некрасиво — и может быть, а может и не быть быстрее; Я не тестировал. Вы можете написать это без явных циклов или условий (с достаточно узкими определениями циклов и условий) и без внешних библиотек. Вы можете назначить список напрямую, злоупотребляя семантикой нарезки Python:

from typing import TypeVar, Sequence, List

ItemT = TypeVar('ItemT')


def bidirectional_iterate(items: Sequence[ItemT], index: int) -> List[ItemT]:
    n = len(items)
    out = [None]*n

    # Increasing from index to end of items
    out[: 2*(n-index): 2] = items[index: index + n//2]

    # Increasing from beginning of items to index
    out[2*(n-index): : 2] = items[-n: index - n*3//2]

    # Decreasing from index to beginning of items
    out[
        min(-1, 2*index-n-1): : -2
    ] = items[index - n*3//2: index-n]

    # Decreasing from end of items to index
    out[n-1: 2*index: -2] = items[index + n//2:]

    return out


for i in range(10):
    print(bidirectional_iterate(tuple(range(10)), i))

Если вы в конечном итоге используете Numpy, это имеет хорошие шансы на выполнение быстрее, чем итеративное решение. Я проверил это на правильность при n = 10 для всех показанных значений индекса.