12

以前、リスト スライスをできるだけ効率的に反復処理したいという質問に答えようとしていました。

for x in lst[idx1:]:

コピーを作成するため、理想的ではありません (一般に、これは ですO(n))。次に考えたのは、 を使用することitertools.isliceでした。しかし、ドキュメントを見ると、探しているインデックスが見つかるまでislice呼び出さnextれ、その時点で値が生成され始めるようです。これもO(n)。渡されたオブジェクトisliceが alistまたは aの場合、ここで利用できる最適化がある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's 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???
4

4 に答える 4

4

NumPy スライスは非コピーであることに言及する価値があると思います (それらは基になる配列へのビューを作成します)。したがって、データに NumPy 配列を使用できれば、問題は解決します。さらに、ベクトル化によってパフォーマンスをさらに向上させることができます。

于 2012-11-29T15:24:27.447 に答える
2

リスト スライスのコピーを作成せず、(最適化された 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
于 2012-11-29T16:01:37.520 に答える
1

PyPy を使用している場合 (パフォーマンスを気にする場合は使用する可能性があります)、文字列のスライスをコピーしないように最適化します。

于 2012-11-29T16:06:33.053 に答える
0

isliceはモジュールの関数であるため、sだけでなく、一般的に s で機能しitertoolsます (そして確実に機能するはずです) 。そのため、ソースコードで最適化を見つけることができません。これは、特定の反復子で機能するはずだからです。iteratorlistitertools

あなたの場合の正しいアプローチは次のとおりです。

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

takewhileジェネレーターは「1つずつ」呼び出され、新しい値になります-一般的なリストのウォーキング+反復yieldと同じ「速度」 。xrangeしたがって、そのような実装のオーバーヘッドは最小限です。さらに必要な場合は、そのような関数を C レベルで書き直すことができますが、これを行う利点はあまりありません。

于 2012-11-29T15:55:12.797 に答える