意外的 Python 算术行为

Question

我正在 Python 中研究 huffman encoder/decoder，并且在我的代码中遇到一些意外的（至少对我而言）行为。编码文件没问题，解码文件时出现问题。下面是相关代码：

def decode(cfile):
    with open(cfile,"rb") as f:
        enc = f.read()
        len_dkey = int(bin(ord(enc[0]))[2:].zfill(8) + bin(ord(enc[1]))[2:].zfill(8),2) # length of dictionary
        pad = ord(enc[2]) # number of padding zeros at end of message
        dkey = { int(k): v for k,v in json.loads(enc[3:len_dkey+3]).items() } # dictionary
        enc = enc[len_dkey+3:] # actual message in bytes
        com = []
        for b in enc:
            com.extend([ bit=="1" for bit in bin(ord(b))[2:].zfill(8)]) # actual encoded message in bits (True/False)
    cnode = 0 # current node for tree traversal
    dec = "" # decoded message
    for b in com:
        cnode = 2 * cnode + b + 1 # array implementation of tree
        if cnode in dkey:
            dec += dkey[cnode]
            cnode = 0

    with codecs.open("uncompressed_"+cfile,"w","ISO-8859-1") as f:
        f.write(dec)

第一个 with open(cfile,"rb") as f 对所有文件大小（测试大小为 1.2MB、679KB 和 87KB）都非常快速地调用运行s，但是显着减慢代码速度的部分是 for b in com循环。我已经做了一些计时，老实说我不知道发生了什么。

我已经对每个文件的整个 decode 函数进行了计时，如下所示：

87KB      1.5 sec
679KB     6.0 sec
1.2MB   384.7 sec

首先，我什至不知道如何分配这种复杂性。接下来，我通过有问题的循环对单个运行进行了计时，并得到 cnode = 2*cnode + b + 1 行需要 2e-6 秒，而 if cnode in dkey 行需要 0.0 秒（根据 time.clock() 在 OSX 上）。所以似乎算术正在显着减慢我的程序......？我觉得这没有意义。

我真的不知道发生了什么，非常欢迎任何帮助

Answer 1

我找到了解决问题的方法，但之后我仍然感到困惑。我通过将 dec 从 "" 更改为 []，然后将 dec += dkey[cnode] 行更改为 dec.append(dkey[cnode]) 来解决问题。这导致以下时间：

87KB    0.11 sec
679KB   0.21 sec
1.2MB   1.01 sec

如您所见，这极大地缩短了时间，因此在这方面，这是成功的。但是，我仍然对为什么 python 的字符串连接似乎是这里的问题感到困惑。

意外的 Python 算术行为

Unexpected Python Arithmetic Behavior

python

performance

encoding

decoding