在 Java 和 C# 等语言中,通常使用 StringBuilder 连接大量字符串以获得线性渐近而不是二次渐近。
然而,JavaScript 以某种方式只能处理一种 String 类型。级联的渐近线在那里是线性的,至少对于高达 131072 次迭代的循环。但是,奇怪的是,时间并不取决于添加的字符串的长度。至少在 Chrome 中是这样的。
这是怎么发生的?
还有一个给 JS 鉴赏家的额外问题:262144 到底发生了什么?
using System;
using System.Collections.Generic;
using System.Diagnostics;
public class Program
{
private static string Test(int n, string s)
{
var res = "";
for (var q=0; q<n; ++q)
res += s;
return res;
}
public static void Main()
{
var res = new Dictionary<string, double>[10];
const int N = 1024;
var sw = new Stopwatch();
for (var n=0; n<res.Length; ++n)
{
res[n] = new Dictionary<string, double>();
foreach (var s in new string[] {"!", "!2", "!234", "!2345678"})
{
res[n][s] = 0;
for (var q=0; q<N; ++q)
{
sw.Restart();
Test(1 << n, s);
sw.Stop();
res[n][s] += sw.ElapsedTicks;
}
res[n][s] /= N;
}
}
for (var n=0; n<res.Length; ++n)
{
Console.Write("{0,2} {1,7} ", n, 1<<n);
foreach (var kvp in res[n])
Console.Write("{0,10:0.000} ", kvp.Value / 1000);
Console.WriteLine();
}
}
}
0 1 0.001 0.000 0.000 0.000
1 2 0.002 0.001 0.001 0.001
2 4 0.003 0.003 0.005 0.003
3 8 0.006 0.006 0.007 0.007
4 16 0.013 0.015 0.013 0.014
5 32 0.025 0.025 0.032 0.034
6 64 0.050 0.059 0.070 0.097
7 128 0.120 0.142 0.220 0.303
8 256 0.337 0.417 0.630 0.972
9 512 0.897 1.256 1.964 4.087
不幸的是,随着迭代次数的增加,该程序不适合在 ideone 上分配的 5 秒执行时间。以下是我家用电脑的结果:
D:\Temp\Supertemp>C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe
Microsoft (R) Visual C# Compiler version 4.7.2046.0
for C# 5
Copyright (C) Microsoft Corporation. All rights reserved.
This compiler is provided as part of the Microsoft (R) .NET Framework, but only supports language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240
0 1 0.000 0.000 0.000 0.000
1 2 0.000 0.000 0.000 0.000
2 4 0.000 0.000 0.000 0.000
3 8 0.001 0.001 0.001 0.001
4 16 0.002 0.001 0.001 0.002
5 32 0.002 0.004 0.004 0.004
6 64 0.005 0.006 0.009 0.014
7 128 0.013 0.019 0.028 0.043
8 256 0.042 0.057 0.087 0.148
9 512 0.118 0.174 0.302 0.559
10 1024 0.354 0.606 1.124 2.279
11 2048 1.220 2.242 4.545 10.041
12 4096 4.517 8.982 19.706 41.568
13 8192 17.864 39.063 82.814 169.274
14 16384 78.454 165.893 337.830 718.843
function test(n, s) {
var res = '';
for (var q=0; q<n; ++q) {
res += s;
}
return res;
}
var res = [], N = 1024;
for (var n=0; n<=18; ++n) {
res.push({len: 1<<n});
for (var s of ['!', '!2', '!234', '!2345678']) {
res[n][s] = 0;
for (var q=0; q<N; ++q) {
var t = performance.now();
test(1 << n, s);
t = performance.now() - t;
res[n][s] += t;
}
res[n][s] /= N;
res[n][s] = res[n][s].toFixed(3);
}
}
console.table(res)