itertools.islice по сравнению с фрагментом списка - PullRequest
Новая
       20

itertools.islice по сравнению с фрагментом списка

14 голосов
/ 29 апреля 2010

Я пытался применить алгоритм, чтобы сократить список питонов в меньший по определенным критериям. Из-за большого объема исходного списка, порядка 100 тыс. Элементов, я попытался использовать itertools для избежания многократного выделения памяти, поэтому придумал следующее: 

reducedVec = [ 'F' if sum( 1 for x in islice(vec, i, i+ratio) if x == 'F' ) 
                         > ratio / 3.0 else 'T'
                for i in xrange(0, len(vec), ratio) ]

Время выполнения для этого занимает очень много времени, порядка нескольких минут, когда в vec около 100 тыс. Элементов. Когда я попытался вместо этого: 

reducedVec = [ 'F' if sum( 1 for x in vec[i:i+ratio] if x == 'F' ) 
                         > ratio / 3.0 else 'T'
                for i in xrange(0, len(vec), ratio) ]

по сути заменить островок на срез, выполнение выполняется мгновенно.

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

Cheers, Фемида

Ответы [ 2 ]

13 голосов
/ 29 апреля 2010

islice работает с произвольными итерациями. Чтобы сделать это, вместо того, чтобы прыгать прямо к n-му элементу, он должен перебрать первый n-1, отбросив их, а затем получить те, которые вы хотите.

Ознакомьтесь с чистой реализацией Python из документации itertools : 

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1))
    nexti = next(it)
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = next(it)

Говоря о документации itertools, если бы я пытался выполнить эту операцию, я бы, вероятно, использовал рецепт grouper. Это на самом деле не спасет вас, но могло бы помочь, если бы вы переписали его так, чтобы оно было ленивее, что было бы непросто. 

from __future__ import division

from itertools import izip_longest
def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

reducedVec = []
for chunk in grouper(ratio, vec):
    if sum(1 for x in chunk if x == 'F') > ratio / 3:
        reducedVec.append('F')
    else:
        reducedVec.append('T')

Мне нравится использовать grouper, чтобы абстрагировать последовательные фрагменты и найти этот код намного проще для чтения, чем оригинал

1 голос
/ 29 апреля 2010

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

...