9

最近の同様の質問 ( isinstance(foo, types.GeneratorType) または inspect.isgenerator(foo)? ) で、これを一般的に実装する方法に興味を持ちました。

実際には、(のようにitertools.cycle)最初にキャッシュし、StopIteration を報告し、次にキャッシュからアイテムを返すジェネレーター型のオブジェクトを持つことは、一般的に便利なことのように思えますが、オブジェクトがそうでない場合ジェネレーター (つまり、本質的に O(1) ルックアップをサポートするリストまたは dict) ではない場合、キャッシュせず、同じ動作をしますが、元のリストに対してです。

可能性:

1) itertools.cycle を修正します。次のようになります。

def cycle(iterable):
    saved = []
    try: 
         saved.append(iterable.next())
         yield saved[-1]
         isiter = True
    except:
         saved = iterable
         isiter = False
    # cycle('ABCD') --> A B C D A B C D A B C D ...
    for element in iterable:
        yield element
        if isiter: 
            saved.append(element)

     # ??? What next?

ジェネレーターを再起動できれば完璧です。StopIteration を送り返し、次の gen.next() でエントリ 0、つまり「ABCD StopIteration ABCD StopIteration」を返すことができますが、実際には可能ではないようです。 .

2 つ目は、StopIteration がヒットすると、保存されたキャッシュが保持されることです。しかし、内部のsaved[]フィールドにアクセスする方法はないようです。たぶんこれのクラスバージョン?

2) または、リストを直接渡すこともできます。

def cycle(iterable, saved=[]):
    saved.clear()
    try: 
         saved.append(iterable.next())
         yield saved[-1]
         isiter = True
    except:
         saved = iterable
         isiter = False
    # cycle('ABCD') --> A B C D A B C D A B C D ...
    for element in iterable:
        yield element
        if isiter: 
            saved.append(element)

mysaved = []
myiter = cycle(someiter, mysaved)

しかし、それはただ厄介に見えます。そしてC/++では、いくつかの参照を渡し、実際の参照を保存されたものに変更して、反復可能を指すようにすることができます.Pythonでは実際にそれを行うことはできません. したがって、これも機能しません。

その他のオプション?

編集:より多くのデータ。CachingIterable メソッドは遅すぎて効果がないように見えますが、機能する可能性のある方向に私を後押ししてくれました。単純な方法 (自分自身をリストに変換する) よりもわずかに遅くなりますが、既に反復可能な場合はヒットしないようです。

いくつかのコードとデータ:

def cube_generator(max=100):
    i = 0
    while i < max:
        yield i*i*i
        i += 1

# Base case: use generator each time
%%timeit
cg = cube_generator(); [x for x in cg]
cg = cube_generator(); [x for x in cg]
cg = cube_generator(); [x for x in cg]
10000 loops, best of 3: 55.4 us per loop

# Fastest case: flatten to list, then iterate
%%timeit
cg = cube_generator()
cl = list(cg)
[x for x in cl]
[x for x in cl]
[x for x in cl]
10000 loops, best of 3: 27.4 us per loop

%%timeit
cg = cube_generator()
ci2 = CachingIterable(cg)
[x for x in ci2]
[x for x in ci2]
[x for x in ci2]
1000 loops, best of 3: 239 us per loop

# Another attempt, which is closer to the above
# Not exactly the original solution using next, but close enough i guess
class CacheGen(object):
    def __init__(self, iterable):
        if isinstance(iterable, (list, tuple, dict)):
            self._myiter = iterable
        else:
            self._myiter = list(iterable)
    def __iter__(self):
        return self._myiter.__iter__()
    def __contains__(self, key):
        return self._myiter.__contains__(key)
    def __getitem__(self, key):
        return self._myiter.__getitem__(key)

%%timeit
cg = cube_generator()
ci = CacheGen(cg)
[x for x in ci]
[x for x in ci]
[x for x in ci]
10000 loops, best of 3: 30.5 us per loop

# But if you start with a list, it is faster
cg = cube_generator()
cl = list(cg)
%%timeit
[x for x in cl]
[x for x in cl]
[x for x in cl]
100000 loops, best of 3: 11.6 us per loop

%%timeit
ci = CacheGen(cl)
[x for x in ci]
[x for x in ci]
[x for x in ci]
100000 loops, best of 3: 13.5 us per loop

「純粋な」ループに近づくことができるより高速なレシピはありますか?

4

3 に答える 3

6

必要なのはイテレータではなく、イテラブルです。イテレータは、その内容を 1 回だけ反復できます。ジェネレーターのように、イテレーターがそれらを覚えていなくても、イテレーターから同じ値を生成して、イテレーターを取り、それを複数回反復できるものが必要です。次に、キャッシングを必要としない入力を特別にケース化するだけです。非スレッドセーフな例を次に示します (編集: 効率のために更新):

import itertools
class AsYouGoCachingIterable(object):
    def __init__(self, iterable):
        self.iterable = iterable
        self.iter = iter(iterable)
        self.done = False
        self.vals = []

    def __iter__(self):
        if self.done:
            return iter(self.vals)
        #chain vals so far & then gen the rest
        return itertools.chain(self.vals, self._gen_iter())

    def _gen_iter(self):
        #gen new vals, appending as it goes
        for new_val in self.iter:
            self.vals.append(new_val)
            yield new_val
        self.done = True

そしていくつかのタイミング:

class ListCachingIterable(object):
    def __init__(self, obj):
        self.vals = list(obj)

    def __iter__(self):
        return iter(self.vals)

def cube_generator(max=1000):
    i = 0
    while i < max:
        yield i*i*i
        i += 1

def runit(iterable_factory):
    for i in xrange(5):
        for what in iterable_factory():
            pass

def puregen():
    runit(lambda: cube_generator())
def listtheniter():
    res = list(cube_generator())
    runit(lambda: res)
def listcachingiterable():
    res = ListCachingIterable(cube_generator())
    runit(lambda: res)
def asyougocachingiterable():
    res = AsYouGoCachingIterable(cube_generator())
    runit(lambda: res)

結果は次のとおりです。

In [59]: %timeit puregen()
1000 loops, best of 3: 774 us per loop

In [60]: %timeit listtheniter()
1000 loops, best of 3: 345 us per loop

In [61]: %timeit listcachingiterable()
1000 loops, best of 3: 348 us per loop

In [62]: %timeit asyougocachingiterable()
1000 loops, best of 3: 630 us per loop

したがって、クラスに関する最も単純なアプローチは、手動でListCachingIterable行うのとほぼ同じように機能します。list"as-you-go" バリアントはほぼ 2 倍遅くなりますが、リスト全体を消費しない場合 (たとえば、100 を超える最初のキューブのみを探している場合など) には利点があります。

def first_cube_past_100(cubes):
    for cube in cubes:
        if cube > 100:
            return cube
    raise Error("No cube > 100 in this iterable")

それで:

In [76]: %timeit first_cube_past_100(cube_generator())
100000 loops, best of 3: 2.92 us per loop

In [77]: %timeit first_cube_past_100(ListCachingIterable(cube_generator()))
1000 loops, best of 3: 255 us per loop

In [78]: %timeit first_cube_past_100(AsYouGoCachingIterable(cube_generator()))
100000 loops, best of 3: 10.2 us per loop
于 2013-10-21T20:36:54.150 に答える