python - 如何优化python中的内存访问？

Question

这可能没有用。这只是我为自己设置的挑战。
假设您有一个大数组。你能做些什么才能使程序不会从缓存、缓存行预取或下一次内存访问只能在第一次访问完成后确定这一事实中受益。
所以我们有我们的数组:array = [0] * 10000000如果您必须访问循环中的所有元素，那么取消优化内存访问的最佳方法是什么？思路是尽可能增加每个内存位置的访问时间
我不是在寻找建议在进行下一次访问之前做“其他事情”(这需要时间)的解决方案。这个想法实际上是尽可能地增加访问时间。我想我们必须以某种方式遍历数组(也许是随机的？我还在研究它)

Answer 1

我没想到有什么区别，但实际上以随机顺序访问数字比以顺序或相反顺序访问它们(两者大致相同)要慢得多。

>>> N = 10**5
>>> arr = [random.randint(0, 1000) for _ in range(N)]
>>> srt = list(range(N))
>>> rvd = srt[::-1]
>>> rnd = random.sample(srt, N)
>>> %timeit sum(arr[i] for i in srt)
10 loops, best of 5: 24.9 ms per loop
>>> %timeit sum(arr[i] for i in rvd)
10 loops, best of 5: 25.7 ms per loop
>>> %timeit sum(arr[i] for i in rnd)
10 loops, best of 5: 59.2 ms per loop

它似乎真的是随机性。只是乱序访问索引，但有一个模式，例如如 [0, N-1, 2, N-3, ...]或 [0, N/2, 1, N/2+1, ...] , 就像按顺序访问它们一样快:

>>> alt1 = [i if i % 2 == 0 else N - i for i in range(N)]
>>> alt2 = [i for p in zip(srt[:N//2], srt[N//2:]) for i in p]
>>> %timeit sum(arr[i] for i in alt1)
10 loops, best of 5: 24.5 ms per loop
>>> %timeit sum(arr[i] for i in alt2)
10 loops, best of 5: 24.1 ms per loop

有趣的是，仅迭代混洗的索引(并像上面的数组一样计算它们的 sum)也比对排序索引执行相同操作慢，但没有那么多。 srt 之间约 35 毫秒的差异和 rnd ，~10ms 似乎来自迭代随机索引，~25ms 用于以随机顺序实际访问索引。

>>> %timeit sum(i for i in srt)
100 loops, best of 5: 19.7 ms per loop
>>> %timeit sum(i for i in rnd)
10 loops, best of 5: 30.5 ms per loop
>>> %timeit sum(arr[i] for i in srt)
10 loops, best of 5: 24.5 ms per loop
>>> %timeit sum(arr[i] for i in rnd)
10 loops, best of 5: 56 ms per loop

(运行 Linux 的旧笔记本电脑上的 IPython 5.8.0/Python 3.7.3)