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

Question

我不知道为什么会发生这种情况.我在搞乱一些列表,我需要一个for从0到log(n, 2)n 的循环,其中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))比仅使用整数的对数的对应物慢几个数量级.这真的很令人惊讶,我不知道为什么会发生这种情况.也许是我的电脑上的问题,可能是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 preparser将文字包装2成Integer(2))

然后它变得奇怪.为了产生一个range消费的int ,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