回答編集履歴
5
typo
test
CHANGED
|
@@ -38,6 +38,8 @@
|
|
|
38
38
|
|
|
39
39
|
なお、実データの場合は、こんな極端な偏りがないなら高速化できる筈です。
|
|
40
40
|
|
|
41
|
+
|
|
42
|
+
|
|
41
43
|
---
|
|
42
44
|
|
|
43
45
|
すいません。実際にはやったことないので、上記は理論値です。
|
4
追記
test
CHANGED
|
@@ -30,6 +30,14 @@
|
|
|
30
30
|
|
|
31
31
|
|
|
32
32
|
|
|
33
|
+
と思ったけど違いますね。常に削除対象が先頭になるので、1削除当たり1回の比較しかしてないはずですね。
|
|
34
|
+
|
|
35
|
+
となると比較回数は確実に増えます。ご提示のソースの場合、Remove処理がほぼ全てです。リスト構造になることでRemoveは高速になりますから、速度が上がる可能性もあります。やってみないと解らないです。
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
なお、実データの場合は、こんな極端な偏りがないなら高速化できる筈です。
|
|
40
|
+
|
|
33
41
|
---
|
|
34
42
|
|
|
35
43
|
すいません。実際にはやったことないので、上記は理論値です。
|
3
typo
test
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
|
|
9
|
-
mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較した
|
|
9
|
+
mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較したと仮定すると最初平均300万回、最後は275万回の比較を行います。更に平均して287.5万回です。
|
|
10
10
|
|
|
11
11
|
これを50万回繰り返すので、287.5万回x50万回の比較を行います。
|
|
12
12
|
|
2
微修正
test
CHANGED
|
@@ -32,4 +32,6 @@
|
|
|
32
32
|
|
|
33
33
|
---
|
|
34
34
|
|
|
35
|
-
すいません。実際にはやったことないので、上記は理論値です。
|
|
35
|
+
すいません。実際にはやったことないので、上記は理論値です。
|
|
36
|
+
|
|
37
|
+
計算間違いもあるかも知れません。違ってたらごめんなさい。
|
1
微修正
test
CHANGED
|
@@ -12,7 +12,7 @@
|
|
|
12
12
|
|
|
13
13
|
|
|
14
14
|
|
|
15
|
-
mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個から見つける時に必要な比較回数は23回です。それを50万回繰り返します。
|
|
15
|
+
mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個（＜2の23乗）から見つける時に必要な比較回数は23回です。それを50万回繰り返します。
|
|
16
16
|
|
|
17
17
|
|
|
18
18
|
|