Problem mit der Sortierung von verschachtelten Listen

[htw7448]

Hallo liebe Python-Gemeinde,

ich bin ein ziemlicher Neuling auf dem Gebiet der Programmierung habe aber schon ein wenig Literatur durchgearbeitet und viele viele Beispiele getestet. Leider habe ich nun ein Problem zu lösen wo mir noch der logische Durchblick fehlt.

Ich generiere aus einer Datei eine verschachtelte Liste der Form:

liste = [['nr.1' ,'nr.2', 'text'], ['nr.1', 'nr.2, 'text'] usw.]

• [['6300918', '15277604', '"Hans Meier war da."']
  ['6300919', '15277605', '"Gustav zur Weiterbildung"']
  ['6300918', 15277604', '"geheiratet am Tag x"']]

Problematik: nr.1 soll mit jeder weiteren nr.1 verglichen werden. Bei Gleichheit soll nr.2 mit der nr.2 der Vergleichsliste geprüft werden. Bei erneuter Gleichheit soll dann der Text aus der Vergleichsliste an den Text der Prüfliste angehangen werden und die Vergleichsliste gelöscht werden.

Ziel ist es alle doppelten Einträge nr.1 zu beseitigen und den Text unter einer Nummer zusammen zu fassen.

hier mein nicht funktionierendes Codeschnipsel :/

Code: Alles auswählen

datei = "/temp/liste.csv"

dat = file(datei, 'r')
dat.readline()
print dat

liste = []
kdnr = type(liste).append
for zeile in dat:
	if zeile[-1]=="\n":
		zeile = zeile[:-1]
	eintraege = zeile.split("\t")
	print "Eintraege", eintraege
	kdnr(liste, eintraege)

print len(liste)
print liste[0][0]

for i in liste:
	for i+1 in liste:
		if liste[i][0] == liste[i+1][0]:
			liste[i][2].append liste[i+1][2]
			del liste[i+1]

[BlackJack]

Wenn ich das Problem richtig verstanden habe:

Code: Alles auswählen

from pprint import pprint

def main():
    liste = [['6300918', '15277604', '"Hans Meier war da."'],
             ['6300919', '15277605', '"Gustav zur Weiterbildung"'],
             ['6300918', '15277604', '"geheiratet am Tag x"']]
    
    result = dict()
    for nr_1, nr_2, text in liste:
        result.setdefault((nr_1, nr_2), list()).append(text)
    
    liste = [[nr_1, nr_2, texte] for (nr_1, nr_2), texte in result.iteritems()]

    pprint(liste)

Vielleicht ist aber auch das Dictionary zur Weiterverarbeitung eine geeignete Datenstruktur.

Zum Einlesen solltest Du mal einen Blick in das `csv`-Modul werfen.

[htw7448]

Halle Blackjack,

deine Variante ist um einiges kürzer als meine und sie arbeitet genauso. Vielen Dank, es ist wirklich unglaublich wie kurz man das schreiben kann.


Ich hab meine zwischenzeitlich nochmal überarbeitet - funktioniert nun, ist aber ein Ungetüm .

Code: Alles auswählen

#!/usr/bin/python

datei = "/temp/liste.csv"
dateiout = "/temp/listeout.csv"
inkonsistent = 0
doppelt = 0


dat = file(datei, 'r')
dat.readline()
print dat

liste = []
kdnr = type(liste).append
for zeile in dat:
	if zeile[-1]=="\n":
		zeile = zeile[:-1]
	eintraege = zeile.split("\t")
	print "Eintraege", eintraege
	kdnr(liste, eintraege)

dat.close()
liste.sort()

print "Eingelesene Datei enthält", len(liste) , "Datensaetze!"

for i in range(len(liste)-1):
	for n in range(len(liste)):
		if n == 0:
			continue
		else:
			try:
				if liste[i][0] == liste[(i+n)][0]:
					if liste[i][1] == liste[i+n][1]:
						liste[i][2]= liste[i][2] +'/' + liste[i+n][2]
						del liste[i+n]
						doppelt += 1
						print doppelte, "doppelte Datensaetze gefunden"
					else:
						inkonsistent += 1
						print inkonsistent, " inkonsistente Datensaetze gefunden"
				
			except:
				continue
	print "Ende Vergleich des Datensatzes Nr. : ", i+1
print
print " Ende der Konvertierung. "
print " ", doppelt, " doppelte Datensaetze korrigiert!"
print " ", inkonsistent, " inkonsistente Datensaetze gefunden "

Welche Vorteile sollte mir das csv-Modul bringen? Ich arbeite doch nur mit Tabstop Zeichen und EOL Markierung (OpenOffice CSV-Export). Momentan habe ich noch ein Problem mit dem Import, weil man im OO keine freie Delimiterwahl hat und Tabstops, Kommata usw. in den Texteinheiten benutzt wurden sind.

Das Zeilenformat sieht so aus: Zahl "\t" Zahl "\t" "Text""\n". Leider ist der Text mit Tabstops usw verseucht. Werde mir dann mal das re-Modul anschauen.

[BlackJack]

Welche Vorteile das `csv`-Modul bringt hast Du im Grunde schon selbst geschrieben: Deine Methode funktioniert nicht wirklich.

Und das `csv`-Modul mit regulären Ausdrücken selber zu implementieren ist fehleranfällig und unnötig.

CSV-Dateien sind nicht nur durch ein spezielles Zeichen getrennte Spalten, sondern es gibt auch Begrenzungszeichen die dieses spezielle Zeichen, Zeilenumbrüche und sich selbst schützen können. Das `csv`-Modul kann das schon alles.

[htw7448]

Ok das leuchtet mir ein, danke Blackjack.

[htw7448]

Nun da der Kern der kleinen Anwendung steht würde ich gern noch ein grafisches Interface dafür bastelt. Was ist für den Anfänger besser geeignet: gtk oder tk? Die Anwendung soll nur ein Textfeld für die Ausgabe und ein Dateibrowser-Dialog haben.

@ Blackjack: Kann man sich mit einem Trick die Anzahl der gefunden Übereinstimmungen in Nr1 und nr_2 bzw. die Übereinstimmung in nr_1 aber nicht in nr_2 ausgeben lassen?

Code: Alles auswählen

import csv


def main(pfad, file):
	reader = csv.reader(open(pfad +"/" +file, "rb"))
	liste = []
	for row in reader:
		liste.append(row)
     
     	result = dict()
     	for nr_1, nr_2, text in liste:
         	result.setdefault((nr_1, nr_2), list()).append(text)
     
     	liste = [[nr_1, nr_2, texte] for (nr_1, nr_2), texte in result.iteritems()]

	for i in liste:
		i.append(" ,".join(i[2]))
		del i[2]
	
	writer = csv.writer(open(pfad +"/" +file[:-4] +"_export.csv", "wb"))
	writer.writerows(liste)
     

datei = "lysi_test.csv"
pfad = "/home/steve"
main(pfad, datei)

[BlackJack]

Anmerkungen zum Quelltext:

Man sollte keine Namen von eingebauten Funktionen an eigene Objekte binden. Aus `file` habe ich weiter unten `filename` gemacht.

Dann sollte man Dateien die man geöffnet hat, auch explizit wieder schliessen.

Dein Programm hat eine furchtbare Laufzeit weil Du das zusammenfassen immer wieder auch auf allen bisher schon gelesenen und zusammengefassten Zeilen durchführst. Das ist quadratische Laufzeit.

Die `liste` braucht man gar nicht bevor die ganze Datei eingelesen wurde. Die Elemente, die der `csv.reader()` liefert, sind schon in der richtigen Form um sie in der ``for``-Schleife zu benutzen.

Die zweite, etwas umständliche ``for``-Schleife kann man eleminieren, wenn man das Zusammenfassen der Texte schon beim erstellen der `liste` erledigt.

Code: Alles auswählen

import csv 
import os

def main(pfad, filename):
    csv_file = open(os.path.join(pfad, filename), 'rb')
    
    result = dict()
    for nr_1, nr_2, text in csv.reader(csv_file):
        result.setdefault((nr_1, nr_2), list()).append(text)
    
    csv_file.close()

    liste = [[nr_1, nr_2, ' ,'.join(texte)]
             for (nr_1, nr_2), texte in result.iteritems()]
    
    csv_file = open(os.path.join(pfad, os.path.splitext()[0] + '_export.csv'),
                    'wb')
    writer = csv.writer(csv_file) 
    writer.writerows(liste)
    csv_file.close()

Ich weiss nicht so recht was für Zahlen Du genau haben möchtest, aber dafür braucht man keinen Trick sondern eine Mischung aus Datenstruktur und Algorithmus um die Zahlen zu ermitteln.

[htw7448]

Danke für die sehr hilfreiche Antwort. DIe beiden ersten Fehler fallen in die Kategorie gewusst aber nicht beachtet .

Die lineare komprimierte Programmierung ist für mich als Anfänger allerdings eine harte Nuss. Aber Übung macht den Meister! Zu dem Zähler für Zeilen doppelter Übereinstimmung in den Nummern und den für einfache Übereinstimmung werde ich mir mal selbst den Kopf zerbrechen .

Ich glaube das Argument filename für die Splitfunktion fehlt oben.

Code: Alles auswählen

csv_file = open(os.path.join(pfad, os.path.splitext(filename)[0] + '_export.csv'), 'wb')

[BlackJack]

Ups, stimmt, der `filename` fehlte.

[htw7448]

Ich glaub der Schlüssel zum Verständnis liegt in der Zeile:

Code: Alles auswählen

for nr_1, nr_2, text in csv.reader(csv_file):
        result.setdefault((nr_1, nr_2), list()).append(text)

Mir ist inzwischen klar das es die performanteste Lösung ist, gleiche Listeneinträge durch das Konvertieren in ein ´´dict´´ zu eleminieren, da dort jeder Schlüssel einmalig ist.

Mit

Code: Alles auswählen

(nr_1, nr_2)

wird die nr_1 und nr_2 einem Tupel welches als Schlüssel dienen soll zugewiesen.

wie

Code: Alles auswählen

list()).append(text)

in dieser for Schleife arbeitet ist mir allerdings schleierhaft. Ich kann dazu
leider auch nichts im www finden. Das ´´append´´ bewirkt doch ein einfaches Anfügen der neuen ´´dict´´ Einträge bei jedem Durchlauf?! Aber
welche Funktion erfüllt dann das ´´list()´´? Ist es nicht so das der jeweils letzte Datensatz mit gleichem Key als aktuell angesehen wird und die vorherigen Datensätze damit überschrieben werden?

[BlackJack]

Du musst ein bisschen auf die Klammern achten ─ der Teil der Dir nicht klar ist, gehört nicht unmittelbar zusammen. Das ``list())`` gehört noch zum Aufruf von der `setdefault()`-Methode und das ``.append(text)`` wird auf das Ergebnis dieser Methode angewendet.

`setdefault()` schaut im Dictionary nach dem ersten Argument und gibt das Ergebnis zurück. Ausser wenn das erste Argument gar nicht als Schlüssel in dem Dictionary vorkommt, dann wird das zweite Argument in das Dictionary eingetragen und zurückgegeben.

Also entweder gibt es für so ein Nummerntupel schon eine Liste im Dictionary, an die dann der `text` angehängt wird, oder es wird eine leere Liste in das Dictionary eingetragen und daran wird dann der Text angehängt.

[htw7448]

Das filtern der Nummern gestaltet sich schwieriger als gedacht.

Grundproblem: Ich habe sowohl horizontal als auch vertikal Eigenschaften zu zählen. Zum einen ist ein Datensatz nur dann korrekt wenn er sowohl eine Angabe bei nr_1 als auch nr_2 enthält. Zusätzich sollen alle Datensätze (Zeilen) die eine identische nr_1 und nr_2 aufweisen gezählt werden (entspricht Anzahl doppelter Einträge). Die Zahl der fehlerhaften Datensätze entspricht dann der Anzahl der Zeilen aus csv_file - der korrekten Datensätze.

count1 = Anzahl der doppelten Datensätze
count2 = Anzahl der korrekten Datensätze
count3 = Anzahl der Zeilen der Datei
count 3 - count2 = Anzahl der fehlerhaften Datensätze

bsp:

1, 2, text1
7, 8, text2
, 9, text3 - fehlerhaft, da nr_1 fehlt
1, 4, text4 - fehlerhaft da nicht mit Zeile 1 übereinstimmende nr_2
7, 8, text5 - doppelter Datensatz (wird durch ´´dict()´´ Funktion zusammengeführt

Problem:

innerhalb der for Anweisung sind mir die Hände gebunden. Alles was ich bis jetzt hinbekommen habe, ist ein Zählen der Häufigkeiten von nr_1 und nr_2. Damit allein kann ich nichts überprüfen.

Code darunter - hab auf dem falschen System geschrieben .[/code]

[htw7448]

Code: Alles auswählen

import csv
import os
 
def main(pfad, filename):
     csv_file = open(os.path.join(pfad, filename), 'rb')
     
     result = dict()
     print len(csv_file)

     for nr_1, nr_2, text in csv.reader(csv_file):
         result.setdefault((nr_1, nr_2), list()).append(text)
     csv_file.close()
     
     csv_file = open(os.path.join(pfad, filename), 'rb') # keine Ahnung ob man im csv-Modul den Cursor wieder auf 0 setzen kann/Doku schweigt sich aus
     frq_nr_1=  dict()
     for nr_1, nr_2, text in csv.reader(csv_file):
	 frq_nr_1[nr_1] = frq_nr_1.get(nr_1, 0) +1
     print frq_nr_1
     csv_file.close()
     
     csv_file = open(os.path.join(pfad, filename), 'rb') 
     frq_nr_2=  dict()
     for nr_1, nr_2, text in csv.reader(csv_file):
	 frq_nr_2[nr_2] = frq_nr_2.get(nr_2, 0) +1
     print frq_nr_2
     csv_file.close()


     liste = [[nr_1, nr_2, ' ,'.join(texte)]
              for (nr_1, nr_2), texte in result.iteritems()]

     csv_file = open(os.path.join(pfad, os.path.splitext(filename)[0] + '_export.csv'), 'wb')

[BlackJack]

Wenn ich das richtig verstanden habe, ist die erste Nummer schon ein eindeutiger Schlüssel? Dann könnte man die zweite mit in den Wert packen und nicht mehr bedingungslos einen Text anhängen, sondern erst testen ob die zweite Nummer übereinstimmt.

Der folgende Quelltext zählt alle gelesenen Zeilen, die kaputten, also solche die nicht beide Nummern besitzen und solche bei denen die zweite Nummer nicht gleich ist.

Die Anzahl der Doppelten wird danach aus den Werten im Dictionary ermittelt.

Code: Alles auswählen

import csv
import os
from itertools import count, izip


def main(filename):
    csv_file = open(filename, 'rb')
    
    broken_rows = 0
    records = dict()
    for row_nr, (nr_1, nr_2, text) in izip(count(1), csv.reader(csv_file)):
        if not (nr_1 and nr_2):
            broken_rows += 1
            continue
        subkey, record = records.setdefault(nr_1, (nr_2, list()))
        if subkey != nr_2:
            broken_rows += 1
            continue
        record.append(text)
    
    csv_file.close()
    
    doubles = sum(len(texts) - 1 for  dummy, texts in records.itervalues())
    
    print '    Gesamtzeilen:', row_nr
    print 'davon fehlerhaft:', broken_rows
    print '         korrekt:', row_nr - broken_rows
    print '         doppelt:', doubles

    result = ((nr_1, nr_2, ', '.join(texts))
              for nr_1, (nr_2, texts) in records.iteritems())
    
    out_filename = os.path.splitext(filename)[0] + '_export.csv'
    csv_file = open(out_filename, 'wb')
    writer = csv.writer(csv_file)
    writer.writerows(result)
    csv_file.close()

if __name__ == '__main__':
    main('test.csv')

[htw7448]

Das Script funktioniert.

die Funtionsweise im Bereich:

Code: Alles auswählen

if subkey != nr_2:
            broken_rows += 1
            continue
        record.append(text)

ist mir etwas schleierhaft. Woher soll PYthon denn wissen welche nr_2 noch alle kommen beim Schleifendurchlauf. Ein print der Variable results ergibt ordnungsgemäß ein bei jedem Durchlauf gefüttertes ´´dict´´. Die beiden Variablen subkey und record enthalten ja auch nur die Daten der aktuellen Zeile.

[BlackJack]

Das Programm weiss an der Stelle nicht was noch für `subkey`\s kommen. Das erste gelesene Nummernpaar wird als korrekt angesehen, alle folgenden Abweichungen als Fehler.

Wenn also das Erste das wirklich fehlerhafte Nummernpaar war, dann gibt's eine Menge "falsche Fehler". Aber das ist etwas was man auch mit Kenntnis aller Nummernpaare nicht sauber entscheiden kann. Mal angenommen man hat (1,23) und (1,42) und keine anderen die mit 1 beginnen, welches ist jetzt das richtige und welches das fehlerhafte? Fügen wir noch ein (1,0) hinzu. Wat 'nu? Oder ein (1,42) ─ haben wir jetzt zwei fehlerhafte und ein richtiges oder ein fehlerhaftes und zwei richtige?

[htw7448]

Du hast Recht BlackJack,

natürlich ist es an der Stelle sinnvoll das erste kommende komplette Paar als richtig anzusehen. Anders geht es nicht. Die einzige Möglichkeit wäre ein Zählen der Häufigkeit der Zahlenpaare.

Das wäre an dieser Stelle aber auch nicht besonders sinnvoll da man dann auch nur die Wahrscheinlichkeit eines falschen Datensatzes minimieren aber nicht ausschließen könnte. Da ist dann eben der Mensch gefragt . Evtl. werde ich das so Einrichten das eben die fehlerhaften Datensätze in einem anderen ´´dict´´ eingefügt werden um sie dann mit einer Leerzeile im csv-File anzuhängen.