なぜl.insert（0、i）がPythonのl.append（i）より遅いのですか？

Question

私は、Pythonでリストを逆にする2つの異なる方法をテストしました。興味深いことに、最初の要素に値を挿入する2番目の方法は、最初の要素よりかなり遅いです。

20.4851300716 
73.5116429329 

これはなぜですか？操作上、要素をヘッドに挿入することはそれほど費用がかかりません。

Answer 1

insertは、挿入位置以降のすべての要素を1つ上に移動する必要があるため、操作はO(n)です。一方、appendは、一般的にはO(1)（最悪の場合、より多くのスペースを割り当てる必要がある場合はO(n)）です。これは実質的な時間差を説明する。

これらの方法の時間の複雑さは、完全に文書化されているhereです。

私は引用：

内部的には、リストはアレイとして表されます。最大のコストは、現在の割り当てサイズを超えて（すべてが移動する必要があるため）、または最初から近い場所に挿入または削除することに起因します（それ以降はすべて移動する必要があるため）。

は今、戻ってあなたのコードに行く、我々はrev2()が実際O(n2)であるのに対しrev1()がO(n)実装であることがわかりますので、rev2()がはるかに遅くなることは理にかなっています。

Answer 2

Pythonでは、リストは配列として実装されています。 1つの要素を配列に追加すると、配列の予約領域が単純に拡張されます。要素を先頭に置くと、すべての要素が1だけずれるため、非常に高価になります。

Answer 3

これは、pythonのリストをオンラインで読むことで確認できます。 Pythonは配列として配列を実装しています。配列のサイズは実際には現在のリストのサイズよりも大きくなります。未使用の要素は配列の最後にあり、先頭ではなくリストのENDに追加できる新しい要素を表します。 Pythonは古典的な償却コストアプローチを使用しているので、平均では、追加の束を行うとリストの末尾に追加するのは時間がかかりますが、単一の追加によって配列がいっぱいになるため、作成される必要があり、すべてのデータが新しい配列にコピーされます。一方、リストの先頭に常に挿入すると、配列の先頭に新しい要素のための空き領域を作るために、下位の配列のすべての要素を1つのインデックスに移動する必要があります。要約すると、N個の挿入を行うことによってリストを作成すると、リストの最後に常に新しい項目を追加すると合計実行時間はO（N）になり、リストの最後にO（N^2）あなたは常にリストの先頭に追加します。