回答編集履歴
5
typo
answer
CHANGED
|
@@ -18,6 +18,7 @@
|
|
|
18
18
|
となると比較回数は確実に増えます。ご提示のソースの場合、Remove処理がほぼ全てです。リスト構造になることでRemoveは高速になりますから、速度が上がる可能性もあります。やってみないと解らないです。
|
|
19
19
|
|
|
20
20
|
なお、実データの場合は、こんな極端な偏りがないなら高速化できる筈です。
|
|
21
|
+
|
|
21
22
|
---
|
|
22
23
|
すいません。実際にはやったことないので、上記は理論値です。
|
|
23
24
|
計算間違いもあるかも知れません。違ってたらごめんなさい。
|
4
追記
answer
CHANGED
|
@@ -14,6 +14,10 @@
|
|
|
14
14
|
ご提示されたコードは600万個の頭の50万個に削除するものが集中しているから、1削除当たり平均25万回の比較になるため、25万回x50万回の比較になりますね。
|
|
15
15
|
ですので、25万回/23回なので1万倍程高速化することが期待できます。1秒かからない筈。
|
|
16
16
|
|
|
17
|
+
と思ったけど違いますね。常に削除対象が先頭になるので、1削除当たり1回の比較しかしてないはずですね。
|
|
18
|
+
となると比較回数は確実に増えます。ご提示のソースの場合、Remove処理がほぼ全てです。リスト構造になることでRemoveは高速になりますから、速度が上がる可能性もあります。やってみないと解らないです。
|
|
19
|
+
|
|
20
|
+
なお、実データの場合は、こんな極端な偏りがないなら高速化できる筈です。
|
|
17
21
|
---
|
|
18
22
|
すいません。実際にはやったことないので、上記は理論値です。
|
|
19
23
|
計算間違いもあるかも知れません。違ってたらごめんなさい。
|
3
typo
answer
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
[コレクションの内部実装](https://csharptan.wordpress.com/2011/12/13/%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3-2/)を見るとList<T>ってソートしてないので頭から１つ1つ比較するので遅いです。更に連続したメモリを確保するようなのでRemoveも遅そうです。（多量のメモリコピーが発生するため）
|
|
4
4
|
|
|
5
|
-
mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較した
|
|
5
|
+
mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較したと仮定すると最初平均300万回、最後は275万回の比較を行います。更に平均して287.5万回です。
|
|
6
6
|
これを50万回繰り返すので、287.5万回x50万回の比較を行います。
|
|
7
7
|
|
|
8
8
|
mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個（＜2の23乗）から見つける時に必要な比較回数は23回です。それを50万回繰り返します。
|
2
微修正
answer
CHANGED
|
@@ -15,4 +15,5 @@
|
|
|
15
15
|
ですので、25万回/23回なので1万倍程高速化することが期待できます。1秒かからない筈。
|
|
16
16
|
|
|
17
17
|
---
|
|
18
|
-
すいません。実際にはやったことないので、上記は理論値です。
|
|
18
|
+
すいません。実際にはやったことないので、上記は理論値です。
|
|
19
|
+
計算間違いもあるかも知れません。違ってたらごめんなさい。
|
1
微修正
answer
CHANGED
|
@@ -5,7 +5,7 @@
|
|
|
5
5
|
mainListの数は最初600万、最後550万ですね。検索で見つかるのに平均して全体の半分と比較した時と仮定すると最初平均300万回、最後は275万回の比較を行います。更に平均して287.5万回です。
|
|
6
6
|
これを50万回繰り返すので、287.5万回x50万回の比較を行います。
|
|
7
7
|
|
|
8
|
-
mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個から見つける時に必要な比較回数は23回です。それを50万回繰り返します。
|
|
8
|
+
mainListをSortedSet<T>に変更すると、2分探索になりますので、600万個（＜2の23乗）から見つける時に必要な比較回数は23回です。それを50万回繰り返します。
|
|
9
9
|
|
|
10
10
|
287.5万回/23回なので125,000倍の速度アップを期待できます。
|
|
11
11
|
SortedSet<T>は一般に言うリスト構造なのでRemoveは高速ですので、更に速くなる筈。
|