python - 为什么创建从 0 到 log(len(list), 2) 的范围这么慢？

Question

我不知道为什么会这样。我正在处理一些列表，我需要一个从 0 到 log(n, 2) 的 for 循环，其中 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 相同的速度运行。

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

Answer 1

天哪——我认得这个。这与我的一个有关，trac #12121 .首先，由于无聊的原因，使用 Python int 而不是 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))

然后它变得很奇怪。为了生成供 range 使用的 int，Sage 必须弄清楚如何将 log(8)/log(2) 变成 3，结果证明她做了最糟糕的事情。剽窃我原来的诊断(mutatis mutandis):

首先，她检查此对象是否有自己的方法来获取 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 位，看看她是否能证明它们是......但是通过 build 它永远不会工作。最后她放弃并尝试简化它，成功了:

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