ประสิทธิภาพความเร็วของ Decompression Algorithm

Question

ฉันได้เขียน Javascript ใหม่ใน Python 3.7 ซึ่งจะคลายการบีบอัดไฟล์ที่บีบอัดในรูปแบบเฉพาะ โครงการที่ผมได้รับนี้สามารถใช้ได้จากที่นี่

รหัสที่ฉันคิดขึ้นมานั้นใกล้เคียงกับอะนาล็อกมากที่สุดเท่าที่ฉันจะตีความได้ (ฉันไม่ได้เก่งที่สุดสำหรับ 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

dataสตริงไบต์อยู่ที่ไหนอ่านจากไฟล์ที่เปิดในโหมดไบนารี รหัสของฉันและรหัสดั้งเดิมสร้างผลลัพธ์เดียวกัน แต่โดยที่รหัสเดิมใช้เวลาเพียงไม่กี่วินาทีในการดำเนินการฉันใช้เวลาประมาณ 10 นาทีในไฟล์เดียวกัน การทดสอบกับไฟล์หลายไฟล์จะให้ผลการวัดผลที่คล้ายกัน คำถามเกี่ยวกับประสิทธิภาพเฉพาะของฉันคือ: ฉันจะทำอย่างไรเพื่อเพิ่มความเร็วในการเรียกใช้สคริปต์นี้ในระบบเดียวกันในขณะที่รักษาความแม่นยำของเอาต์พุต

ฉันเปิดรับแนวคิดเรื่องมัลติเธรด / มัลติโพรเซสเซอร์แม้ว่าฉันไม่คิดว่าจะเป็นไปได้เนื่องจากลักษณะของการบีบอัดประเภทนี้

ไฟล์ตัวอย่างแม้ว่าจะมีขนาดเล็กมากและทำงานได้อย่างรวดเร็วทั้งในการใช้งาน มันจะต้องเป็นอาหารที่จะเป็นdecompress_lz2bytes

Answer 1

ฉันไม่สามารถทดสอบได้ในขณะนี้ แต่ฉันสงสัยว่าเป็นผู้ร้าย

output += chunk

ในสองแห่ง บรรทัดนี้อาจมี O (n ^ 2) ความซับซ้อนเพราะการคัดลอกoutputไปยังสถานที่ใหม่ในหน่วยความจำที่มีห้องพักที่จะผนวกchunkกับมัน การต่อท้ายchunkรายการจะมีประสิทธิภาพมากกว่าจากนั้นใช้b''.join()ในตอนท้ายเพื่อเชื่อมต่อชิ้นส่วนทั้งหมดเข้าด้วยกัน

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