python - Python:リストの前にある要素を効率的に削除しますか?

Question

数字の長いリストの先頭から要素を削除する方法はありますか? 現在、del arr[i:i+x] を実行していますが、そのポイントを超えてすべてを左に移動する必要があるため、速度が遅く、大きなリストでは時間がかかります。

私は両端キューを調べましたが、それらがここに当てはまるかどうかはわかりません。いくつかの方向を使用できます！

Answer 1

はい、ここにdeque当てはまります。それを使用する方法を示す例を用意しました：

import collections

"create deque from list"
d=collections.deque([1,2,3,4,5,6])
"remove first element"
d.popleft()

print d

出力：

deque([2,3,4,5,6])

Answer 2

おそらくツリーまたはスキップリストが必要だと思います。

しばらく前に Python ツリーの実装について調査しました: http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

これについては、サイトのアルゴリズム セクションで質問したほうがよいかもしれません。

Answer 3

連続して複数の削除を行っている場合は、フィルター付きのジェネレーターを使用して新しいリストを作成する方が効率的かもしれません。

arr = [e for e in arr if not rejected(e)]

インデックスを操作する必要がある場合は、enumerate を使用できます。

arr = [e for i, e in enumerate(arr) if not rejected(i)]

どちらの操作も O(n) (スペースでは O(2*n)) ですが、連続して複数の削除を実行すると O(n*m) (ただし、スペースでは O(n)) になります。

dequeこの特性は、あなたが望むものではないかもしれません:

インデックス アクセスは両端で O(1) ですが、途中で O(n) まで遅くなります。