回答編集履歴
1
順序や重複を維持しないというパターンも追加
answer
CHANGED
|
@@ -1,19 +1,45 @@
|
|
|
1
|
-
Listからの削除は**大変重い処理**です。これはListが「配列(array)」と言われるデータ構造であるため、インデックスアクセスがO(1)になる代わりに、削除がO(n)になってしまうからです。
|
|
1
|
+
Listからの削除は**大変重い処理**です。これはListが「配列(array)」と言われるデータ構造であるため、インデックスアクセスがO(1)になる代わりに、削除がO(n)になってしまうからです。ましてや、Removeで添字ではなくオブジェクトを指定する場合は、検索もO(n)になるため、さらに遅い原因になります。
|
|
2
2
|
|
|
3
|
-
|
|
3
|
+
つまり、オリジナルコードは削除のリスト分繰り返しているためO(n × m)です。(nはmainのサイズ、mはdeleteのサイズ)
|
|
4
4
|
|
|
5
|
-
|
|
5
|
+
解決策は二つ(順序重複維持あり)＋二つ(順序重複維持なし)ほどです。
|
|
6
6
|
|
|
7
|
+
###順序と重複を維持する場合
|
|
8
|
+
|
|
9
|
+
順序を維持し、また、重複している場合は重複したままにする場合です。
|
|
10
|
+
|
|
11
|
+
####連結リストを使う
|
|
12
|
+
|
|
7
13
|
「連結リスト(linked list)」といわれるデータ構造の場合は、削除はO(1)になります(代わりに、インデックスアクセスがO(n)です)。C#では連結リストとしてLinkedListが用意されていますので、こちらを使用すれば、速度アップになります。
|
|
8
14
|
|
|
9
15
|
**と言いたいところですが、この方法ではそれほど速くなりません。**
|
|
10
16
|
|
|
11
|
-
なぜなら、Removeで該当の
|
|
17
|
+
なぜなら、Removeで該当のオブジェクトを探す検索がO(n)の計算量が必要になるからです。削除が速いだけで見つけるのが速くなるわけではありません。結局O(n × m)になってしまいます。
|
|
12
18
|
|
|
13
|
-
###新たに配列を作る
|
|
19
|
+
####新たに配列を作る
|
|
14
20
|
|
|
15
21
|
削除するのではなく、削除対象ではない物だけ抜き出して、新しい配列にします。処理はLINQを使うとコードがすっきりするでしょう。また、削除のリストにHashSetを使うと削除対象かどうかのチェックも高速に行うことができます。
|
|
16
22
|
|
|
23
|
+
HashSetの作成はO(n)ですが、検索はO(1)です。配列作成も内部がO(1)ならO(n)になりますので、計算量はO(n + m)とかなり改善されます。
|
|
24
|
+
|
|
25
|
+
###順序と重複を維持しない場合
|
|
26
|
+
|
|
27
|
+
順序を維持し、また、重複している場合は重複したままにする場合です。
|
|
28
|
+
|
|
29
|
+
####並び替え済みリストを使う
|
|
30
|
+
|
|
31
|
+
並び替え済みリストの場合、検索がO(1)と高速になります。C#には並び替え済みのSortedListがありますのでこれが使用できます。ただし、削除はO(n)であり、オリジナルより速い程度です。結局O(n × m)になってしまいます。
|
|
32
|
+
|
|
33
|
+
重複は維持されますが、順序はソートされるために維持できません。
|
|
34
|
+
|
|
35
|
+
####ハッシュ化された集合を使う
|
|
36
|
+
|
|
37
|
+
順序や重複を維持しなければいいのであれば、ハッシュ化された集合が使用できます。検索も削除もほぼO(1)になるため、極めて高速です。
|
|
38
|
+
|
|
39
|
+
ハッシュ化された集合としてHashSetが使用できます。なお、HashSetでは順序もそのまま維持されるようです(正式ドキュメントが見つけられなかったので、知っている人は教えて欲しい)。ただし、重複は維持されません。
|
|
40
|
+
|
|
41
|
+
ただし、ハッシュ化された集合自体の作成にO(n)必要になりますので、そこは注意してください。ということで、計算量はO(n + m)とかなり改善されます。。
|
|
42
|
+
|
|
17
43
|
###検証コード
|
|
18
44
|
|
|
19
45
|
```C#
|
|
@@ -55,9 +81,9 @@
|
|
|
55
81
|
deleteStopwatch.Stop();
|
|
56
82
|
Console.WriteLine("delete 作成完了: {0} ms",
|
|
57
83
|
deleteStopwatch.ElapsedMilliseconds);
|
|
58
|
-
|
|
84
|
+
|
|
59
|
-
|
|
85
|
+
Console.WriteLine();
|
|
60
|
-
|
|
86
|
+
|
|
61
87
|
List<string> list;
|
|
62
88
|
|
|
63
89
|
list = Original(new List<String>(mainList),
|
|
@@ -74,10 +100,24 @@
|
|
|
74
100
|
|
|
75
101
|
Console.WriteLine();
|
|
76
102
|
|
|
77
|
-
list =
|
|
103
|
+
list = CreateListWithHashset(new List<String>(mainList),
|
|
78
104
|
new List<String>(deleteList));
|
|
79
105
|
Console.WriteLine("サイズ: {0}", list.Count);
|
|
80
106
|
Console.WriteLine("最初: {0}", list[0]);
|
|
107
|
+
|
|
108
|
+
Console.WriteLine();
|
|
109
|
+
|
|
110
|
+
list = UseSortedList(new List<String>(mainList),
|
|
111
|
+
new List<String>(deleteList));
|
|
112
|
+
Console.WriteLine("サイズ: {0}", list.Count);
|
|
113
|
+
Console.WriteLine("最初: {0}", list[0]);
|
|
114
|
+
|
|
115
|
+
Console.WriteLine();
|
|
116
|
+
|
|
117
|
+
list = UseHashSet(new List<String>(mainList),
|
|
118
|
+
new List<String>(deleteList));
|
|
119
|
+
Console.WriteLine("サイズ: {0}", list.Count);
|
|
120
|
+
Console.WriteLine("最初: {0}", list[0]);
|
|
81
121
|
}
|
|
82
122
|
|
|
83
123
|
static List<String> Original(List<String> mainList,
|
|
@@ -120,10 +160,11 @@
|
|
|
120
160
|
runStopwatch.ElapsedMilliseconds);
|
|
121
161
|
return newList;
|
|
122
162
|
}
|
|
163
|
+
|
|
123
|
-
static List<String>
|
|
164
|
+
static List<String> CreateListWithHashset(List<String> mainList,
|
|
124
165
|
List<String> deleteList)
|
|
125
166
|
{
|
|
126
|
-
Console.WriteLine("start
|
|
167
|
+
Console.WriteLine("start CreateListWithHashset");
|
|
127
168
|
var runStopwatch = new Stopwatch();
|
|
128
169
|
runStopwatch.Start();
|
|
129
170
|
|
|
@@ -137,6 +178,51 @@
|
|
|
137
178
|
runStopwatch.ElapsedMilliseconds);
|
|
138
179
|
return newList;
|
|
139
180
|
}
|
|
181
|
+
|
|
182
|
+
static List<String> UseSortedList(List<String> mainList,
|
|
183
|
+
List<String> deleteList)
|
|
184
|
+
{
|
|
185
|
+
Console.WriteLine("start UseSortedList");
|
|
186
|
+
var runStopwatch = new Stopwatch();
|
|
187
|
+
runStopwatch.Start();
|
|
188
|
+
|
|
189
|
+
// SortedListに変換して処理をする。
|
|
190
|
+
var mainSortedList = new SortedList<String, String>(
|
|
191
|
+
mainList.ToDictionary(s => s));
|
|
192
|
+
foreach (string deleteStr in deleteList)
|
|
193
|
+
{
|
|
194
|
+
mainSortedList.Remove(deleteStr);
|
|
195
|
+
}
|
|
196
|
+
var newList = mainSortedList.Select(pair => pair.Value)
|
|
197
|
+
.ToList();
|
|
198
|
+
|
|
199
|
+
runStopwatch.Stop();
|
|
200
|
+
Console.WriteLine("run 完了: {0} ms",
|
|
201
|
+
runStopwatch.ElapsedMilliseconds);
|
|
202
|
+
return newList;
|
|
203
|
+
}
|
|
204
|
+
|
|
205
|
+
static List<String> UseHashSet(List<String> mainList,
|
|
206
|
+
List<String> deleteList)
|
|
207
|
+
{
|
|
208
|
+
Console.WriteLine("start UseHashSet");
|
|
209
|
+
var runStopwatch = new Stopwatch();
|
|
210
|
+
runStopwatch.Start();
|
|
211
|
+
|
|
212
|
+
// HashSetに変換して処理をする。
|
|
213
|
+
var mainHashSet = new HashSet<String>(mainList);
|
|
214
|
+
foreach (string deleteStr in deleteList)
|
|
215
|
+
{
|
|
216
|
+
mainHashSet.Remove(deleteStr);
|
|
217
|
+
}
|
|
218
|
+
var newList = mainHashSet.ToList();
|
|
219
|
+
|
|
220
|
+
runStopwatch.Stop();
|
|
221
|
+
Console.WriteLine("run 完了: {0} ms",
|
|
222
|
+
runStopwatch.ElapsedMilliseconds);
|
|
223
|
+
return newList;
|
|
224
|
+
}
|
|
225
|
+
|
|
140
226
|
}
|
|
141
227
|
```
|
|
142
228
|
|
|
@@ -146,21 +232,33 @@
|
|
|
146
232
|
|
|
147
233
|
```
|
|
148
234
|
60000個中5000個を削除
|
|
149
|
-
main 作成完了:
|
|
235
|
+
main 作成完了: 368 ms
|
|
150
|
-
delete 作成完了:
|
|
236
|
+
delete 作成完了: 26 ms
|
|
151
237
|
|
|
152
238
|
start Original
|
|
153
|
-
run 完了:
|
|
239
|
+
run 完了: 4572 ms
|
|
154
240
|
サイズ: 55000
|
|
155
|
-
最初:
|
|
241
|
+
最初: 57539
|
|
156
242
|
|
|
157
243
|
start UseLinkedList
|
|
158
|
-
run 完了:
|
|
244
|
+
run 完了: 3258 ms
|
|
159
245
|
サイズ: 55000
|
|
160
|
-
最初:
|
|
246
|
+
最初: 57539
|
|
161
247
|
|
|
162
|
-
start
|
|
248
|
+
start CreateListWithHashset
|
|
163
249
|
run 完了: 13 ms
|
|
164
250
|
サイズ: 55000
|
|
165
|
-
最初:
|
|
251
|
+
最初: 57539
|
|
252
|
+
|
|
253
|
+
start UseSortedList
|
|
254
|
+
run 完了: 2628 ms
|
|
255
|
+
サイズ: 55000
|
|
256
|
+
最初: 10000
|
|
257
|
+
|
|
258
|
+
start UseHashSet
|
|
259
|
+
run 完了: 16 ms
|
|
260
|
+
サイズ: 55000
|
|
261
|
+
最初: 57539
|
|
166
|
-
```
|
|
262
|
+
```
|
|
263
|
+
|
|
264
|
+
UseSortedListの最初の要素は異なります。UseHashSetの場合は重複が維持されないことに注意です。なお、順序づけしておきたい場合はSortedSetを使うという手段もあります。
|