Python 3.3 for() 循环迭代处理时间呈指数增长？

Question

我有一个简单的 Python (3.3) 应用程序，其中迭代之间的处理时间在每次迭代中变得更长。我相信我已经将问题隔离到 bytes() 函数，正如您将在下面看到的那样。代码看起来是常数，n 次复杂度。但是，在运行时，它实际上会射击大约 n^2 次。我提供了两个代码块。第一个 block 是有问题的 block ，感觉有点像 n^2 倍的复杂度。第二个 block 是一个小的重构，它从处理输入中删除了 bytes()。这是第一个 block :

import hashlib
def gethash(data):
  return hashlib.sha1(data).hexdigest()
body = b"blob 5\01234"

for i in range(1, 100000):
  hashout = gethash(body+bytes(i))
  if(i%1000==0):
    print(".")

(此 block 的 Linux time 实用程序输出):真实 0m12.742s - 用户 0m12.188s - sys 0m0.536s

这是第二个 block ，经过重构以排除使用 bytes() 并且在迭代之间具有恒定的处理时间(n 次复杂度，看起来是正确的):

import hashlib
def gethash(data):
  return hashlib.sha1(data.encode('utf-8')).hexdigest()
body = "blob 5\01234"

for i in range(1, 100000):
  hashout = gethash(body+str(i))
  if(i%1000==0):
    print(".")

(此 block 的 Linux time 实用程序输出):real 0m0.305s - user 0m0.296s - sys 0m0.008s

我正在使用 Linux Mint 16(x86_64 上的内核 3.11.0-12-generic)和 Python 3.3.2。我大大简化了这段代码，以便更能表达中心问题。我主要使用 Python 3，可以用 Python 编写一些不平凡的应用程序，但我不能声称拥有 Pythonic 思维模式。考虑到这一点，我尝试在 Python 2.7.5 中运行这两个代码块，并且它们都“正常”迭代恒定的时间量(n 次复杂度)。我对那个版本及其功能了解不够，不知道这是否有意义。谢谢!

Answer 1

bytes(i) 创建一个 i 长度的 bytes 对象，其中全是零。查看bytearray文档； bytes 的构造函数参数以相同的方式解释。

要解决此问题，请对字符串进行编码:

  hashout = gethash(body+str(i).encode('utf-8'))

我选择了 UTF-8，因为您选择了 UTF-8，但正确的编码可能取决于您要在其中使用它的上下文。