JavaScript charAt() 运行时

Question

JavaScript 中的 charAt() 函数相对于字符串长度的运行时复杂度是多少？它是在 EcmaScript 中定义的吗（我没找到）？如果不是，常见浏览器的行为是什么？

Answer 1

这是一个小实验：我生成不同长度的文本并执行 charAt 一百万次。

function repeat(text, n) {
    const randomPositions = [];
    for (let i = 0; i < n; i++) {
        randomPositions.push(Math.floor(Math.random() * text.length));
    }
    const t0 = performance.now();
    for (let pos of randomPositions) {
        text.charAt(pos);
    }
    console.log("Elapsed time: " + (performance.now() - t0) + " ms")
}

const characters ='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';

// Thanks https://www.programiz.com/javascript/examples/generate-random-strings
function generateString(length) {
    let result = '';
    const charactersLength = characters.length;
    for (let i = 0; i < length; i++) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;
}

[10**2, 10**3, 10**4, 10**5, 10**6, 10**7].forEach(l => repeat(generateString(l), 10000000));

我运行它在 Chrome 91、Firefox 89 和 Safari 14 中。

结果：

在 Chrome 和 Firefox 中，所需时间似乎与指示 O(1) 的文本长度没有很强的相关性。一些示例时间：

# Chrome:
Elapsed time: 37.40000003576279 ms
Elapsed time: 39.5 ms
Elapsed time: 38.30000001192093 ms
Elapsed time: 39.40000003576279 ms
Elapsed time: 46.39999997615814 ms
Elapsed time: 45.89999997615814 ms

# Firefox
Elapsed time: 255 ms
Elapsed time: 224 ms
Elapsed time: 269 ms
Elapsed time: 227 ms
Elapsed time: 424 ms
Elapsed time: 393 ms

在 Safari 中，所需时间增加：

Elapsed time: 94.00000000005821 ms
Elapsed time: 83.0000000000291 ms
Elapsed time: 93 ms
Elapsed time: 128 ms
Elapsed time: 294 ms
Elapsed time: 571 ms

我是不是漏掉了一个重要的因素？请告诉我！

JavaScript charAt() 运行时

JavaScript charAt() runtime

javascript

time-complexity