- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
我正在查看 sorted_containers 的来源惊讶地看到this line :
self._load, self._twice, self._half = load, load * 2, load >> 1
这里 load
是一个整数。为什么在一个地方使用位移,而在另一个地方使用乘法?移位可能比除以 2 更快,这似乎是合理的,但为什么不将乘法也替换为移位呢?我对以下案例进行了基准测试:
并发现 #3 始终比其他替代方案更快:
# self._load, self._twice, self._half = load, load * 2, load >> 1
import random
import timeit
import pandas as pd
x = random.randint(10 ** 3, 10 ** 6)
def test_naive():
a, b, c = x, 2 * x, x // 2
def test_shift():
a, b, c = x, x << 1, x >> 1
def test_mixed():
a, b, c = x, x * 2, x >> 1
def test_mixed_swapped():
a, b, c = x, x << 1, x // 2
def observe(k):
print(k)
return {
'naive': timeit.timeit(test_naive),
'shift': timeit.timeit(test_shift),
'mixed': timeit.timeit(test_mixed),
'mixed_swapped': timeit.timeit(test_mixed_swapped),
}
def get_observations():
return pd.DataFrame([observe(k) for k in range(100)])
问题:
我的测试有效吗?如果是,为什么 (multiply, shift) 比 (shift, shift) 快?
我在 Ubuntu 14.04 上运行 Python 3.5。
编辑
以上是问题的原始陈述。 Dan Getz 在他的回答中提供了很好的解释。
为了完整起见,以下是不适用乘法优化时较大 x
的示例插图。
最佳答案
这似乎是因为小数的乘法在 CPython 3.5 中得到了优化,而小数的左移则没有。作为计算的一部分,正左移总是创建一个更大的整数对象来存储结果,而对于您在测试中使用的排序的乘法,特殊的优化可以避免这种情况并创建一个正确大小的整数对象。这可以在 the source code of Python's integer implementation 中看到.
因为 Python 中的整数是任意精度的,所以它们存储为整数“数字”数组,每个整数位的位数有限制。所以在一般情况下,涉及整数的运算不是单个运算,而是需要处理多个“数字”的情况。在pyport.h中,这个位限制is defined as在 64 位平台上为 30 位,否则为 15 位。 (我从这里开始将其称为 30 以保持解释简单。但请注意,如果您使用的是为 32 位编译的 Python,那么您的基准测试结果将取决于 x
是否小于 32,768与否。)
当操作的输入和输出保持在此 30 位限制内时,可以以优化的方式而不是一般方式来处理操作。 integer multiplication implementation的开头如下:
static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
/* fast path for single-digit multiplication */
if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
/* if we don't have long long then we're almost certainly
using 15-bit digits, so v will fit in a long. In the
unlikely event that we're using 30-bit digits on a platform
without long long, a large v will just cause us to fall
through to the general multiplication code below. */
if (v >= LONG_MIN && v <= LONG_MAX)
return PyLong_FromLong((long)v);
#endif
}
因此,当将两个整数相乘时,每个整数都适合 30 位数字,这是由 CPython 解释器作为直接乘法完成的,而不是将整数作为数组处理。 (在正整数对象上调用 MEDIUM_VALUE()
只会获取其第一个 30 位数字。)如果结果适合单个 30 位数字,PyLong_FromLongLong()
会在相对较少的操作中注意到这一点,并创建一个个位数的整数对象来存储它。
相比之下,左移并没有以这种方式进行优化,并且每个左移都将被移位的整数作为数组处理。特别是,如果您查看 long_lshift()
的源代码,在一个小的但正左移的情况下,总是创建一个 2 位整数对象,如果只是为了稍后将其长度截断为 1:(我在 /*** 中的评论 ***/
)
static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
/*** ... ***/
wordshift = shiftby / PyLong_SHIFT; /*** zero for small w ***/
remshift = shiftby - wordshift * PyLong_SHIFT; /*** w for small w ***/
oldsize = Py_ABS(Py_SIZE(a)); /*** 1 for small v > 0 ***/
newsize = oldsize + wordshift;
if (remshift)
++newsize; /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
z = _PyLong_New(newsize);
/*** ... ***/
}
您没有询问与右移相比整数下限除法的性能更差,因为这符合您(和我)的期望。但是,将一个小的正数除以另一个小的正数也没有像小的乘法那样优化。每个 //
使用函数 long_divrem()
计算商 和 余数。 .这个余数是用 a multiplication 计算一个小的除数。 , 和 is stored in a newly-allocated integer object ,在这种情况下会立即被丢弃。
关于python - 对于 Python 3.x 整数,比位移快两倍?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37053379/
这看起来很基础,但我想不通。是否有一种简单的 CSS 唯一方法可以使 cssa 真正快速淡入并缓慢淡出。这是为了改变多个 div 的颜色。大约 0.5 秒的缓入和 2 秒的缓出。 谢谢! 最佳答案 你
我一直在用各种语言和实现实现相同的代码(在 Blackjack 中发牌而不爆牌的方法的数量)。我注意到的一个奇怪之处是,Python 在 C 中调用分区函数的实现实际上比用 C 编写的整个程序快一点。
如果我没看错,/ 意味着它右边的节点必须是左边节点的直接子节点,例如/ul/li 返回 li 项,它们是作为文档根的 ul 项的直接子项。 //ul//li 返回 li 项,它们是文档中某处任何 ul
如何随机更新一个表。所以你给一列一个随机值。并且该列(例如“顶部”)是唯一的。如果您在数字 10 到 20 之间进行选择,并且您有 10 行,那么您就不能有未使用的数字。如果你有 Test table
这在一小部分是一个问题(因为我不明白为什么它会有所不同),在很大程度上是一篇希望能帮助其他一些可怜的程序员的帖子。 我有一个代码库,是我大约 5-7 年前第一次开始 Android 编程时编写的,它具
我正在尝试过滤关系表以获得满足两个条件的表子集(即:我想要 color_ids 为 1 或 2 的条目的所有 ID)。这是一张结实的 table ,所以我正在尝试尽可能多地进行优化。 我想知道是否有人
在上一篇《聊聊PHP中require_once()函数为什么不好用》中给大家介绍了PHP中require_once()为什么不好用的原因,感兴趣的朋友可以去阅读了解一下~ 那么本文将给大家介绍PH
很难说出这里问的是什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或言辞激烈,无法以目前的形式合理回答。如需帮助澄清此问题以便可以重新打开,visit the help center . 10年前关
有没有办法提高glReadPixels的速度?目前我做: Gdx.gl.glReadPixels(0, 0, Gdx.graphics.getWidth(), Gdx.graphics.getHeig
通常,我以函数形式`:=`()来计算data.table中的多列,认为这是最有效的方法。但是我最近发现它比简单地重复使用:=慢。至少在我的电脑上。 我猜想:=的功能形式可能会产生一些开销,但这是它变慢
我的问题是针对 Windows 环境中多线程的性能问题。 在测试我的代码后,我得到的结果是增加线程数不会提高并行计算的性能,并且在经过一些计数后变得更少。到底是怎么回事?是否可以找出最佳线程数的公式:
我看到很少有相同问题的主题,但我仍然无法解决我的问题。这是我的代码 - 使用 XOR 加密的 C 套接字编程 当服务器和客户端连接时:- 用户发送消息,例如:你好- 服务器响应,例如:(服务器):你好
我正在定义继承自 Shape 类并实现“几何”属性的形状。 这是一个例子: public class Landmark : Shape { public override bool IsInB
相同代码在 Android(1Ghz Snapdragon)上的执行速度比我在 3.3 Ghz Core 2 Duo 的 PC(在桌面应用程序中)快 2 倍(PC 的类被复制到 Android 项目)
我需要将一个值与一组数组进行比较。但是,我需要比较 foreach 中的多个值。如果使用 in_array,它可能会很慢,真的很慢。有没有更快的选择?我当前的代码是 foreach($a as $b)
这个问题在这里已经有了答案: How do I write a correct micro-benchmark in Java? (11 个答案) 关闭 9 年前。 今天我做了一个简单的测试来比较
如果比较不应该以这种方式进行,我深表歉意。我是编程新手,只是很好奇为什么会这样。 我有一个包含词嵌入的大型二进制文件 (4.5gb)。每行都有一个单词,后面跟着它的嵌入,它由 300 个浮点值组成。我
我经历了几个不同的四元数乘法实现,但我很惊讶地发现引用实现是迄今为止我最快的实现。这是有问题的实现: inline static quat multiply(const quat& lhs, cons
我写了一个简单的例子,估计调用虚函数的平均时间,使用基类接口(interface)和dynamic_cast和调用非虚函数。这是它: #include #include #include #in
有没有人知道比“StackWalk”更好/更快的获取调用堆栈的方法?我还认为 stackwalk 在有很多变量的方法上也会变慢......(我想知道商业分析员是做什么的?)我在 Windows 上使用
我是一名优秀的程序员,十分优秀!