Verbessern der Python-Iterationsleistung über große Dateien

Question

Ich habe eine Referenzdatei, die etwa 9.000 Zeilen ist und die folgende Struktur hat: (Index, Größe) - wo Index ist einzigartig, aber die Größe möglicherweise nicht.

0 193532 
1 10508 
2 13984 
3 14296 
4 12572 
5 12652 
6 13688 
7 14256 
8 230172 
9 16076 

Und ich habe eine Datendatei, die über 650.000 Zeilen und hat die folgende Struktur: (Cluster, Offset, Größe) - wo Offset einzigartig ist aber die Größe ist es nicht.

446 0xdf6ad1 34572 
447 0xdf8020 132484 
451 0xe1871b 11044 
451 0xe1b394 7404 
451 0xe1d12b 5892 
451 0xe1e99c 5692 
452 0xe20092 6224 
452 0xe21a4b 5428 
452 0xe23029 5104 
452 0xe2455e 138136 

Ich brauche jeden Größenwert in der zweiten Spalte der Referenzdatei für alle Übereinstimmungen mit den Größenwerten in der dritten Spalte der Datendatei zu vergleichen. Wenn es eine Übereinstimmung gibt, geben Sie den Offset-Hex-Wert (zweite Spalte in der Datendatei) mit dem Indexwert (erste Spalte in der Referenzdatei) aus. Derzeit ich dies mit dem folgenden Code mache und kochend es nur in eine neue Datei:

#!/usr/bin/python3 

import sys 

ref_file = sys.argv[1] 
dat_file = sys.argv[2] 

with open(ref_file, 'r') as ref, open(dat_file, 'r') as dat: 

    for r_line in ref: 
     ref_size = r_line[r_line.find(' ') + 1:-1] 

     for d_line in dat: 
      dat_size = d_line[d_line.rfind(' ') + 1:-1] 
      if dat_size == ref_size: 
       print(d_line[d_line.find('0x') : d_line.rfind(' ')] 
         + '\t' 
         + r_line[:r_line.find(' ')]) 
     dat.seek(0) 

Die typische Ausgabe sieht wie folgt aus:

0x86ece1eb 0 
0x16ff4628f 0 
0x59b358020 0 
0x27dfa8cb4 1 
0x6f98eb88f 1 
0x102cb10d4 2 
0x18e2450c8 2 
0x1a7aeed12 2 
0x6cbb89262 2 
0x34c8ad5 3 
0x1c25c33e5 3 

Dies funktioniert gut, aber dauert etwa 50 Minuten für die abzuschließen angegebene Dateigrößen.

Es hat seinen Job gemacht, aber als Anfänger bin ich immer daran interessiert, Möglichkeiten zu finden, um meine Programmierung zu verbessern und diese Erkenntnisse zu teilen. Meine Frage ist, welche Änderungen könnte ich machen, um die Leistung dieses Codes zu verbessern?

Answer 1

Da Sie Linien von size in den Akten nachschauen Diese Größen sollten die Schlüssel in jeder Wörterbuchdatenstruktur sein. Dieses Wörterbuch müssen Sie die verschachtelte Schleife loswerden, die hier der wahre Leistungskiller ist. Da Ihre Größen nicht eindeutig sind, müssen Sie außerdem Listen mit offset/index Werten verwenden (abhängig davon, welche Datei im Wörterbuch gespeichert werden soll). Ein defaultdict wird Ihnen helfen, etwas klobig Code zu vermeiden:

from collections import defaultdict 

with open(ref_file, 'r') as ref, open(dat_file, 'r') as dat: 
    dat_dic = defaultdict(list) # maintain a list of offsets for each size 
    for d_line in dat: 
     _, offset, size = d_line.split() 
     dat_dic[size].append(offset) 

    for r_line in ref: 
     index, size = r_line.split() 
     for offset in dat_dic[size]: 
      # dict lookup is O(1) and not O(N) ... 
      # ... as looping over the dat_file is 
      print('{offset}\t{index}'.format(offset=offset, index=index)) 

Wenn die Reihenfolge der Ausgangsleitungen keine Rolle spielt Sie es anders zu tun, um denken, weil Ihr dat_file so viel größer ist und somit den Aufbau der defaultdict aus es verwendet viel mehr RAM.

Answer 2

Sie können folgende tun, nehmen Sie ein Wörterbuch dic und gehen Sie wie folgt (im Anschluss an eine Pseudo-Code, auch gehe ich davon aus Größen nicht wiederholen)

 for index,size in the first file: 
      dic[size] = index 
     for index,offset,size in second file: 
      if size in dic.keys(): 
      print dic[size],offset