空のリストから開始して項目を追加するのではなく、事前に割り当てられたリストから開始して各インデックスに項目を設定する方が大幅に高速ですか? 10k-100k のアイテムを保持するには、このリストが必要です。
再帰の各レベルで O(n) 時間を必要とするアルゴリズムを実装しようとしているのですが、O(n^2) 時間を示す結果が得られているためです。リストのサイズを変更し続ける必要があるPythonがこの速度低下を引き起こす可能性があると思いました。
同様の質問が見つかりましたが、私の質問に明確に答えたものはありませんでした。1 つの回答は、アイテムが非常に多いとガベージ コレクションが非常に遅くなる可能性があることを示していたので、GC をオンまたはオフにしてみましたが、結果に改善は見られませんでした。
問題の解決: 誰かが興味を持っている場合、スローダウンは集合をあまりにも頻繁に結合することによって引き起こされました. ここで、別の方法 (並べ替えを含む) を使用して、同じキーが 2 回表示されるかどうかを確認します。
Python は、リストのサイズに比例するチャンクでリストを事前に割り当てます。これにより、リストに追加するための償却された O(1) が得られます
リストがいつ大きくなるかを確認する簡単なテストを次に示します。これらの多くはその場で再割り当てできるため、コピーは必ずしも必要ではないことに注意してください。
>>> import sys
>>> A = []
>>> sz = sys.getsizeof(A)
>>> for i in range(100000):
... if sz != sys.getsizeof(A):
... sz = sys.getsizeof(A)
... print i, sz
... A.append(i)
...
1 48
5 64
9 96
17 132
26 172
36 216
47 264
59 320
73 384
89 456
107 536
127 624
149 724
174 836
202 964
234 1108
270 1268
310 1448
355 1652
406 1880
463 2136
527 2424
599 2748
680 3116
772 3528
875 3992
991 4512
1121 5100
1268 5760
1433 6504
1619 7340
1828 8280
2063 9336
2327 10524
2624 11864
2959 13368
3335 15060
3758 16964
4234 19108
4770 21520
5373 24232
6051 27284
6814 30716
7672 34580
8638 38924
9724 43812
10946 49312
12321 55500
13868 62460
15608 70292
17566 79100
19768 89012
22246 100160
25033 112704
28169 126816
31697 142692
35666 160552
40131 180644
45154 203248
50805 228676
57162 257284
64314 289468
72360 325676
81412 366408
91595 412232