Geschwindigkeitseffizienz des Dekompressionsalgorithmus

Question

Ich habe in Python 3.7 ein Stück Javascript umgeschrieben, das eine in einem bestimmten Format komprimierte Datei dekomprimiert. Das Projekt, von dem ich das bekommen habe, ist hier verfügbar .

Der Code, den ich mir ausgedacht habe, ist so nah wie möglich an einem Analogon (ich bin nicht der Beste in Javascript).

def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = b''

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output += chunk

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat
                output += repeat_chunk

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output += chunk
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return output

Dabei datawird eine Byte-Zeichenfolge aus einer im Binärmodus geöffneten Datei eingelesen. Mein Code und der Originalcode erzeugen beide dieselbe Ausgabe, aber wenn die Ausführung des Originalcodes nur wenige Sekunden dauert, dauert mein Code für dieselbe Datei ~ 10 Minuten. Das Testen mit mehreren Dateien ergibt ähnliche Benchmarks. Meine spezifische Effizienzfrage lautet: Was kann ich tun, um die Ausführungsgeschwindigkeit dieses Skripts auf demselben System zu erhöhen und gleichzeitig die Ausgabegenauigkeit beizubehalten?

Ich bin offen für die Idee von Multithreading / Multiprocessing, obwohl ich aufgrund der Art dieses Komprimierungstyps nicht denke, dass dies möglich ist.

Beispiel - Datei , obwohl es sehr klein ist und schnell läuft auf beiden Implementierungen. Es muss als gefüttert decompress_lz2werden bytes.

Answer 1

Ich kann es im Moment nicht testen, aber ich vermute, dass der Schuldige ist

output += chunk

an ein paar Orten. Diese Zeile weist möglicherweise eine O (n ^ 2) -Komplexität auf, da sie outputan einen neuen Speicherort kopiert wird, an den sie angehängt werden chunkkann. Es wäre effizienter, chunkan eine Liste anzuhängen und b''.join()am Ende alle Chunks zu verketten.

def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = []               # <-- make output a list

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output.append(chunk)  # <-- changed '+=' to '.append()'

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat

                output.append(repeat_chunk)  # <-- changed '+=' to '.append()'

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output.append(chunk)  # <-- changed '+=' to '.append()'
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return b''.join(output)  # <-- concatenate the chunks