1 
import random

a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
d = dict()
for i in xrange(len(a)):
    for j in xrange(len(b)):
        for k in xrange(len(c)):
            if (i+j+k == 10):
                d[(i,j,k)] = a[i]+b[j]+c[k]

print max(d.values())

该代码在其中找到最佳的三元组元素，a,b,c使其最大化a[i]+b[j]+b[k]并i+j+k=10保持

4

4 回答 4

4

首先，您可以更改循环的边界并摆脱最内层的循环：

import random
a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
d = dict()
for i in xrange(10):
    for j in xrange(10 - i):
        k = 10 - i - j
        if k < len(c):
            d[(i,j,k)] = a[i]+b[j]+c[k]

print max(d.values())

这将运行时间提高了约 4.5 倍：

In [2]: %timeit original()
10000 loops, best of 3: 166 us per loop

In [3]: %timeit new()
10000 loops, best of 3: 36.1 us per loop
于 2013-03-16T08:54:28.750 回答
3

由于您实际上并未使用's 键，因此您可以更快地dict构建和迭代 a 。list但是，由于您实际上并没有对这些值做任何事情，除了调用之外max，您可以在进行过程中跟踪最大值，而不是构建和迭代任何东西。

修改NPE的解决方案：

import random
a = [int(1000*random.random()) for i in xrange(10)]
b = [int(1000*random.random()) for i in xrange(10)]
c = [int(1000*random.random()) for i in xrange(10)]
maxval = 0
for i in xrange(10):
    for j in xrange(10 - i):
        k = 10 - i - j
        if k < len(c):
            val = a[i]+b[j]+c[k]
            if val > maxval:
                maxval = val
print maxval

这使得它比他在 CPython 中的版本快得多，但在 PyPy 中却有很大的不同。

                 OP    HYRY   NPE    AB
CPython 2.7.2    161.  98.8   46.9   38.0
PyPy 1.9.0       11.8  7.28   7.39   2.46

不用说，首先使用 PyPy 而不是 CPython 比任何人建议的任何微优化都要大得多。

对于一个真正的问题，你有 1000000 个值而不是 10 个，这是解决它的糟糕方法。

一方面，您可以通过将值保存为值数组int32而不是 Python来减少内存使用量（以及因此分页时间、缓存命中等） list。完成此操作后，您不妨将其放入 1000000x3 中numpy.array。然后你只需要构建一个i+j+k==1000000的掩码数组，应用掩码，并找到其中的最大值。这会将你所有的循环都移到 C 中，我猜它会快 10-30 倍。远不止你从 Python 的微优化中得到的。

但是你可能想去另一个方向。您是否需要列表存在？如果您有一系列数据正在生成/读取/任何延迟，有没有办法在不将整个数据读入内存的情况下做到这一点？看起来您只需要完整的两个列表 - 如果您可以控制第三个到达的顺序，则只需一个。事实上，如果你可以控制第三个的顺序，你只需要生成/读取它的前 10%。

于 2013-03-16T09:22:10.947 回答
1

将您的代码包装在一个函数中将提高变量查找速度，并且您不需要第三个循环：

import random
def f(random=random.random):
    a = [int(1000*random()) for i in xrange(10)]
    b = [int(1000*random()) for i in xrange(10)]
    c = [int(1000*random()) for i in xrange(10)]
    d = {}
    for i in xrange(len(a)):
        for j in xrange(len(b)-i):
            k = 10 - i - j
            if 0 <= k < 10:
                d[i,j,k] = a[i]+b[j]+c[k]
    return max(d.values())
f()

如果你只想要最大值，你不需要字典。

于 2013-03-16T08:56:15.083 回答
0

我认为缓存random.random查找可以显着提高性能。

import random

def f():
    rand = random.random
    a = [int(1000*rand()) for _ in xrange(10)]
    b = [int(1000*rand()) for _ in xrange(10)]
    c = [int(1000*rand()) for _ in xrange(10)]
    d = dict()
    for i in xrange(10):
        for j in xrange(10 - i):
            k = 10 - i - j
            if 0 <= k < 10:
                d[(i,j,k)] = a[i]+b[j]+c[k]

    print max(d.values())

f()
于 2013-03-16T09:14:09.477 回答