javascript - 你能比 O(log n) 快 10 倍吗？

Question

我知道在大多数情况下取幂是 O(log n) 或更糟，但我在试图理解数字是如何表示自己时迷失了方向。以 JavaScript 为例，因为它有多种原生数字格式：

100000 === 1E5 && 100000 === 0303240
>>> true

在内部，它们最终不都被存储和操作为存储在内存中的二进制值吗？如果是这样，机器是否能够像存储八进制一样快地存储十进制和科学记数法表示？

因此，您会期望+("1E" + n)比更快Math.pow(10, n)吗？

这个问题主要是关于 1E(n) 是如何工作的，但是在尝试自己思考答案时，我对如何首先解析和存储数字变得更加好奇。我将不胜感激您能提供的任何解释。

score 3 · Accepted Answer

我认为字符串操作不会更快，因为至少连接会创建一个新对象（内存分配，GC 的更多工作），Math.pow通常涉及单机指令。

此外，一些现代 JS VM 会进行热点优化，从 javascript 生成机器代码。有机会Math.pow，但对于弦魔法几乎是不可能的。

如果您 100% 确定Math.pow在您的应用程序中运行缓慢（我简直不敢相信），您可以使用数组查找，它应该会以最快的速度运行：[1,10,100,1000,10000,...][n]. 数组会比较小，复杂度是O(1).

score 1 · Accepted Answer

我在选项上运行了jsperf。

var sum = 0;
for (var i = 1; i < 20; ++i){
  sum += +("1E" + i);
}

由于字符串连接，速度很慢。

var sum = 0;
for (var i = 0; i < 20; ++i){
  Math.pow(10, i);
}

因此速度更快，因为它只对数字进行操作。

var sum = 0;
sum += 1e0;
sum += 1e1;
...
sum += 1e19;

是最快的，但很可能是因为1ex常量是预先计算的值。

为了获得最佳性能，您可能需要自己预先计算答案。

score 1 · Accepted Answer

但我在试图理解数字是如何表示自己时迷失了方向。以 JavaScript 为例，因为它有多种原生数字格式：

在内部，它们最终不都被存储和操作为存储在内存中的二进制值吗？

是的，在 javascript 中，只有一种数字类型是 64 位浮点类型，因此

1 === 1.0

如果是这样，机器是否能够像存储八进制一样快地存储十进制和科学记数法表示？

是的，因为只有一种类型。（也许有细微差别，但应该可以忽略不计）

但是，对于这种特定情况，可以表示的数字有一个限制 ~ 1e300，因此运行时间是 O(~300) = O(1)，所有其他数字都表示为 +/- Infinity。

因此，您会期望 +("1E" + n) 比 Math.pow(10, n) 快吗？

不完全的！1E100 比 Math.pow(10,n) 快但是 +("1E"+n) 比 Math.pow(10,n); 慢不是因为字符串和内存分配，而是因为 JS 解释器必须解析字符串并将其转换为数字，这比原生 Math.pow(num,num) 操作要慢。

score 0 · Accepted Answer

Math.pow 不区分数字，因此它对每个数字都一样慢，前提是解释器不针对整数进行优化。它可能只分配几个浮点数来运行。我忽略了解析时间。

"1E"+n 将分配 2~3 个可能具有相当大内存开销的字符串对象，销毁中间体，并将其重新解析为数字。不太可能比 pow 更快。我再次忽略了解析时间。

4 回答 4