ChickenLipsRfun2eat
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Hallo zusammen! Ich bin im Zuge von pathlib und os.path.expandvars(x) über die Frage gestolpert, wie man am besten auf Zeichen innerhalb eines String-Literals prüft. In den Beispielen, bzw. der Herkunft der Frage ist klar, dass ich effektiv auf das erste Zeichen prüfen könnte, ich spiele aber mit dem Gedanken da gleich einen Rahmen für ein gezieltes char_replace draus zu machen, welches ich per map („Übersetzungsliste“) dann woanders verwenden könnte. Das Ergebnis sollte also unabhängig von den ursprünglichen Umgebungsvariablen und Shell-Builtins funktionieren mit einer freien Liste an unicode(!)-chars. Beispiel:
| check = ['$','~','!','…']
string1 = "$HOME/Pfad/Zum/Ziel"
string2 = "~/Pfad/Zum/Ziel"
string3 = "relativer/Pfad/Zum/!Ziel"
string4 = "noch/…ein/~Sonderzeichen/!Pfad"
#ermitteln kann ich das ganze nun mit bspw.
[c for c in check if c in stringN]
|
Da kommt dann entweder leer/false raus, wenn keins der Zeichen enthalten ist oder eine Liste mit den enthaltenen Zeichen. Soweit, so gut. Aber: Gibt es da effektivere, mehr „pythonische“ Wege als die beiden gegenseitigen Loops zu durchlaufen?
|
Nobuddy
Anmeldungsdatum: 2. September 2005
Beiträge: 6896
Wohnort: 29614 Soltau
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | #!/usr/bin/env python
# _*_ coding: utf_8 _*_
# For Python3.x
import os
string1 = "$HOME/Pfad/Zum/Ziel"
string2 = "~/Pfad/Zum/Ziel"
string3 = "relativer/Pfad/Zum/!Ziel"
string4 = "noch/…ein/~Sonderzeichen/!Pfad"
check = ['$','~','!','…']
#ermitteln kann ich das ganze nun mit bspw.
paths = [string1, string2, string3, string4]
result = [(c, path) for path in paths for c in check if path.find(c) >= 0]
print(result)
|
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12848
|
Ich würde das ja mit einem Regex machen. Kann das aber gerade nicht in Python aus dem Ärmel schütteln. In Ruby: | findings = s.scan /[$~!…]/
if findings.empty?
...
end
|
|
ChickenLipsRfun2eat
(Themenstarter)
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
rklm schrieb: Ich würde das ja mit einem Regex machen. Kann das aber gerade nicht in Python aus dem Ärmel schütteln.
Ich habe irgendwie im Hinterkopf das Regex böse sind und langsam. Ist aktuell noch nicht relevant, aber ich baue mir mal eine Regex-Lösung mit ein, dann kann ich später bei > 50.000 Zeichenketten die Zeit mal messen. Ich habe das mal anderweitig genutzt mit re/compile und .search, da habe ich aber nach ganzen Ausdrücken, nicht nach einzelnen Zeichen gesucht. Aber, guter Hinweis! Danke!
|
ChickenLipsRfun2eat
(Themenstarter)
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Nobuddy schrieb: …code
Darf ich dich fragen, was du mir damit sagen möchtest? Du nutzt doch das selbe Konzept — oder übersehe ich was?
|
sebix
Moderator, Webteam
Anmeldungsdatum: 14. April 2009
Beiträge: 5364
|
ChickenLipsRfun2eat schrieb: Gibt es da effektivere, mehr „pythonische“ Wege als die beiden gegenseitigen Loops zu durchlaufen?
Meine Logik sagt mir, dass du an O(n²) nicht herumkommst. Was du optimieren kannst, ist die Laenge und Verstaendlichkeit deines Code (was bei dir sehr optimal aussieht) und die Laufzeit. Mit regex kannst du die Komplexitaet ja auch nicht senken, schliesslich hat re ja auch keine Glaskugel ☺ Der einzige Ansatzpunkt der mit einfaellt ist, dass Schleifen in Python eher langsam sind. Da kann regex ein Spur besser sein, weil das im Hintergrund in Cpython ablaeuft, aber das haengt bestimmt stark von der Anzahl der zu pruefenden Zeichen ab. Kurzum: Ich bezweifle dass du da was optimieren kannst. Es gibt viele verschiedene Schreibweisen, zB kannst du noch Generatoren und any() verwenden.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Soll die eingangs gezeigte Reihenfolge erhalten bleiben oder geht es nur darum, dass alle Sonderzeichen, die tatsächlich vorkommen, angezeigt werden? Sonst könnte man das alternativ mit Sets lösen. Ein Beispiel, wo ich … weg gelassen habe:
| specials = set("$~!…")
strings = [
"$HOME/Pfad/Zum/Ziel",
"~/Pfad/Zum/Ziel",
"relativer/Pfad/Zum/!Ziel",
"noch/ein/~Sonderzeichen/!Pfad"
]
result = set()
for string in strings:
result |= set(string) & specials
print("Enthaltene Sonderzeichen:", list(result))
|
Die Komplexität bleibt natürlich gleich, aber man hat mehr in C ausgelagert. Inwiefern das wirklich was bringt, müsste man noch messen.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Und hier noch komplett ohne Python-Schleife:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | from functools import reduce
SPECIAL_CHARS = "$~!…"
def get_specials(strings, specials=set(SPECIAL_CHARS)):
return reduce(set().union, map(specials.intersection, strings))
def main():
strings = [
"$HOME/Pfad/Zum/Ziel",
"~/Pfad/Zum/Ziel",
"relativer/Pfad/Zum/!Ziel",
"noch/ein/~Sonderzeichen/!Pfad"
]
print("Enthaltene Sonderzeichen:", get_specials(strings))
if __name__ == "__main__":
main()
|
Ist aber nicht mehr so lesbar wie das vorherige Beispiel. Übrigens, für das Verständnis von Sets in Python ist neben der offiziellen Doku auch das ganz gut: https://realpython.com/python-sets/ EDIT: Ohne union(), um somit die Zwischenergebnisse zu vermeiden:
| from itertools import chain
SPECIAL_CHARS = "$~!…"
def get_specials(strings, specials=set(SPECIAL_CHARS)):
intersections = map(specials.intersection, strings)
return set(chain.from_iterable(intersections))
|
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12848
|
sebix schrieb: ChickenLipsRfun2eat schrieb: Gibt es da effektivere, mehr „pythonische“ Wege als die beiden gegenseitigen Loops zu durchlaufen?
Meine Logik sagt mir, dass du an O(n²) nicht herumkommst.
Das ist kein Fall von O(n^2). Wenn Du die Anzahl der Zeichenketten verdoppelst, bekommst Du asymptotisch auch nur doppelte Laufzeit - und nicht vierfache. Das hier ist O(n*m), mit n als Anzahl der Zeichenketten und m als durchschnittliche Länge. Oder halt O(n), wenn Du nur die Anzahl der zu prüfenden Zeichenketten berücksichtigen willst.
Mit regex kannst du die Komplexitaet ja auch nicht senken, schliesslich hat re ja auch keine Glaskugel ☺
Regex machen es aber auch nicht schlechter, denn bei dem verwendeten Ausdruck (Gruppe von einzelnen Zeichen ohne Wiederholung) gibt es kein Backtracking. Der Ausdruck sucht genau so wie die "naive" Strategie aus dem ersten Posting.
|
sebix
Moderator, Webteam
Anmeldungsdatum: 14. April 2009
Beiträge: 5364
|
rklm schrieb: sebix schrieb: ChickenLipsRfun2eat schrieb: Gibt es da effektivere, mehr „pythonische“ Wege als die beiden gegenseitigen Loops zu durchlaufen?
Meine Logik sagt mir, dass du an O(n²) nicht herumkommst.
Das ist kein Fall von O(n^2). Wenn Du die Anzahl der Zeichenketten verdoppelst, bekommst Du asymptotisch auch nur doppelte Laufzeit - und nicht vierfache. Das hier ist O(n*m), mit n als Anzahl der Zeichenketten und m als durchschnittliche Länge. Oder halt O(n), wenn Du nur die Anzahl der zu prüfenden Zeichenketten berücksichtigen willst.
Oh, ja, natuerlich 😇 Hatte irgendwie im Kopf n=m gesetzt.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Noch ein Set-Ansatz. Hierbei werden die Zeichen aller Strings in ein gemeinsames Set gesteckt (dies passiert implizit in der intersection-Methode) und dann die Schnittmenge zu den Sonderzeichen geliefert. Die chain-Funktion sorgt dafür, dass die Strings wie ein großes Iterable behandelt werden und ihre Zeichen nacheinander liefern, ohne Zwischenergebnisse zu benötigen. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | from itertools import chain
SPECIAL_CHARS = "$~!…"
def get_specials(strings, specials=set(SPECIAL_CHARS)):
return specials.intersection(
chain.from_iterable(strings)
)
def main():
strings = [
"$HOME/Pfad/Zum/Ziel",
"~/Pfad/Zum/Ziel",
"relativer/Pfad/Zum/!Ziel",
"noch/ein/~Sonderzeichen/!Pfad"
]
print("Enthaltene Sonderzeichen:", get_specials(strings))
if __name__ == "__main__":
main()
|
Im Endeffekt muss natürlich auch alles verglichen werden. Den Zeichen werden aber eindeutige Zahlen zugeordnet (Hashes), mehrfache Vorkommen werden verworfen und am Ende wird die "große" Hash-Table mit der Sonderzeichen-Table verglichen. Das *kann* durchaus effizienter sein als der naive Ansatz. Müsste man wie gesagt mal ausprobieren und messen. Und kompakter ist es mMn auch, sofern man verstanden hat, was da passiert. ☺
|
ChickenLipsRfun2eat
(Themenstarter)
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Hier ist ja was los 😉 Danke an alle, aber ich brauche erstmal ein wenig Zeit alles durchzugucken. Zur Info: Der obige Code ist Beispielcode. Ich kann auch keinen echten liefern, da ich den noch nicht habe. Wie beschrieben bin ich bei String-Literalen mit möglicherweise aufzulösenden Umgebungsvariablen darüber gestolpert und ich habe im Zuge dessen über die Charakter-Sets nachgegrübelt, da ich im Zusammenhang mit unicode-Strings, etc. mittlerweile sehr gern auf Python zurückgreife, da ich dort ohne Bauchschmerzen '…' als char verwenden kann, was in C doch etwas komplexer ist.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
ChickenLipsRfun2eat schrieb: Zur Info: Der obige Code ist Beispielcode.
Schon klar, aber die Ansätze hast du ja nun. Man muss auch sagen, dass Python sehr gut optimiert ist für String-Operationen. Insofern ist dein erster Ansatz am Ende vielleicht gar nicht so langsam wie du befürchtest. Kannst ja gerne die Mess-Ergebnisse hier reinschreiben, wenn du es mit den echten Daten testest.
|
ChickenLipsRfun2eat
(Themenstarter)
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
snafu1 schrieb: Soll die eingangs gezeigte Reihenfolge erhalten bleiben oder geht es nur darum, dass alle Sonderzeichen, die tatsächlich vorkommen, angezeigt werden?
Nein, es gibt keine zu beachtende Reihenfolge. Die Strings werden einzeln für sich (weiter-)verarbeitet. Sollte ich irgendwas sortieren wollen, würde ich das aus Gewohnheit als letzten, separaten Schritt machen, wenn die Daten „fertig“ sind. Sonst könnte man das alternativ mit Sets lösen. Ein Beispiel, wo ich … weg gelassen habe:
Danke! Set habe ich mir auch notiert und werde deine Ansätze mit ausprobieren. Die Komplexität bleibt natürlich gleich, aber man hat mehr in C ausgelagert. Inwiefern das wirklich was bringt, müsste man noch messen.
Bei ein paar kb Daten vielleicht nix. Ich nehme den Set-Ansatz aber auf jeden Fall mit rein, der erscheint mir plausibel. Welche Algorithmen dahinterstehen, weiß ich natürlich nicht, aber dafür nutzt man ja Python und schreibt es nicht selbst in C 😉 Was den ersten Ansatz angeht: Das ist halt das, was ich aus dem C(++)-Gedankenansatz gemacht habe. Da würde ich auch zwei char arrays durchiterieren müssen. Im Endeffekt müssen ja sowieso alle chars (bis auf den letzten) einmal geprüft werden. Ich hätte auch besser keine Pfade als Beispiel genommen. Das ist verwirrend, da man dort nach dem ersten Treffer schon abbrechen könnte, etc.
|
ChickenLipsRfun2eat
(Themenstarter)
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Da ich jetzt zu neugierig war, habe ich schon mal den ersten Testlauf gestartet. Die Beispieldaten waren ein find $(pwd) in einem Medienordner mit rund 53.000 Einträgen. Die „special chars“ habe ich zu Umlauten gemacht, da gibt es mehr Treffer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | #!/usr/bin/env python
"""Ermitteln von Sonderzeichen in Zeichenketten
, siehe https://forum.ubuntuusers.de/topic/python3-char-listen-pruefung-im-string-literal"""
from itertools import chain
import cProfile
SPECIAL_CHARS = "äöüß"
with open( "./sonderzeichen_ermitteln.beispieldaten", "r" ) as f:
STRING_DATA = f.read().splitlines()
def ansatz_loop():
"""Klassischer Loop"""
result = list()
for string in STRING_DATA:
result += [c for c in SPECIAL_CHARS if c in string]
return result
def ansatz_set_get_specials(strings): #, specials=set(SPECIAL_CHARS)):
"""[post:9237280:]"""
specials = set(SPECIAL_CHARS)
intersections = map(specials.intersection, strings)
result = chain.from_iterable(intersections)
return list(result)
if __name__ == "__main__":
cProfile.run('ansatz_loop()')
cProfile.run('ansatz_set_get_specials(STRING_DATA)')
|
Angesichts der Tatsache, dass mein Rechner von 2012 ist und Zeiten von 0.027/0.028 Sekunden, bzw. 0.142/0.152 Sekunden ausspuckt kann ich mir glaube ich weitere Überlegungen dazu sparen. Da lässt sich an anderen Stellen sicher mehr optimieren 😉 Sehr interessant, wie schnell das mit den unicode-Zeichenketten funktioniert. Die Regex-Lösung folgt dann später/demnächst, weil ich die auch wissen will 😉
|