JavaScript charAt() 运行时 [英] JavaScript charAt() runtime

问题描述

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

What is the runtime complexity of the charAt() function in JavaScript with respect to the string length? Is it defined in EcmaScript (I failed to find it)? If not, what's the behavior in the common browsers?

推荐答案

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

Here is a small experiment: I generate texts of different lengths and perform charAt a million times.

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 中运行它.

I run it in Chrome 91, Firefox 89 and Safari 14.

结果:

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

In Chrome and Firefox, the needed time does not seem to correlate very strongly with the text length indicating O(1). Some example times:

# 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 中，所需时间增加:

In Safari, the needed time goes up:

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() 运行时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！