Itertools.islice - эффективный выбор списка

Раньше я пытался ответить на вопрос, где я хотел бы как можно более итеративно перебирать фрагмент списка.

for x in lst[idx1:]:

не идеален, так как он создает копию (в общем, это O(n)). Моя следующая мысль заключалась в том, чтобы использовать itertools.islice. Но если вы посмотрите на документацию, кажется, что islice вызовет next, пока не найдет индекс, который он ищет, и в этот момент он начнет давать значения. Это также O(n). Похоже, что существует оптимизация, доступная здесь, если объект, переданный в islice, является list или tuple. Кажется, что вы могли выполнять итерацию по "срезу" напрямую (на C) без фактического создания копия. Мне было любопытно, если эта оптимизация находится в источнике, но я ничего не нашел. Я не очень хорошо знаком с C и деревом исходников python, поэтому вполне возможно, что я его пропустил.

Мой вопрос:

Есть ли способ итерации над списком "срез" без создания копии среза списка и без записи через кучу нежелательных элементов (в оптимизированной реализации C)?

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

def myslice(obj,start,stop,stride):
    for i in xrange(start,stop,stride):
        yield obj[i]

но это определенно не собирается превзойти оптимизированную реализацию C.

Если вам интересно, зачем мне это нужно, просто перейдя по фрагменту напрямую, рассмотрите разницу между:

takewhile(lambda x: x == 5, lst[idx:])  #copy the tail of the list unnecessarily

takewhile(lambda x: x == 5, islice(lst,idx,None)) #inspects the head of the list unnecessarily

и, наконец:

takewhile(lambda x: x == 5, magic_slice(lst,idx,None)) #How to create magic_slice???

Ответ 1

Есть ли способ итерации над списком "срез" без создания копии среза списка и без записи через кучу нежелательных элементов (в оптимизированной реализации C)?

Да, если вы пишете эту реализацию C. Cython делает это особенно просто.

cdef class ListSlice(object):
    cdef object seq
    cdef Py_ssize_t start, end

    def __init__(self, seq, Py_ssize_t start, Py_ssize_t end):
        self.seq = seq
        self.start = start
        self.end = end

    def __iter__(self):
        return self

    def __next__(self):
        if self.start == self.end:
            raise StopIteration()
        r = self.seq[self.start]
        self.start += 1
        return r

Ответ 2

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

Ответ 3

Если вы используете PyPy (который вы можете, так как вы заботитесь о производительности), они оптимизируют строковое кодирование, чтобы не копировать: http://doc.pypy.org/en/latest/interpreter-optimizations.html

Ответ 4

islice - это функция из модуля itertools, поэтому она работает (и определенно должна работать) с iterator в общем случае не только с list s. Таким образом, вы не можете найти свою оптимизацию в исходном коде itertools, потому что она должна работать с любым заданным итератором.

Правильный подход в вашем случае:

def magic_slice(lst, start, end=None):
    for pos in xrange(start, (end or len(lst)):
        yield lst[pos]

takewhile будет вызывать ваш генератор "один за другим", и он будет yield новых значений - той же "скорости", что и для повторения общего списка ходов + xrange итерации. Таким образом, накладные расходы при такой реализации минимальны. Если вам нужно больше - вы можете переписать такую функцию на уровне C, но я не вижу много преимуществ для этого.