94

私は最近、コードをより効率的にするために、Pythonでさまざまなデータ構造がどのように実装されているかを調査するようになりました。リストと両端キューがどのように機能するかを調査したところ、シフトとシフト解除を行うと、リストのO（n）から両端キューのO（1）に時間を短縮したい場合にメリットが得られることがわかりました（リストは、前面に何かを挿入するたびに完全にコピーされるなど...）。私が見つけられないように見えるのは、dequeの実装方法の詳細と、その欠点とリストの詳細です。誰かがこれらの2つの質問について私に教えてもらえますか？

4

4 に答える 4

87

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

Adequeobjectは、二重にリンクされたblockノードのリストで構成されます。

そうdequeです、別の答えが示唆しているように、aは（二重に）リンクされたリストです。

詳細：これが意味するのは、Pythonリストは、スライスを含むランダムアクセスおよび固定長の操作にはるかに優れているのに対し、両端キューは、インデックス付け（ただし、興味深いことに、スライスではない）を使用して、物事をプッシュおよびポップするのにはるかに役立つということです。可能ですが、リストよりも遅くなります。

于 2011-06-06T19:35:52.833 に答える
55

チェックアウトcollections.deque。ドキュメントから：

Dequeは、スレッドセーフでメモリ効率の高い追加と、Dequeの両側からのポップをサポートし、どちらの方向でもほぼ同じO（1）パフォーマンスを実現します。

リストオブジェクトは同様の操作をサポートしますが、高速の固定長操作用に最適化されており、基になるデータ表現のサイズと位置の両方を変更するpop（0）およびinsert（0、v）操作のO（n）メモリ移動コストが発生します。

それが言うように、pop（0）またはinsert（0、v）を使用すると、リストオブジェクトに大きなペナルティが発生します。でスライス/インデックス操作を使用することはできませんが、操作が最適化されている/dequeを使用できます。これを実証するための簡単なベンチマークは次のとおりです。popleftappendleftdeque

import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

私のマシンでの結果：

Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec
于 2011-06-06T19:35:13.943 に答える
20

dequeオブジェクトのドキュメントエントリには、知っておく必要のあることのほとんどが詳しく説明されていると思います。注目すべき引用：

Dequeは、スレッドセーフでメモリ効率の高い追加と、Dequeの両側からのポップをサポートし、どちらの方向でもほぼ同じO（1）パフォーマンスを実現します。

だが...

インデックス付きアクセスは、両端がO（1）ですが、中央がO（n）になります。高速ランダムアクセスの場合は、代わりにリストを使用してください。

ソースを調べて、実装がリンクリストなのか他の何かなのかを判断する必要がありますがdeque、二重リンクリストとほぼ同じ特性を持っているように思えます。

于 2011-06-06T19:35:56.990 に答える
11

他のすべての役立つ回答に加えて、Pythonリスト、両端キュー、セット、および辞書に対するさまざまな操作の時間計算量（Big-Oh）を比較するいくつかの詳細情報があります。これは、特定の問題に対して適切なデータ構造を選択するのに役立ちます。

于 2013-03-17T18:01:05.863 に答える