1

我最近尝试在 python 中运行 Project Euler 问题。我相信它会做 100^5 步之类的事情。

在看到我的解决方案花费了太长时间（它应该在一分钟内运行）之后，我问自己是否有任何运行这么多步骤的 python 程序是可行的（在一分钟内）

所以，我设计了一个愚蠢的小测试

def fun():
  l=range(1,100)
  for x in l:
     for y in l:
        for k in l:
           for n in l:
               for h in l:
                  s=1

>>> t = timeit.Timer('demorado.fun()','import demorado')
>>> t.timeit(1)
1202.484529018402
>>>

有意义吗？它是否证明任何具有这么多步骤的程序（在这种情况下，我猜有 2*(100^5)）总是需要大约 20 分钟？

4

5 回答 5

2

欧拉计划问题不应该在一分钟内运行，因为您的编程语言足够快，而是因为存在一种比蛮力更聪明的解决方案。

但在你的情况下，是的，你会得到一个循环99^5时间的函数（不是100^5因为range(1,100)is 1, 2, ..., 99）......

于 2012-07-22T22:02:45.337 回答
2

这是一个合理的假设，尽管我不确定它是否在做你想要的。在现实生活中，这可能更接近：

for i in xrange(100 ** 5): pass
于 2012-07-22T22:05:28.607 回答
1

对于python，这可能是一个很好的估计。使用 numpy 或 C++ 扩展可能会加快您的 Project Euler 代码，但请记住 Project Euler 上的所有问题都旨在在 <1 分钟内解决。您不太可能需要运行 100^5 次操作才能得出正确的解决方案。如果我是你，我会尝试从不同的角度解决问题。

于 2012-07-22T22:06:26.863 回答
1

这是否证明任何有这么多步骤的程序总是需要大约 20 分钟？

取决于您对“步骤”的定义。以下代码需要大约 99^5 次浮点运算，但运行时间约为 1 秒：

import numpy as np
a = np.zeros(shape=(1681, 1681), dtype=np.float32) # 1681 x 1681 matrix
b = np.dot(a, a) # matrix product
于 2012-07-22T22:09:57.863 回答
0

尝试pass而不是s=1在内循环中。

此外，使用numpy.nditer“external_loop”选项，或者如果循环成为您的瓶颈，则在 Cython 中编写循环。

于 2012-07-22T22:02:36.007 回答