相关疑难解决方法(0)

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

（更新：可能只发生在 Windows 的 CPython 3.8 32 位中，所以如果您不能在其他版本中重现它，请不要感到惊讶。请参阅更新部分中的表格。）

双方iter并reversed因此在列表专门迭代器：

>>> iter([1, 2, 3])
<list_iterator object at 0x031495C8>

>>> reversed([1, 2, 3])
<list_reverseiterator object at 0x03168310>

但reversed一个要慢得多：

> python -m timeit -s "a = list(range(1000))" "list(iter(a))"
50000 loops, best of 5: 5.76 usec per loop

> python -m timeit -s "a = list(range(1000))" "list(reversed(a))"
20000 loops, best of 5: 14.2 usec per loop

而且我可以始终如一地重现它。后来又试了iter五次，分别是5.98、5.84、5.85、5.87、5.86。然后又是reversed五次，分别是 14.3、14.4、14.4、14.5、14.3。

我认为iter增加列表元素的内存位置可能会带来好处，所以我事先尝试反转列表。同一张图：

> python …

这是我的环境：

$ python
Python 3.8.10 (default, Nov 14 2022, 12:59:47) 
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> quit()
$ lscpu | grep "Model name"
Model name:                      Intel(R) Core(TM) i5-4430 CPU @ 3.00GHz
$ sudo dmidecode --type memory | grep -E "^\\s+(Speed|Type):" -
    Type: DDR3
    Speed: 1600 MT/s
    Type: DDR3
    Speed: 1600 MT/s

我在我的机器上始终得到如下计时结果：

$ python -m timeit -s "x = list(range(250)) * 4" "[*x]"
200000 loops, best of 5: 1.54 usec per loop …

我有一个字符串列表，我想按 Python 3.6 中的两个自定义键函数对其进行排序。将多排序方法（按较小键排序，然后按主键排序）与多键方法（将键作为元组(major_key, lesser_key)）进行比较，我可以看到后者比前者慢 2 倍以上，这是惊讶，因为我认为它们是等价的。我想了解为什么会这样。

import random
from time import time

largest = 1000000
length = 10000000
start = time()
lst = [str(x) for x in random.choices(range(largest), k=length)]
t0 = time() - start

start = time()
tmp = sorted(lst, key=lambda x: x[::2])
l1 = sorted(tmp, key=lambda x: ''.join(sorted(x)))
t1 = time() - start

start = time()
l2 = sorted(lst, key=lambda x: (''.join(sorted(x)), x[::2]))
t2 = time() - start

print(f'prepare={t0} multisort={t1} multikey={t2} slowdown={t2/t1}')

assert l1 == l2

我正在优化一段代码并发现列表复制（浅层）是瓶颈。

现在我很好奇：为什么列表复制比复制array8 字节慢这么多？在我看来，应该没有区别。在这两种情况下，应该只是memcpy(dst, src, sizeof(int64_t)*len(src))因为指针的长度为 8 个字节。但显然 Python 做的工作比我预期的要多。它与GC有某种关系吗？或者列表是否可能实现为链接列表？

import array
import numpy as np
import timeit


n = 100*1000
lst = [i for i in range(n)]
arr = array.array('q', lst)
nmp = np.array(arr, dtype=np.int64)

assert(arr.itemsize == 8)

n_iter = 100000
print('=== copy() ===')
print('List of int:', timeit.timeit(stmt='lst.copy()', setup='from __main__ import lst', number=n_iter))
print('Array of 8-bytes:', timeit.timeit(stmt='arr.__copy__()', setup='from __main__ import arr', number=n_iter))
print('Numpy array of int64:', timeit.timeit(stmt='nmp.copy()', setup='from __main__ import nmp', number=n_iter))

结果：

import array
import …