knots-memo-2と同様の発想で、 今度は、Reduceの中の検索部分の実行回数を調べてみた。
ReduceはC++でもSwiftでも、3重ループになっていて、 その内側に検索がある。
C++の場合は連結リストからのリニアスキャンで、O(N)で遅く見える。 Swiftの場合はSetへの存在チェックで、O(1)で速く見える。
C++の計測コード
// For every source->k
for(list<int>::iterator k = Graph[MM][source].out.begin();
k != Graph[MM][source].out.end(); k++) {
searchCount += 1;
int searchRangeSize = (int)Graph[MM][*j].out.size();
maxSearchRangeSize = max(maxSearchRangeSize, searchRangeSize);
searchRangeSizeSum += searchRangeSize;
// Search for j->k. If found, remove it; if not, add it.
list<int>::iterator search;
for(search = Graph[MM][*j].out.begin();
search != Graph[MM][*j].out.end(); search++ )
{出力コード
printf("@@@ Reduce(MM=%2d): searchCount=%8d, size=%8d, ave=%6d, max=%6d, allSearchCount=%8d\n",
MM, searchCount, searchRangeSizeSum,
searchCount > 0 ? (int)((float)searchRangeSizeSum / (float)searchCount) : 0,
maxSearchRangeSize,
allSearchCount);
MMのステップに対する
検索が行われた回数と、
検索対象のサイズ x 検索回数、
検索一回あたりの平均対象サイズ、
最大の検索対象サイズ、
プログラム全体での検索回数
を出している。
同じことをSwiftでは下記で計測
for a in graph.cotargets[y] ?? [] where a != x {
for b in graph.targets[x] ?? [] where b != y {
searchCount += 1
searchRangeSize = graph.targets[a]?.count ?? 0
searchRangeSizeSum += searchRangeSize
maxSearchRangeSize = max(maxSearchRangeSize, searchRangeSize)
if graph.targets[a]?.contains(b) ?? false {
graph.disconnect(a, b)
} else {
graph.connect(a, b)
}
}
}で、結果。
C++
@@@ Reduce(MM=39): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=38): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=37): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=36): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=35): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=34): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=33): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=32): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=31): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=30): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=29): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=28): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=27): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=26): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=25): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=24): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 0
@@@ Reduce(MM=23): searchCount= 81, size= 909, ave= 11, max= 22, allSearchCount= 81
@@@ Reduce(MM=22): searchCount= 1699, size= 19999, ave= 11, max= 37, allSearchCount= 1780
@@@ Reduce(MM=21): searchCount= 12383, size= 164141, ave= 13, max= 78, allSearchCount= 14163
@@@ Reduce(MM=20): searchCount= 28470, size= 334130, ave= 11, max= 60, allSearchCount= 42633
@@@ Reduce(MM=19): searchCount= 9395, size= 68891, ave= 7, max= 27, allSearchCount= 52028
@@@ Reduce(MM=18): searchCount= 2518, size= 13643, ave= 5, max= 17, allSearchCount= 54546
@@@ Reduce(MM=17): searchCount= 363, size= 1316, ave= 3, max= 7, allSearchCount= 54909
@@@ Reduce(MM=16): searchCount= 28, size= 71, ave= 2, max= 4, allSearchCount= 54937
@@@ Reduce(MM=15): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM=14): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM=13): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM=12): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM=11): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM=10): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 9): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 8): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 7): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 6): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 5): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 4): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 3): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 2): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
@@@ Reduce(MM= 1): searchCount= 0, size= 0, ave= 0, max= 0, allSearchCount= 54937
Swift
@@@ loop= 0, alex= 0, k= 5: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 0
@@@ loop= 1, alex= 0, k= 4: searchCount= 48, size= 925, ave= 19, max= 26 allSearchCount= 48
@@@ loop= 2, alex= 0, k= 3: searchCount= 2069, size= 70958, ave= 34, max= 75 allSearchCount= 2117
@@@ loop= 3, alex= 0, k= 2: searchCount= 31431, size= 2126998, ave= 67, max= 187 allSearchCount= 33548
@@@ loop= 4, alex= 0, k= 1: searchCount= 396656, size= 46550351, ave= 117, max= 285 allSearchCount= 430204
@@@ loop= 5, alex= 0, k= 0: searchCount= 1313313, size= 185287215, ave= 141, max= 335 allSearchCount= 1743517
@@@ loop= 6, alex= 0, k=-1: searchCount= 1186708, size= 132173551, ave= 111, max= 219 allSearchCount= 2930225
@@@ loop= 7, alex= 0, k=-2: searchCount= 123215, size= 4429047, ave= 35, max= 104 allSearchCount= 3053440
@@@ loop= 8, alex= 0, k=-3: searchCount= 6571, size= 68080, ave= 10, max= 28 allSearchCount= 3060011
@@@ loop= 9, alex= 0, k=-4: searchCount= 355, size= 1546, ave= 4, max= 9 allSearchCount= 3060366
@@@ loop=10, alex= 0, k=-5: searchCount= 12, size= 24, ave= 2, max= 2 allSearchCount= 3060378
@@@ loop=11, alex= 0, k=-6: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3060378
@@@ loop=12, alex= 0, k=-7: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3060378
@@@ loop=13, alex= 1, k= 4: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3060378
@@@ loop=14, alex= 1, k= 3: searchCount= 168, size= 1871, ave= 11, max= 21 allSearchCount= 3060546
@@@ loop=15, alex= 1, k= 2: searchCount= 2889, size= 49520, ave= 17, max= 47 allSearchCount= 3063435
@@@ loop=16, alex= 1, k= 1: searchCount= 13242, size= 293523, ave= 22, max= 76 allSearchCount= 3076677
@@@ loop=17, alex= 1, k= 0: searchCount= 8554, size= 188709, ave= 22, max= 63 allSearchCount= 3085231
@@@ loop=18, alex= 1, k=-1: searchCount= 3259, size= 39896, ave= 12, max= 30 allSearchCount= 3088490
@@@ loop=19, alex= 1, k=-2: searchCount= 403, size= 2234, ave= 5, max= 12 allSearchCount= 3088893
@@@ loop=20, alex= 1, k=-3: searchCount= 12, size= 24, ave= 2, max= 2 allSearchCount= 3088905
@@@ loop=21, alex= 1, k=-4: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3088905
@@@ loop=22, alex= 1, k=-5: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3088905
@@@ loop=23, alex= 2, k= 4: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3088905
@@@ loop=24, alex= 2, k= 3: searchCount= 27, size= 185, ave= 6, max= 9 allSearchCount= 3088932
@@@ loop=25, alex= 2, k= 2: searchCount= 164, size= 1048, ave= 6, max= 16 allSearchCount= 3089096
@@@ loop=26, alex= 2, k= 1: searchCount= 68, size= 307, ave= 4, max= 8 allSearchCount= 3089164
@@@ loop=27, alex= 2, k= 0: searchCount= 29, size= 107, ave= 3, max= 6 allSearchCount= 3089193
@@@ loop=28, alex= 2, k=-1: searchCount= 4, size= 8, ave= 2, max= 2 allSearchCount= 3089197
@@@ loop=29, alex= 2, k=-2: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3089197
@@@ loop=30, alex= 2, k=-3: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3089197
@@@ loop=31, alex= 3, k= 4: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3089197
@@@ loop=32, alex= 3, k= 3: searchCount= 2, size= 7, ave= 3, max= 4 allSearchCount= 3089199
@@@ loop=33, alex= 3, k= 2: searchCount= 1, size= 2, ave= 2, max= 2 allSearchCount= 3089200
@@@ loop=34, alex= 3, k= 1: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3089200
@@@ loop=35, alex= 3, k= 0: searchCount= 0, size= 0, ave= 0, max= 0 allSearchCount= 3089200
プログラム全体での合計検索回数が、 5万と300万で、60倍の差がついている。
平均探索サイズもだいぶ違う。 C++の方はだいたい10個ぐらい。 Swiftの方は100ぐらい。
10個ぐらいの連結リストのリニアスキャンと、 100個ぐらいのSetのハッシュ検索だと、 検索時間としてはほぼ同じぐらいになる気がする。
どちらもmaxの値を見た感じ、 極端に歪んだ分布になっていることは無さそう。 C++のMM=20のケースについては、 生の値をダンプしてみたけど、10〜20の範囲で適度にばらつく感じだった。
検証結果