Name that Cow

[pixewakb]

Hi,

zu diesem Blogpost würde ich gerne wissen, ob man die Funktion 'treffer_suchen(code,vornamen)' optimieren kann und wenn ja, wie.

Das ist keine Anfrage für Quellcode oder weitere Lösungen, eher wären mir Ratschläge angenehm, wo ich von Benennungsempfehlungen abweiche oder wo ich besser andere Sprachkonstrukte nutzen sollte.

Ich habe ans re-Modul gedacht, dann aber feststellen müssen, dass das nicht auf eine Liste, sondern auf Strings anwendbar ist. Da ich da nicht sehr firm bin, war die kleinschritte Lösung für mich einfach zu implementieren.

[BlackJack]

``line.replace("\n","")`` um *ein* Zeilenende am Ende von `line` zu entfernen würde ich durch `rstrip()` oder zumindest `strip()` ersetzen.

Beim `teffer_suchen()` werden Namen ausgefilter, die Leerzeichen enthalten. Das sollte man vielleich *vorher* machen, denn wenn es keine Möglichkeit gibt das Leerzeichen als Ziffer auszudrücken, dann kann man den Namen auch schon beim einlesen/vorverarbeiten der Liste raus schmeissen.

`list()` bei `vorname` und `code` vor dem Anwenden von `zip()` ist überflüssig. Die `zip()`-Funktion funktioniert mit jedem iterierbaren Objekt, nicht nur mit Listen. Dafür könnte man den Vornamen in komplett in Grossbuchstaben umwandeln statt das für jeden einzelnen Buchstaben zu tun. Wobei auch das etwas wäre was man mit der Namensliste in der Vorverarbeitung tun könnte.

Wenn man den Test für einen einzelnen Namen in eine eigene Funktion steckt, kann man das `match`-Flag loswerden und damit ein wenig einfacher verständlichen Quelltext schreiben, weil man dann sobald das Ergebnis feststeht einfach ``return`` verwenden kann. Die Funktion kann man dann sogar für die `filter()`-Funktion verwenden. Und ``if match == True:`` sollte man einfach als ``if match:`` schreiben, denn `match` ist ja schon genau der Wert, der bei dem Vergleich *wieder* heraus kommt.

Eine Lösung mit `re` hätte man statt Deiner `match`-Geschichte innerhalb der `treffer_suchen()`-Funktion umsetzen können. Denn da hast Du in der Schleife dann ja einzelne Zeichenketten.

Wenn man weiss, dass sich eine Vorverarbeitung der Namen lohnt, weil dann auf diese Daten mehrere Anfragen gemacht werden, würde man sich einen Baum aufbauen wo die Kanten den Ziffern entsprechen und an den Knoten die Namen gespeichert werden, die man auf dem Weg dorthin mit einer Folge von Ziffern erreichen kann. Das dürfte von der Laufzeit für das Prüfen von Seriennummern das effizienteste sein.

[Leonidas]

Da sind viele Kommentare die offensichtliche Sachen kommentieren:

Code: Alles auswählen

if namensliste:        # Wahr, wenn die Liste nicht leer ist!

Code: Alles auswählen

results = [] # Nimmt die Ergebnisse auf

Code: Alles auswählen

    ''' Mainfunktion
 
    '''

Und überhaupt bin ich nicht Fan von inline-Kommentaren, weil die leicht die Zeilenlänge sprengen und irgendwie nie richtig formattiert aussehen. Außerdem nutzt man für Docstrings meist Double-Quotes.

Deine Parameterlisten sind nicht PEP8-Konform.

Außerdem wenn du ein if hast bei dem du ``pass`` stehen hast, kannst du auch einfach die Bedingung bei ``else`` umdrehen. Weil so schauts etwas seltsam aus.

[pixewakb]

@Leonidas: Was meinst du mit folgendem Satz?

Deine Parameterlisten sind nicht PEP8-Konform.

Ich bin in PEP8 auf Anhieb nicht fündig geworden. Denke, du meinst die Parameter beim Funktionsaufruf? Muss ich eine Reihenfolge beachten oder was geht da schief?

Die inline-Kommentare verwende ich momentan inflationär, aber ehrlich gesagt sind einige Dinge für mich noch nicht fest abgespeichert, weshalb ich mir das immer noch mal hintippe - ja, ich versuche das zukünftig zu vermeiden.

@BlackJack: Danke fürs Feedback. Das muss ich mir noch genau ansehen. Die Sache mit dem Baum klingt spannend, scheint mir aber etwas zu hoch. Soweit bin ich noch nicht, das kann ich schlicht (noch) nicht. Den Rest muss ich mir noch ansehen, ob ich das verstehe.

[Leonidas]

@Leonidas: Was meinst du mit folgendem Satz?

Deine Parameterlisten sind nicht PEP8-Konform.

Ich bin in PEP8 auf Anhieb nicht fündig geworden. Denke, du meinst die Parameter beim Funktionsaufruf? Muss ich eine Reihenfolge beachten oder was geht da schief?

Aus

Code: Alles auswählen

def treffer_suchen(code,vornamen):

wird

Code: Alles auswählen

def treffer_suchen(code, vornamen):

Ich sehe das nicht in PEP 8 jetzt explizit erwähnt, aber wenn du dort reinschaust sind die Parameter in den Beispielen *immer* mit Komma und Leerzeichen voneinander getrennt.

[BlackJack]

@pixewakb: Hier ist mal ein PDF, das den Baum für alle Namen aus Deinen Dateien mit maximaler Länge 3 zeigt:code_name_tree_l3.pdf.

[pixewakb]

Ein Link auf ein Tutorial oder eine Infoseite, wo mir das mit den Bäumen erklärt wird oder wo ich mir das Konzept ansehen kann, würde mir wahrscheinlich mehr helfen.

Ich hatte schon überlegt die Vornamen in einzelne Listen zu packen und zwar entsprechend der Länge der jeweiligen Namen, aber das Konzept Kanten und Knoten (Graphentheorie) sagt mir leider nichts -

[Sirius3]

@BlackJack: hier kommt jeder Skriptprogrammierer wieder in Gewissenskonflikte. Wenn man Bäume in Python nachprogrammiert werden sie kaum an die Performance von Dictionaries heranreichen, wenn man also jeden Namen in eine Zahl umwandelt und dann im „Hash-Baum“ speichert. Aber vom Konzept her ist natürlich ein Octalbaum viel schöner.

[BlackJack]

@Sirius3: *Die* Lösung war mir zu einfach. Aber vielleicht ist das ja etwas für pixewakb.

@pixewakb: Puh, eine Webseite mit den gängigen Datenstrukturen kenne ich nicht. Ich habe Bäume mittlerweile in so vielen Büchern zu den verschiedensten Programmiersprachen abgehandelt gelesen, dass ich da nie im Netz nach gesucht habe. Verkettete Listen und Bäume sind die Standardbeispiele an denen bei Büchern zu „low level”-Programmiersprachen Zeigertypen und dynamische Speicherverwaltung erklärt werden. Und dann gibt es noch eine ganze Menge Bücher zum Thema Datenstrukturen bei denen alle möglichen Programmiersprachen verwendet werden. Ob es auch eines mit Python als Implementierungssprache gibt, weiss ich nicht. Das Standardwerk „Introduction to Algorithms” von Cormen, Leiserson, Rivest, und Stein (a.k.a. „der Cormen”) kann man wahrscheinlich nicht jedem zumuten.

Aber Sirius3 hat ja auch einen viel einfacheren Weg angedeutet.

[Leonidas]

Das Standardwerk „Introduction to Algorithms” von Cormen, Leiserson, Rivest, und Stein (a.k.a. „der Cormen”) kann man wahrscheinlich nicht jedem zumuten.

Ich muss da wiedersprechen, gerade den Cormen finde ich von vielen üblichen Informatik-Klassikern die gerne mal empfohlen werden als Lektüre zu verschiedenen Themen ("Wizard-Book", "Dragon-Book", "Tanenbaum", "Paradigms of Artificial Intelligence Programming", "K&R") als sehr gut verständliches Buch welches die Themen recht gut beschreibt ohne in Blabla zu verfallen wie "anschauliche" Bücher das gerne tun.

Aber wie auch immer, was ich empfehlen kann ist ein Ausflug zur nächsten Universitäts-Bibliothek mit Informatikbüchern, die sollten Bücher zu Datenstrukturen ohne Ende haben. Man braucht sich ja die Bücher nicht kaufen, zudem sie ja dann doch teils eher teuer sind.

[nezzcarth]

Noch mal ein allgemeinerer Hinweis:

Hier und z.B. auch bei vielen Ansätzen, Anagramme zu generieren wird immer rein "mechanisch" vorgegangen: man generiert erst mal vor sich hin und schaut dann, was ein valider Name bzw. ein valides Wort ist. Die Annahme ist, dass prinzipiell jede Zeichenkette ein Name/ein Wort sein könnte. Das stimmt so aber nicht; Seriennummern, die z.B. die Zahlenfolge 575 enthalten, werden nur in seltenen Fällen einen Namen erzeugen, den man auch aussprechen kann. Der Grund dafür ist, dass hier drei Konsonanten Grapheme aufeinander folgen. Der Grundbaustein eines Wortes ist die Silbe, und es gibt bestimmte Strukturbedingungen, denen Silben folgen: in den meisten Sprachen sind sie um einen Vokal/Diphthong (Nukleus) aufgebaut, davor können Konsonanten stehen (Onset) und es können welche Folgen (Coda), allerdings auch nicht "beliebig" sondern nach bestimmten Kriterien (s.a. http://de.wikipedia.org/wiki/Sonorit%C3%A4t). Einfache Silbenstrukturen sind z.B. CV, CVC oder VC. Wenn auf dieser Basis Zeichenfolgen generiert, und z.B. C und Q weglässt, erhält man immer etwas, das zumindest aussprechbar ist (http://de.wikipedia.org/wiki/Logatom#Phonologie). In der praktischen Anwendungen hat das einige Nachteile, weil z.B. keine 1:1 Beziehung zwischen Buchstaben und Aussprache bestehen, und viele Aspekte sprachspezifisch sind, aber auf diese Weise hat man evtl. eine Art Heuristik, was überhaupt denkbare Kombinationen sind, und was von vorne herein ausgeschlossen werden kann.

[BlackJack]

@nezzcarth: Prima das jemand mit einem *noch* komplizierterem Ansatz kommt als ich. Die Liste der möglichen Namen liegt als Daten vor. Dein Ansatz könnte sogar verhindern das Namen die darin *enthalten* sind, vielleicht gar nicht als Antwort kommen weil Dein Heuristikansatz diese *gültigen* Daten ausschliesst.

[nezzcarth]

@BlackJack: Für komplizierte Lösungen bin ich immer zu haben

Möglicherweise bin ich da etwas über's Ziel hinausgeschossen, weil ich den Ansatz, das mit einer Liste abzugleichen generell in Frage stelle. Da bei Kühen auch kein Standesamt über die Benennung entscheidet, würde ich sogar einfach nur aussprechbare Zeichenketten nehmen, egal, ob das jetzt "echte" Namen oder Fantasiewörter sind; aber das ist wohl an der Aufgabenstellung vorbei Du hast Recht: wenn man das auf diese Weise löst, fallen eigentlich immer irgendwelche validen Lösungen raus, weil man insbesondere im Bereich der Namen Abweichungen feststellen kann. Die "Güte" der Lösung hängt davon ab, wie man komplex das Modell ist, das man zugrunde legt (das oben skizzierte war stark vereinfachst), und das ist - enn man c.a. zu denselben Ergebnissen kommen möchte, wie mit der "Listenmethode" - sehr komplex.

Was mich halt nur immer etwas wundert bei vielen Lösungen zu sprachlichen Fragestellungen (z.B. auch Algorithmen zur phonetischen Suche) wundert, ist, dass da Wissen über sprachliche Strukturen vollkommen ignoriert wird. Wörter bestehen nicht aus zufällig zusammen gewürftelten Buchstaben, sondern folgen bestimmten, beschreibaren Strukturen, und eine Zeichenkette, die nur aus Konsonanten besteht ist i.d.R. kein wohlgeformtes Wort. Solche - wie ich es oben genannt habe - "mechanischen" Methoden sind in der praktischen Anwendung oft die bessere Wahl, gegenüber Ansätzen, die theoretische Erkenntnisse sauber abbilden, allerdings sollte man meiner Meinung nach schauen, ob man nicht doch etwas davon nutzen kann, um den Suchraum etwas zu verringern.

[pixewakb]

Damit ich das richtig verstehe: Du liest jeden Namen ein, wandelst ihn in den Zahlencode um und fügst dann den Namen dem entsprechenden Key zu, so dass ein Key dann z. B. verschiedene Namen in einer Liste enthält. Je nach Zahlencode werden dann direkt die Ergebnisse aus dem Wörterbuch ausgegeben.

Vorteil: Ich prüfe nicht bei jedem Durchlauf jeden Namen aufs Neue.

Nachteile fallen mir gerade nicht ein. Das ist mit Hashtable gemeint, wenn ich bis hier richtig folge.

[BlackJack]

@pixewakb: Ja, Du folgst richtig. Hashtable nennt sich die Datenstruktur mit der `dict` implementiert ist.