[解決済み] なぜ max は sort よりも遅いのですか？

質問

私は、以下のことを発見しました。 max よりも遅いです。 sort 関数より遅いです。

Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

パイソン3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

なぜ は max ( O(n) ) よりも遅い。 sort 関数 ( O(nlogn) )?

どのように解決するのですか？

を使用するときは、非常に注意しなければなりません。 timeit モジュールを使うときは、非常に注意しなければなりません。

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

ここでは、初期化コードを一度実行し、ランダムな配列を生成しています。 a . その後、残りのコードが数回実行されます。最初の1回は配列をソートしますが、それ以外はすでにソートされた配列に対して sort メソッドを呼び出しています。最速の時間だけが返されるので、あなたは実際にPythonがすでにソートされた配列をソートするのにかかる時間を計っているのです。

Pythonのソートアルゴリズムの一部は、配列がすでに部分的にソートされているか、完全にソートされているかを検出することです。完全にソートされている場合、これを検出するために配列を通して一度スキャンするだけで、その後停止します。

代わりにあなたが試した場合。

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

を実行すると、タイミングループごとにソートが行われ、配列のソートにかかる時間は、単に最大値を求めるよりもずっと長くなることがわかります。

編集してください。 スカイキングの 答え は、私が説明しきれなかった部分を説明してくれています。 a.sort() はリストで作業していることを知っているので、要素に直接アクセスすることができます。 max(a) は任意のイテラブルで動作するため、一般的な反復処理を使用する必要があります。