[Algorithmik] 6stellige Zahlen aus einem string filtern.

[SPUTNiK]

Hallo zusammen,

ich habe aus Langeweile den nachfolgenden code geschrieben um alle sechsstelligen Zahlen aus einem string zu filtern. Er tut seinen job, nur ist er meiner Meinung nach ziemlich lame und schlecht erweiterbar noch dazu (sodass beispielsweise auch weitere x-stellige Zahlen gefiltert werden können).

Deshalb meine Frage an euch: Wie würdet Ihr das Problem (ohne RegEx) lösen?

Code: Alles auswählen

def isdigit(value):
 if((value>="0") and (value<="9")):
  return 1
 else:
  return 0

string = "ABC156458ABC01234567ABCABC431747ABC61"
x = list(string + ".")

for i in range(0, len(x)):
 if isdigit(x[i]):
  if isdigit(x[i+1]) and isdigit(x[i+2]) and isdigit(x[i+3]) and isdigit(x[i+4]) and isdigit(x[i+5]) and isdigit(x[i+6]):
   x[i+1]=x[i+2]=x[i+3]=x[i+4]=x[i+5]=x[i+6]="::"

  elif (isdigit(x[i+1]) and isdigit(x[i+2]) and isdigit(x[i+3]) and isdigit(x[i+4]) and isdigit(x[i+5])) and (x[i-1] != "::"):
   
   print "Hit:" + x[i]+x[i+1]+x[i+2]+x[i+3]+x[i+4]+x[i+5]
   x[i+1]=x[i+2]=x[i+3]=x[i+4]=x[i+5]="."

[EyDu]

Code: Alles auswählen

>>> import re
>>> re.findall("(?=(\d{6}))", "ABC156458ABC01234567ABCABC431747ABC61")
['156458', '012345', '123456', '234567', '431747']  

Edit: Vielleicht noch ein paar Anmerkungen:
- Der Beitrag hat nicht so richtig etwas mit Algorithmik zu tun
- Deine isdigit-Funktion hat gleich mehrere Probleme:
* zum einen ist sie überflüssig, da Strings bereits eine Methode isdigit besitzen. Die sollte man nicht noch einmal implementieren.
* Der Test ist auch nicht besonders klug. Was ist, wenn der Benutzer "0a" übergibt. Bei dir kommt dann raus, das es sich um eine Ziffer handelt
* Es gibt True und False, dafür sollten nicht 1 und 0 gebraucht werden.
* Die Klammern beim if sind überfüssig und sollten weggelassen werden
- Weiter solltest du nichts an den Namen ``string`` binden, da es sich um einen vorhandenen Typen handelt, welchen du damit verdeckst.
- Konstanten werden in Python durchgängig groß geschrieben (schaue dir mal PEP 8 an)
- Das ``x = list(string + ".")`` ist unnötig, was willst du damit bezwecken?
- wenn du ``for i in range(0, len(x)):`` verwendest, dann machst du etwas falsch. Zum einen ist die 0 als Startwert überflüssig, zum anderen solltest du ``enumerate`` verwenden, wenn du den index brauchst.
- Wenn du anfänst zu nummerieren oder immer das selbe Muster schreibst (+1, +2, +3, ...) dann machst du etwas falsch. Da solltest du generischer arbeiten, zum Beispiel mit Listen, Tupeln oder, in diesem Fall, mit einer Schleife. Insgesamt ist an dem Code sehr viel redundant.
- Außerdem sollte eine Zeile nicht mehr als 80 Zeichen haben.

Sebastian

[BlackJack]

@SPUTNiK: Ohne regulären Ausdruck würde ich das gar nicht lösen, denn so einer wäre hier die einfachste, kompakteste und wohl auch sehr nachvollziehbare und verständliche Lösung. Dein's verstehe ich auf Anhieb nicht so ganz und es ist voll von Wiederholungen die eigentlich in eine Schleife gehören. Insbesondere wenn es auch auf andere Längen als sechs parametrisierbar sein soll.

In Python wird per Konvention um vier Leerzeichen pro Ebene eingerückt. Es gibt die Wahrheitswerte `True` und `False` die man anstelle von 1 und 0 verwenden sollte. Bei `isdigit()` sind dann auch das ``if`` und die beiden expliziten ``return``-Anweisungen unnötig, weil die Bedingung selbst ja schon zu einem Wahrheitswert ausgewertet wird. Den kann man auch einfach zurück geben. Ausserdem sind die Klammern um die Bedingung insgesamt als auch um die beiden Teilausdrücke überflüssig. Das ``and`` kann man sich an der Stelle auch sparen, weil man Vergleichsoperatoren verketten kann. Übrig bleiben würde dann ``return '0' <= value <= '9'``. Aber man könnte auch einfach die `isdigit()`-Methode auf Zeichenketten aufrufen und sich die eigene Funktion damit komplett sparen.

[problembär]

Code: Alles auswählen

#!/usr/bin/env python
# coding: iso-8859-1

s = "ABC156458ABC01234567ABCABC431747ABC61"
a = ""
x = 0
for i in range(len(s)):
    if s[i].isdigit():
        a += s[i]
        x += 1
        if x == 6:
            if i == len(s) - 1 or not s[i + 1].isdigit():
                print "Hit: " + a
                a = ""
                x = 0
    else:
        a = ""
        x = 0

Aber die RegEx ist schon recht cool.

[lunar]

@SPUTNiK: Wenn unbedingt ohne reguläre Ausdrücke, dann vielleicht so:

Code: Alles auswählen

def find_numbers(s, digits):
    groups = (s[i:i+digits] for i in xrange(len(s)))
    return [g for g in groups if len(g) == digits and g.isdigit()]

Aufzurufen wie folgt:

Code: Alles auswählen

In [8]: s = 'ABC156458ABC01234567ABCABC431747ABC61'

In [12]: find_numbers(s, 6)
Out[12]: [u'156458', u'012345', u'123456', u'234567', u'431747']

Es mag andere, elegantere Lösungen geben. Problembärs Lösung ist allerdings keine gute Lösung, sondern C in Python-Syntax.

[BlackJack]

@EyDu, @lunar: Euer Code findet überlappende Zifferngruppen, das Original nicht, weil dort gefundene Ziffern durch '.' ersetzt werden und damit nicht mehr Teil weiterer Treffer sein können.

[EyDu]

Ehrlich gesagt, habe ich mir nicht angeschaut, was genau oben rauskommen soll. Ich bin einfach vom allgemeinsten Fall ausgegangen. Ohne Überlappungen ist es ja nur noch einfacher.

[lunar]

@BlackJack: Und ich habe mir wiederum nur cofis Ausdruck angesehen, ohne das Original weiter zu beachten, es war mir viel zu konfus.

@cofi: Die Lösung ohne reguläre Ausdrücke wird komplizierter, da man bei Ausschluss überlappender Ziffernfolgen die Ausdehnung der letzten Ziffernfolge berücksichtigen muss. Ergo hat man Zustände und kann nicht mehr so schöne geschlossene Ausdrücke aufstellen. Zumindest fällt mir keine Lösung ein, die nur mit Generatorausdrücken, LCs und itertools auskäme…

[cofi]

@lunar: Ich bin unschuldig, das hat EyDu alleine verbrochen

[lunar]

@cofi: Oh, das tut mir leid. Keine Ahnung, wie ich auf Dich kam, ich hoffe, Du siehst mir diesen Fauxpas nach

[cofi]

@lunar: Keine Sache

[SPUTNiK]

Uff, vielen Dank für die zahlreichen Antworten! Wie man sieht bin ich blutiger Anfänger und darf mir nun erstmal alles zu Gemüte führen und verinnerlichen. 

Das die isdigit() Methode existiert ist mir bekannt. Die fehlerhafte Funktion ist beim herumexperimentieren entstanden und im Script verblieben, wo sie letztendlich doch für etwas gut war

Btw. Ich habe bei dem Script von problembär ein kleines Verständnisproblem. Wie genau wird die 12. Zeile interpretiert? Der zweite Teil ist mir schlüssig,, doch was hat es mit dem ersten auf sich?

LG Jack

[webspider]

Btw. Ich habe bei dem Script von problembär ein kleines Verständnisproblem. Wie genau wird die 12. Zeile interpretiert? Der zweite Teil ist mir schlüssig,, doch was hat es mit dem ersten auf sich?

Solltest du tatsächlich das ``if i == len(s) - 1`` meinen: Da i in der Schleife dem aktuellen Index entspricht und len(s) - 1 der letzte mögliche Index ist, wird mit diesem Vergleich lediglich überprüft ob das Ende erreicht wurde. Ehrlich gesagt fand ich ihn verständlicher als den zweiten Teil der Bedingung. Aber gut, wirklich verständlich ist es sowieso nicht in dem Stil Python-Programmierung zu betreiben.

[SPUTNiK]

Ohje, das -1 hat mich die ganze Zeit ziemlich irritiert. Ich dachte len(s)-1 (in dem Fall 28) wäre der zweitletzte Index da der string aus 29 Zeichen besteht und print len(s) ebenfalls 29 ausgibt. Das hat bei mir irgendwie verdrängt das der erste Index 0 ist und nicht 1 *facepalm.

[problembär]

Ohje, das -1 hat mich die ganze Zeit ziemlich irritiert. Ich dachte len(s)-1 (in dem Fall 28) wäre der zweitletzte Index da der string aus 29 Zeichen besteht und print len(s) ebenfalls 29 ausgibt. Das hat bei mir irgendwie verdrängt das der erste Index 0 ist und nicht 1 *facepalm.

Daß der Index von Listen (oder Arrays) bei 0 und nicht bei 1 beginnt, ist seit vielen Jahren eines der Hauptschwierigkeiten für Programmierer, verursacht oft Fehler, und es wird für viele Sprachen diskutiert, ob das so beibehalten werden soll (siehe z.B. Google zu "array index start"). Man hat es aber trotzdem nicht geändert und wird es daher wohl auch nicht mehr.

Code: Alles auswählen

if i == len(s) - 1 or not s[i + 1].isdigit():

Mein Code prüft ja auf 6 Zahlen nacheinander, und dann, ob das Zeichen danach auch eine Zahl ist oder nicht. Wenn man am Ende des Strings ist, ist das Zeichen danach sicher keine Zahl mehr, aber es existiert auch gar nicht, daß heißt, es darf dann auch nicht zu der Überprüfung dieses nichtexistenten Zeichens kommen, sonst würde es einen Fehler geben ("list index out of range"). Daher "if i == len(s) - 1" zuerst. Wenn dies "True" ist, wird der Code-Block darunter ausgeführt, ohne daß der Teil hinter dem "or ..." noch geprüft wird (wichtig, sonst wie gesagt Error).
"s[i + 1].isdigit()" gibt "True" zurück, wenn das nachfolgende Zeichen eine Ganzzahl ist, sonst "False".
Man könnte also auch

Code: Alles auswählen

if ... s[i + 1].isdigit() == False:

schreiben,

Code: Alles auswählen

if ... not s[i + 1].isdigit():

ist eine Verkürzung, die - in diesem Fall - dasselbe macht (es gibt dazu ein paar Einzelheiten, dazu siehe bei Interesse die Diskussion hier).

Wenn man in einer if-Bedingung einen Ausdruck hat, kann man den einfach so stehen lassen und auf die Auswertung zu "wahr" oder "falsch" testen, siehe hier.
Z.B. wird eine ganze Zahl wie 5 zu "wahr" ausgewertet. Man kann dann also schreiben:

Code: Alles auswählen

if 5:
    print "Ausdruck wahr"

Ebenso, wenn eine Funktion einen solchen Wert wie "True" zurückgibt.

Code: Alles auswählen

if "5".isdigit():
    print 'Der String "5" enthält eine Ganzzahl.'

umgekehrt

Code: Alles auswählen

if not "a".isdigit():
    print 'Der String "a" ist keine Ganzzahl.'

Hoffe, die Zeile in dem Skript wird Dir so ein bißchen verständlicher.

So, und da die anderen Leute hier meine Erklärungen normalerweise nicht leiden können, bin ich jetzt raus hier, SPUTNiK weitere Fragen an mich bitte ggf. per PN.

[BlackJack]

@problembär: Wenn der Index bei 1 beginnt verursacht das oft Fehler, genau deswegen beginnt er ja bei fast allen Sprachen bei 0. Das ist das Ergebnis von rationalen Diskussionen mit Argumenten und Beobachtung von Fehlern die eben bei 1-basierten Sequenztypen deutlich häufiger auftreten, weil man da deutlich häufiger in Berechnungen eins abziehen oder addieren muss um an die richtige Stelle im Speicher zu kommen.

[EyDu]

Das Index-"Problem" wurde doch von Dijkstra schon vor 30 zufriedenstellend gelöst und ich musste wirklich überlegen, welche Sprache noch mit 1 anfangen. Eingefallen sind mir lediglich Lua und MATLAB. Bei letzterem würde ich davon ausgehen, dass die 1 beibehalten wurde, da es in der Mathematik so üblich ist. Dieses Thema als eine der "Hauptschwierigkeiten" für Programmierer zu bezeichnen ist aber etwas seltsam. Wenn das eines meiner Hauptschwierigkeiten wäre, dann würde ich mir über meine Berufswahl echte Gedanken machen. Oder liegt hier etwa der Unterschied zwischen Informatikern und Programmierern?

[nomnom]

@lunar: Du hättest einfach die „xrange“ verkleinern können, statt für jede Zahl zu prüfen, ob sie die richtige Länge hat:

Code: Alles auswählen

def find_numbers(s, digits):
    return [s[i:i+digits] for i in xrange(len(s)-digits+1) if s[i:i+digits].isdigit()]

[lunar]

@nomnom: Stimmt, daran habe ich nicht gedacht… Danke

[snafu]

Daß der Index von Listen (oder Arrays) bei 0 und nicht bei 1 beginnt, ist seit vielen Jahren eines der Hauptschwierigkeiten für Programmierer, verursacht oft Fehler, und es wird für viele Sprachen diskutiert, ob das so beibehalten werden soll (siehe z.B. Google zu "array index start").

Wenn man die von dir vorgeschlagene Googlesuche durchführt, dann stößt man auf ein paar Fragen zu dem Thema, die vermutlich von Programmieranfängern gestellt wurden, sowie auf einen Blogeintrag mit einigen Erläuterungen, warum diese Regelung insbesondere aus logisch-mathematischer Sicht praktikabel und daher sinnvoll erscheint. Jedenfalls nichts, was die von dir aufgestellten Behauptungen wirklich stützen würde...

So, und da die anderen Leute hier meine Erklärungen normalerweise nicht leiden können, bin ich jetzt raus hier, SPUTNiK weitere Fragen an mich bitte ggf. per PN.

Weitere Fragen bitte gerne weiterhin öffentlich stellen, damit man nicht nur die Meinung eines Einzelnen hören muss, der nicht ohne Grund desöfteren für seine Aussagen und Haltung (in aller Regel auf inhaltlicher Ebene) in diesem Forum kritisiert wird. Verschiedene Meinungen zu einem Thema geben erfahrungsgemäß einen deutlichen besseren Überblick, um eine Fragestellung möglichst zufriedenstellend beantwortet zu bekommen.