C++でO（1）を実行しているときに、PythonでO（n）をランダムにアクセスします。なぜですか？

Question

C++ deque：

ランダムアクセス - 定数O（1）

パイソンdeque：

インデックス付きアクセスがn（両端O（1）であるが、Oに遅く） 途中で。

もし私が何かを逃していなければ、他のものはすべて、PythonとC++のデックで同等以上に速く、少なくとも複雑である。いくつかのケースでは、pythonのdequeを改善するものはありますか？そうでなければ、C++の持つものに切り替えるのはなぜですか？

Answer 1

免責事項：この答えは、主にジェフのコメントからインスピレーションを得ているとの回答が既にWhy is a deque implemented as a linked list instead of a circular array ?

あなたの質問に掲示本質的に異なっているが、上記のタイトルは、それ自体が答えです：Pythonで、モジュールcollections.dequeがありリンクされたリストを使用して実装されているため、途中のアイテムにアクセスするときの線形時間の複雑さです。

pydocから：

データ用に最適化されたリストのような配列は、そのエンドポイントの近くにアクセスします。あなたがを迷っている場合この実装が選ばれた理由

は今、答えはジェフが指摘記事ですでに利用可能です。

Answer 2

Dequeは特定の方法で使用されるように構造化されたデータであり、最初の要素または最後の要素によってアクセスされるため、 しかし、pythonはデータ構造で奇妙なことをしたり、この場合、構造

のpythonが、これはあなたがそれは、このデータ構造の「コア」操作ではありませんデックの真ん中にデータ構造要素にアクセスすることを可能にする

remove(value) 
#Remove the first occurrence of value. If not found, raises a ValueError. 

機能を持ってい

は「しかし、中央でO（n）に遅くなります。 「このような場合には、それは、配列のように振る舞うので

両方のケースで