8

Python でリストを逆にする 2 つの異なる方法をテストしました。

import timeit

value = [i for i in range(100)]
def rev1():
    v = []
    for i in value:
        v.append(i)
    v.reverse()

def rev2():
    v = []
    for i in value:
        v.insert(0, i)

print timeit.timeit(rev1)
print timeit.timeit(rev2)

興味深いことに、最初の要素に値を挿入する 2 番目のメソッドは、最初のメソッドよりかなり遅いです。

20.4851300716
73.5116429329

どうしてこれなの？操作の面では、要素をヘッドに挿入することはそれほど高価ではないようです。

4

3 に答える 3

1

Python では、リストは配列として実装されます。配列に要素を 1 つ追加すると、配列用に予約されたスペースが単純に拡張されます。要素を先頭に追加すると、すべての要素が 1 つシフトされ、非常にコストがかかります。

于 2013-07-14T01:52:20.293 に答える
1

これは、Python リストについてオンラインで読むことで確認できます。Python はリストを配列として実装します。配列のサイズは通常、現在のリストのサイズよりも大きくなります。未使用の要素は配列の末尾にあり、リストの先頭ではなく末尾に追加できる新しい要素を表します。Python は古典的な償却コスト アプローチを使用するため、多数の追加を行う場合、平均してリストの末尾への追加には O(1) 時間がかかりますが、1 回の追加で配列がいっぱいになることがあるため、新しいより大きな配列作成する必要があり、すべてのデータが新しい配列にコピーされます。一方、常にリストの先頭に挿入する場合は、基になる配列ですべての要素を 1 つのインデックス上に移動して、配列の先頭に新しい要素用のスペースを作る必要があります。要約すると、

于 2013-07-14T01:57:53.673 に答える