5

好奇心と怠惰な退屈から、画家のアルゴリズムであるシュレミエルのベンチマークをいじっていました。空白文字列から始めて、1000 個の空白文字列をもう 1 つ作成し、単純な古い非効率的な文字列連結を使用して、1 つを別の空白文字列に追加し始め、毎回所要時間を計りました。

string s1 = "";
string s2 = "";
while (s2.Length < 1000)
{
    s2 += " ";
}

while (true)
{
    Stopwatch sw = Stopwatch.StartNew();
    s1 += s2;
    sw.Stop();

    Console.WriteLine(" {0}| {1}", s1.Length, sw.ElapsedMilliseconds);
}

予想どおり、文字列が長くなるほど、連結に時間がかかりました (予想よりもはるかに小さい影響でしたが、それはまた別の質問です)。しかし、驚くべきことは、所要時間の一貫したスパイクでした。6 回の連結ごとに、前の 5 回の連結の約 2 倍から 3 倍の時間がかかりました。

 Length     | Time (ms)
 -----------------------
 32250000   | 117
 32251000   | 44
 32252000   | 31
 32253000   | 30
 32254000   | 30
 32255000   | 32
 32256000   | 129
 32257000   | 35
 32258000   | 43
 32259000   | 34
 32260000   | 30
 32261000   | 29
 32262000   | 107
 32263000   | 47
 32264000   | 29
 32265000   | 30
 32266000   | 31
 32267000   | 29
 32268000   | 110
 32269000   | 46
 32270000   | 31
 32271000   | 30
 32272000   | 30
 32273000   | 30
 32274000   | 113

これらのサンプルは、文字列が非常に大きくなり始めたときのものですが、パターンは最初から保持されています。ほとんどの場合、最初の 1000 程度のサンプルは小さすぎてパターンに気付かないのですが、1.8k マークあたりで認識できます。

私の最初の仮定は、文字が何らかの種類の ArrayList/vector 型取引に格納されていて、いっぱいになるとサイズが 2 倍になるというものでしたが、よく考えてみると、それは収まりません。この場合、スパイクは線形ではなく指数関数的に発生します。

つまり、要するに、ここで一体何が起こっているのでしょうか?

4

1 に答える 1

4

文字列を作成して破棄すると、ゴミが発生します。一定量のメモリを使用すると、ガベージ コレクションが発生し、プロセスが一時停止します。プロセスでは他に何も行われておらず、常に文字列を同じ長さにしているため、GC は常に同時に (6 回実行ごとに) 発生します。

このタイミングへの影響を回避するには、各実行でタイマーを開始する前にGC.Collectを呼び出します。

于 2013-11-04T15:10:39.380 に答える