python 2 vs python 3随机性能,特别是`random.sample`和`random.shuffle`

Question

python随机模块的性能问题,特别是,random.sample并random.shuffle提出了这个问题.在我的计算机上,我得到以下结果:

> python  -m timeit -s 'import random' 'random.randint(0,1000)'
1000000 loops, best of 3: 1.07 usec per loop
> python3 -m timeit -s 'import random' 'random.randint(0,1000)'
1000000 loops, best of 3: 1.3 usec per loop

在python3和python2中,性能下降超过20%.它变得更糟.

> python  -m timeit -s 'import random' 'random.shuffle(list(range(10)))'
100000 loops, best of 3: 3.85 usec per loop
> python3 -m timeit -s 'import random' 'random.shuffle(list(range(10)))'
100000 loops, best of 3: 8.04 usec per loop

> python  -m timeit -s 'import random' 'random.sample(range(10),3)'
100000 loops, best of 3: 2.4 usec per loop
> python3 -m timeit -s 'import random' 'random.sample(range(10),3)'
100000 loops, best of 3: 6.49 usec per loop

这表示性能降低了100%random.shuffle,并且几乎降低了200%random.sample.这非常严重.

我在上面的测试中使用了python 2.7.9和python 3.4.2.

我的问题:randompython3中的模块发生了什么？

Answer 1

-----------改变了什么------------------------------------- ----------

发生了几件事:

• 整数在整数/长期统一中变得不那么有效.这也是为什么整数现在是28字节宽而不是64位Linux/MacOS版本上的24字节的原因.

• 通过使用,Shuffle变得更加准确_randbelow.这消除了先前算法中的微妙偏差.

• 索引变得更慢,因为从ceval.c中删除了整数索引的特殊情况,主要是因为它更难以处理更新的整数,并且因为一些核心开发人员并不认为优化是值得的.

• 的范围()函数被替换的xrange() .这是相关的,因为OP的时序都在内循环中使用range().

shuffle()和sample()的算法在其他方面没有变化.

Python 3做了许多改变,比如unicode-无处不在,这使得内部更复杂,更慢,内存更密集.作为回报,Python 3使用户更容易编写正确的代码.

同样,int/long统一使语言更简单,但代价是速度和空间._randbelow()在随机模块中使用的切换具有运行时成本,但在准确性和正确性方面受益.

-----------结论-------------------------------------- ------------

简而言之,Python 3在某些方面对许多用户来说更好,在某些方面更糟糕,人们很少注意到.工程通常是权衡取舍.

- - - - - - 细节 - - - - - - - - - - - - - - - - - - - -------------------

shuffle()的 Python2.7代码:

def shuffle(self, x, random=None):
    if random is None:
        random = self.random
    _int = int
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = _int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

shuffle()的 Python3.6代码:

def shuffle(self, x, random=None):
    if random is None:
        randbelow = self._randbelow
        for i in reversed(range(1, len(x))):
            # pick an element in x[:i+1] with which to exchange x[i]
            j = randbelow(i+1)              # <-- This part changed
            x[i], x[j] = x[j], x[i]
    else:
        _int = int
        for i in reversed(range(1, len(x))):
            # pick an element in x[:i+1] with which to exchange x[i]
            j = _int(random() * (i+1))
            x[i], x[j] = x[j], x[i]

Python 2.7整数大小:

>>> import sys
>>> sys.getsizeof(1)
24

Python 3.6整数大小:

>>> import sys
>>> sys.getsizeof(1)
28

索引查找的相对速度(带有索引到列表中的整数参数的二进制订阅):

$ python2.7 -m timeit -s 'a=[0]' 'a[0]'
10000000 loops, best of 3: 0.0253 usec per loop
$ python3.6 -m timeit -s 'a=[0]' 'a[0]'
10000000 loops, best of 3: 0.0313 usec per loop

ceval.c中的 Python 2.7代码,带有索引查找的优化:

    TARGET_NOARG(BINARY_SUBSCR)
    {
        w = POP();
        v = TOP();
        if (PyList_CheckExact(v) && PyInt_CheckExact(w)) {
            /* INLINE: list[int] */
            Py_ssize_t i = PyInt_AsSsize_t(w);
            if (i < 0)
                i += PyList_GET_SIZE(v);
            if (i >= 0 && i < PyList_GET_SIZE(v)) {
                x = PyList_GET_ITEM(v, i);
                Py_INCREF(x);
            }
            else
                goto slow_get;
        }
        else
          slow_get:
            x = PyObject_GetItem(v, w);
        Py_DECREF(v);
        Py_DECREF(w);
        SET_TOP(x);
        if (x != NULL) DISPATCH();
        break;
    }

ceval.c中的 Python 3.6代码,没有索引查找的优化:

    TARGET(BINARY_SUBSCR) {
        PyObject *sub = POP();
        PyObject *container = TOP();
        PyObject *res = PyObject_GetItem(container, sub);
        Py_DECREF(container);
        Py_DECREF(sub);
        SET_TOP(res);
        if (res == NULL)
            goto error;
        DISPATCH();
    }