Python 取幂速度
Python exponentiation speed
知道如何估计这个程序需要多长时间吗?我已经 运行 这个程序 8 个小时了,不知道我还需要等多久。
print (9 ** ((9 ** 9) + 9))
我知道答案很大(我知道它会溢出十亿位数)。我只想知道需要多长时间
算术 (9**(N**N+N)
) 的时间与 N
的比例非常好(并且呈指数增长),如下图所示。我的小伙伴大约需要 48 分钟来计算 N=9 的答案。 但是,在某些时候,您的数字的字面表示不适合 RAM,这就是 swapping/paging 发挥作用并因不可预测的因素使整个过程变慢的地方。
(我知道这不能回答你的问题,但我还是想分享图表。欢迎大家 flag/downvote。)
如上所述,您正在进行两个单独的计算。第一个是 9**((9**9) + 9) 的幂。第二个是将该结果转换为十进制字符串格式。第二次计算比第一次计算慢得多。
让我们看看在我的计算机上 9**((N**N)+N) 的大约 运行 次。
对于N=6,求幂需要0.01秒。转换为十进制字符串需要0.02秒。
对于N=7,求幂需要0.15秒。转换为十进制字符串需要 6.9 秒。
对于N=8,求幂需要16.9秒。转换为十进制字符串需要 48 分钟。
对于N=9,求幂需要40分钟。转换为十进制字符串需要很长时间 - 可能需要几周。
Python的整数到字符串的转换算法是O(n^2),它的运行时间最终会占优。还有其他库可以更快地执行计算。 GMPY2 将在不到 2 分钟的时间内完成这两项计算。有关详细信息,请查看此问题的第二个答案:
知道如何估计这个程序需要多长时间吗?我已经 运行 这个程序 8 个小时了,不知道我还需要等多久。
print (9 ** ((9 ** 9) + 9))
我知道答案很大(我知道它会溢出十亿位数)。我只想知道需要多长时间
算术 (9**(N**N+N)
) 的时间与 N
的比例非常好(并且呈指数增长),如下图所示。我的小伙伴大约需要 48 分钟来计算 N=9 的答案。 但是,在某些时候,您的数字的字面表示不适合 RAM,这就是 swapping/paging 发挥作用并因不可预测的因素使整个过程变慢的地方。
(我知道这不能回答你的问题,但我还是想分享图表。欢迎大家 flag/downvote。)
如上所述,您正在进行两个单独的计算。第一个是 9**((9**9) + 9) 的幂。第二个是将该结果转换为十进制字符串格式。第二次计算比第一次计算慢得多。
让我们看看在我的计算机上 9**((N**N)+N) 的大约 运行 次。
对于N=6,求幂需要0.01秒。转换为十进制字符串需要0.02秒。
对于N=7,求幂需要0.15秒。转换为十进制字符串需要 6.9 秒。
对于N=8,求幂需要16.9秒。转换为十进制字符串需要 48 分钟。
对于N=9,求幂需要40分钟。转换为十进制字符串需要很长时间 - 可能需要几周。
Python的整数到字符串的转换算法是O(n^2),它的运行时间最终会占优。还有其他库可以更快地执行计算。 GMPY2 将在不到 2 分钟的时间内完成这两项计算。有关详细信息,请查看此问题的第二个答案: