Неожиданное арифметическое поведение Python

Question

Я работаю над кодировщиком / декодером Хаффмана в Python и испытываю неожиданное (по крайней мере для меня) поведение в моем коде. Кодирование файла в порядке, проблема возникает при декодировании файла. Ниже приведен связанный код:

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,2 МБ, 679 КБ и 87 КБ), но часть, которая значительно замедляет код, - это for b in com петля. Я провел некоторое время и, честно говоря, не знаю, что происходит.

Я рассчитал весь decode Функция для каждого файла, как показано ниже:

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

Прежде всего, я даже не знаю, как назначить эту сложность. Затем я рассчитал один проход проблемного цикла и понял, что cnode = 2*cnode + b + 1 занимает 2е-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 кажется здесь проблемой.