Efficacité de la vitesse de l'algorithme de décompression
J'ai réécrit un morceau de Javascript en Python 3.7 qui décompresse un fichier compressé dans un format spécifique. Le projet dont j'ai obtenu ceci est disponible ici .
Le code que j'ai trouvé est aussi proche d'un analogique que je pourrais l'interpréter (je ne suis pas le meilleur en 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
où dataest une chaîne d'octets lue à partir d'un fichier ouvert en mode binaire. Mon code et le code d'origine produisent tous deux la même sortie, mais lorsque le code d'origine ne prend que quelques secondes à s'exécuter, le mien prend ~ 10 minutes sur le même fichier. Tester avec plusieurs fichiers donne des repères similaires. Ma question d'efficacité spécifique est la suivante: que puis-je faire pour augmenter la vitesse d'exécution de ce script sur le même système tout en maintenant la précision de sortie?
Je suis ouvert à l'idée du multithreading / multiprocessing bien que je ne pense pas que ce soit possible en raison de la nature de ce type de compression.
Fichier d' exemple , bien qu'il soit très petit et s'exécute rapidement sur les deux implémentations. Il doit être alimenté en decompress_lz2tant que bytes.
Réponses
Je ne peux pas le tester pour le moment, mais je soupçonne que le coupable est
output += chunk
dans quelques endroits. Cette ligne a potentiellement une complexité O (n ^ 2) en raison de la copie outputvers un nouvel endroit de la mémoire qui a de la place pour y ajouter chunk. Il serait plus efficace d'ajouter chunkà une liste puis de l'utiliser b''.join()à la fin pour concaténer tous les morceaux.
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