9

我不知道为什么会这样。我弄乱了一些列表，我需要一个for从 0 到log(n, 2)n 是列表长度的循环。但是代码非常慢，所以经过一番研究，我发现问题出在范围生成上。演示示例代码：

n = len([1,2,3,4,5,6,7,8])
k = 8
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2

输出

2 loops, best of 3: 2.2 s per loop
2 loops, best of 3: 3.46 µs per loop

测试的数量很少（我不希望它运行超过 10 分钟），但它已经表明它range(log(n, 2))比仅使用整数的对数的对应物慢几个数量级。这真的很令人惊讶，我不知道为什么会发生这种情况。可能是我的 PC 上的问题，可能是 Sage 问题或 Python 错误（我在 Python 上没有尝试相同的方法）。

使用xrange而不是range也无济于事。此外，如果您获得带有 的数字.n()，则测试 1 以与 2 相同的速度运行。

有人知道会发生什么吗？谢谢！

4

4 回答 4

13

天哪——我认得这个。它与我的一个trac #12121有关。首先，由于无聊的原因，使用 Pythonint而不是 Sage会产生额外的开销：Integer

sage: log(8, 2)
3
sage: type(log(8, 2))
sage.rings.integer.Integer
sage: log(8r, 2)
log(8)/log(2)
sage: type(log(8r, 2))
sage.symbolic.expression.Expression
sage: %timeit log(8, 2)
1000000 loops, best of 3: 1.4 us per loop
sage: %timeit log(8r, 2)
1000 loops, best of 3: 404 us per loop

（r后缀表示“原始”，并防止 Sage 预解析器将文字包装2成Integer(2)）

然后它变得很奇怪。为了产生一个 int 供range消费，Sage 必须弄清楚如何log(8)/log(2)变成 3，而事实证明她做了最糟糕的事情。抄袭我的原始诊断（比照）：

首先，她检查这个对象是否有自己的方式来获取一个 int，但它没有。所以她用 log(8)/log(2) 构建了一个 RealInterval 对象，结果证明这是她能做的最糟糕的事情！她检查区间的上下部分是否一致（我的意思是在地板上）（以便她确定地板是什么）。但是在这种情况下，因为它确实是一个整数！这总是看起来像：

sage: y = log(8)/log(2)
sage: rif = RealIntervalField(53)(y)
sage: rif
3.000000000000000?
sage: rif.endpoints()
(2.99999999999999, 3.00000000000001)

这两个边界的底线不相等，所以 Sage 认为她还没有解决这个问题，她不断将精度提高到 20000 位，看看她是否能证明它们是……但通过构造它是永远不会去工作。最后她放弃并试图简化它，它成功了：

sage: y.simplify_full()
3

不言而喻地证明它是完全可分情况的反常性质：

sage: %timeit range(log(8r, 2))
1 loops, best of 3: 2.18 s per loop
sage: %timeit range(log(9r, 2))
1000 loops, best of 3: 766 us per loop
sage: %timeit range(log(15r, 2))
1000 loops, best of 3: 764 us per loop
sage: %timeit range(log(16r, 2))
1 loops, best of 3: 2.19 s per loop
于 2013-04-29T23:56:47.653 回答
1

Python 2 允许 range(some_float)，但它已被弃用并且在 python 3 中不起作用。

代码示例没有给出指定的输出。但我们可以通过它。首先timeit需要一个完整的脚本，调用timeit的脚本中的import是不用的：

>>> timeit('range(log(8,2))')
  Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib64/python2.6/timeit.py", line 226, in timeit
    return Timer(stmt, setup, timer).timeit(number)
  File "/usr/lib64/python2.6/timeit.py", line 192, in timeit
    timing = self.inner(it, self.timer)
  File "<timeit-src>", line 6, in inner
NameError: global name 'log' is not defined

如果您将导入添加到正在计时的脚本，它包括设置时间：

>>> timeit('from math import log;range(log(8,2))')
3.7010221481323242

如果将导入移到设置中，效果会更好，但是众所周知，一次性的时间是不准确的：

>>> timeit('range(log(8,2))',setup='from math import log')
1.9139349460601807

最后，运行它很多次，你会得到一个不错的数字：

>>> timeit('range(log(8,2))',setup='from math import log',number=100)
0.00038290023803710938
于 2013-04-29T22:48:30.173 回答
1

这看起来像是一个 Sage 错误。

我创建了一个新笔记本并这样做了：

n = len([1,2,3,4,5,6,7,8])
k = 8
timeit('range(log(n, 2))', number=2, repeat=3) # Test 1
timeit('range(log(len([1,2,3,4,5,6,7,8]), 2))', number=2, repeat=3) # Test 1.5
timeit('range(log(k, 2))', number=2, repeat=3) # Test 2

测试 1.5 和测试 1 一样慢。但是如果你以任何方式分解它——去掉range，或者甚至添加m=n+0并使用m而不是n，它会下降到微秒。

很明显，Sage 在评估表达式时试图在这里做一些复杂的事情，并感到困惑。

为了验证这一点，在普通的旧 ipython 中：

n = len([1,2,3,4,5,6,7,8])
k = 8
%timeit 'range(log(n, 2))'
%timeit 'range(log(len([1,2,3,4,5,6,7,8]), 2))'
%timeit 'range(log(k, 2))'

正如您所期望的那样，它们都同样快。

所以……你怎么办？

好吧，您可能想尝试追踪 Sage 错误并将其提交到上游。但与此同时，您可能希望在代码中找到一种解决方法。

如上所述，只是做m = n+0和使用m而不是n似乎可以加快速度。看看这对你有用吗？

于 2013-04-29T22:58:39.707 回答
-1

也许使用log(x, 2)(aka ld()) 一开始就不是一个好主意。我建议使用转换 int 值来实现ld()：

n = len(array)
while n:
  n >>= 1
  # perform the loop stuff

这样，您可以避免使用range()和 的所有这些丑陋log()。

在正常情况下，调用log()应该比在 int 上进行简单的位移花费更多的时间。例子：

>>> timeit('for i in range(int(math.log(8, 2))): pass', setup='import math')
0.6762251853942871
>>> timeit('n = 8\nwhile n:\n  n >>= 1')
0.24107813835144043

值越大，n差异越小。因为n = 10000我得到了 0.8163230419158936 和 0.8106038570404053，但这应该是因为与循环初始化相比，循环体将花费大部分时间。

于 2013-04-29T22:48:15.530 回答