Laufzeit Problem

[frosch]

Hi,

mein Programm soll 2 Listen mit einander vergleichen und jene Zeile ausgeben, wo die ID2 in Liste1 größer ist als in Liste2. Die ID1, von und bis sind aber ident.

Liste 1:
ID1 von bis ID2
| 101|01.01.2006|31.12.2006| 5|
| 105|01.01.2008|31.12.2008| 1|
| 107|01.01.2006|16.05.2006| 3|
| 1107|01.01.2006|30.05.2006| 3|

Liste 2:
ID1 von bis ID2
| 101|01.01.2006|31.12.2006| 3|
| 105|01.01.2008|31.12.2008| 1|
| 107|01.01.2006|16.05.2006| 2|
| 1107|01.01.2006|30.06.2006| 3|


Hier mein Code:

Code: Alles auswählen

datei1 = str(eing1.get()) 
  in_T5 = open(datei1,'rU') 
  datei2 = str(eing2.get())
  in_ZZT = open(datei2,'rU')
  out_f1 = file (str(eing3.get()) , 'w') 
  listT5 = list() 
  listZZT = list()
  i = 1


  for line in in_T5:
	text = line
	for line in text.split('\n'): 
		try:
			pernr, von, bis, id = (x.strip() for x in line[1:-1].split('|'))
		except ValueError:
			pass
		else:
			if pernr and von and bis and id:
				listT5.append((pernr, von, bis, id))

 
  for line in in_ZZT:
	text = line
	for line in text.split('\n'): 
		try:
			pernr, von, bis, id = (x.strip() for x in line[1:-1].split('|'))
		except ValueError:
			pass
		else:
			if pernr and von and bis and id:
				listZZT.append((pernr, von, bis, id))
    
	
  while i < len(listZZT):
	if listT5[i][0] == listZZT[i][0]:
		if listT5[i][3] > listZZT[i][3]:
			if listT5[i][1] == listZZT[i][1]:
				if listT5[i][2] == listZZT[i][2]:
					write.out_f1("%s |" % listT5)

Mein Problem ist, dass sie Laufzeit schon bei wenigen Einträgen in der Liste (ca. 100) sehr lange ist.
Das Programm sollte aber Listen mit bis zu 20.000 Einträgen in akzeptabler Zeit verarbeiten können. Kann mir bitte jemand helfen die Laufzeit dieses Programmes zu verbessern.

Dank im Voraus
FROSCH

[Rebecca]

Deine ganzen Schleifen sehen ja abenteuerlich aus, ich hab's jetzt nicht so genau angeschau... Setze mal folgende Idee um: Gehe einmal durch die erste Liste, erstelle dabei ein Dictionary mit den ID1 als Schluessel und dem Rest als Wert (als Tupel oder Liste). Gehe dann einmal durch die zweite Liste und vergleiche dabei jede Zeile mit dem Wert aus dem Dict.

[Rebecca]

So etwa:

Code: Alles auswählen

d = {}

with open("/tmp/l1") as f:
    for line in f:
        columns = line.split("|")[1:-1]
        d[columns[0]] = columns

with open("/tmp/l2") as f:
    for line in f:
        if line.startswith("ID"): continue
        columns =  line.split("|")[1:-1]
        if int(d[columns[0]][-1]) > int(columns[-1]):
            print line

[b.esser-wisser]

Wenn sich bei den Listen wirklich nur das letzte Feld 'ID 2' unterscheidet, mach es doch in einer Schleife (stichw. zip(), str.rsplit())...

edit: rsplit natürlich

[Rebecca]

Stimmt, wenn die Menge und die Reihenfolge der Zeilen gleich bleibt...

[sma]

Ich würde ja sagen, das while in Zeile 36 terminiert nie, denn weder i noch listZZT ändern sich in der Schleife.

[b.esser-wisser]

@sma: Das wäre die beste Erklärung für die lange Laufzeit Der Code läuft so aber sowieso nicht (Einrückung), von daher ....

[frosch]

Hallo,

danke für eure zahlreichen Antworten. Leider habe ich feststellen müssen, dass die beiden Listen unterschiedlich lang sein können. Weiters kann es zu einer ID1 mehrere ID2 Einträge geben. Dies kann in beiden Listen vorkommen.
z.B.:
194| 01.01.2006| 31.12.2006| 1
194| 01.01.2006| 31.12.2006| 2
194| 01.01.2006| 31.12.2006| 4
194| 01.01.2006| 31.12.2006| 5

Als Python und Programmier Anfänger bin ich nun etwas ratlos, wie ich am effektivsten abfragen, ob die ID2 in Liste 1 für jeweilige ID1 ist?

Dank im Voraus
FROSCH

[Rebecca]

wie ich am effektivsten abfragen, ob die ID2 in Liste 1 für jeweilige ID1 ist?

Liegt's an mir oder ist die Fragestellung etwas wirr? Hast du dir meinen Code mal angeschaut und ausprobiert? Wenn man an der richtigen Stelle noch ein Try/Except einfuegt, sollte er das tun was du willst...

[b.esser-wisser]

Nö, ich versteh die Frage auch nicht.
@OP:
- Was hast du da? (Was steht in diesen Listen(CSV-Dateien?), wo kommen die her?)
- Was willst du? (Beschreibe In Worten, ohne die Worte 'Listen', 'IDn).
Du schreibst, die Listen können unterschiedlich lang sein: was dann?

hth, Jörg

[ms4py]

Du willst ja immer nur die höchste ID2 der jeweiligen ID1 vergleichen, sehe ich das richtig?
Dann würde ich folgende Datenstruktur und Vorgehensweise vorschlagen:

Datenstruktur:
- Dictionary mit ID1 als Key und als Wert ein eigener Datentyp
- Dieser Datentyp enthält: ID2, Nummer der Liste, Zeilennummer

Vorgehensweise:
- Zuerst füllst du das Dictionary Zeile für Zeile von Liste2 und dann Liste1, wobei du nur einen Wert überschreibst, wenn die ID2 der aktuellen Zeile größer ist als die bereits im dict hinterlegte
- Dann gehst du das dict durch und gibst alle Einträge aus, in der Liste 1 eingetragen ist. Dabei hast du ja dann auch Zugriff auf die zugehörige Zeilennummer.