2011-12-29 102 views
2

我知道大多数情况下指数是O(log n)或更差,但是我试图理解数字是如何表示自己的。以JavaScript的,例如,因为它有几个本地的数字格式:你能比O(log n)获得10的幂更快吗?

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

内部,是不是所有最终被存储和处理存储在内存中的二进制值?如果是这样,机器是否能够像八进制一样快地存储小数和科学符号表示?

因此,您认为+("1E" + n)会比Math.pow(10, n)更快吗?

大多数情况下,这个问题是关于1E(n)是如何工作的,但在试图自己思考答案时,我更加好奇数字是如何解析并存储在第一位的。我希望你能提供任何解释。

回答

1

但我迷路了,试图了解数字如何表示自己。以JavaScript为例,因为它有几种本地数字格式:

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

是的在JavaScript中,只有一个号码键入一个64位浮点类型因此

1 === 1.0 

http://www.hunlock.com/blogs/The_Complete_Javascript_Number_Reference

如果是这样,是能够存储小数和科学记数法的机表示与八进制一样快?

是的,因为只有一种类型。 (也许有一个微小的差异,但它应该可以忽略不计)

但是,对于这种特定情况下,可以表示的数字是有限制的〜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)操作要慢。

jsperf test

+0

感谢精心布置,很好的支持答案。 – kojiro 2011-12-29 19:25:32

3

我不认为字符串操作可能会更快,因为至少连接会创建一个新的对象(内存分配,更多的GC工作),Math.pow通常来自单机指令。此外,一些现代JS虚拟机做热点优化,从javascript生成机器码。对于Math.pow有机会,但几乎不可能的字符串魔术。

如果您100%确定Math.pow在您的应用程序中运行缓慢(我无法相信它),您可以使用数组查找,它应该尽可能快地工作:[1,10,100,1000,10000,...][n]。阵列相对较小,复杂度为O(1)

+0

喜欢的数组覆盖范围。 [10^1,10^2,...](我知道^在JS中不是pow) – 2011-12-29 14:38:58

+0

@TomRoggero Better'[1e0,1e1,1e2,1e3,...]' – kan 2011-12-29 14:55:52

0

Math.pow不区分数字,所以对于每个数字它都一样慢,只要解释器​​不针对整数进行优化。它可能只分配几个花车来运行。我忽略了解析时间。

“1E”+ n将分配2〜3个字符串对象,这些对象可能具有相当大的内存开销,销毁中间体并将其重新分解为数字。不可能比pow更快。我再次无视分析时间。

1

我在选项上运行了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为一个常数是预先计算的值。

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

相关问题