Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Python: Prüfen, ob ein Tuple ein Teil eines anderen ist
Autor
Kein bestimmter Bereich J Python: Prüfen, ob ein Tuple ein Teil eines anderen ist
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Themenstart: 2021-02-23

Habe danach gesucht, bin aber auch nur auf die Frage gestoßen, ohne Antwort. Kennt jemand vielleicht eine Funktion die prüft ob ein Tuple komplett mit gleicher Reihenfolge in einem anderen Tupel vorkommt ? Oder ich bezeichne es besser als zwei zu vergleichende Blockchains, da der Vergleich der Tupel mitunter mehrere 1000 Elemente umfasst. Wäre es vielleicht besser das als String-Vergleich (mit Trennzeichen) zu machen ? a ='1-2-3-4-5-6-7-8-9-10-11-12' b ='4-5-6-7-8' Prüfung ob Teilstring b in String a enthalten ist ? \sourceon Copied from stackoverflow This might be a silly question, but is it possible to check whether the elements in a tuple1 are a subset of another tuple2 in the same sequence as they appear in tuple1? I tried to do this with .issubset, but this does not look at whether the sequence of tuple1 is in tuple 2: tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) set(tuple1).issubset(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) set(tuple1).issubset(tuple2) True # Only membership is considered, not sequence What I would like is: tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) (tuple1).sequenceisin(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) (tuple1).sequenceisin(tuple2) False Is there a simple way to do this? \sourceoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2989
  Beitrag No.1, eingetragen 2021-02-23

Hallo, \quoteon(2021-02-23 14:01 - haegar90 im Themenstart) EDIT: Das funktioniert. \sourceon Python def tpl_ctt(b, a): ans = True for i in iter(b): ans &= i in a return ans \sourceoff \quoteoff Hierbei missachtest du aber die Reihenfolge. (Dein letztes Beispiel aus dem Themenstart würde True zurückgeben, obwohl du False haben willst.) Für Strings kannst du einfach \sourceon Python a = "23" b = "123" a in b # True \sourceoff benutzen. Für Tupel oder andere Iterables musst du halt selbst eine Funktion schreiben, was nicht schwierig ist.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.2, vom Themenstarter, eingetragen 2021-02-23

Oh, hatte deine Antwort noch nicht gesehen und mein "EDIT" gelöscht da ich auch festgestellt hatte dass es auch ein "True" gibt wenn die Reihenfolge nicht stimmt. Ja, danke, als String müssten dann Trennzeichen dazu kommen. "12345" als [1,2,3,4,5] "123" als [1,2,3] True "12345" als [1,2,3,4,5] "123" als [1,23] True (wäre dann falsch) Es müssten dann alle items der Reihe nach verglichen werden. Vielleicht könnte man ja das kürzere Tupel schrittweise über das längere schieben bis zum Ende den längeren Tupels und prüfen ob an einer Position alle Elemente gleich sind.🤔


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2989
  Beitrag No.3, eingetragen 2021-02-23

Wenn du mit Strings arbeiten willst, dann könntest du z.B. \sourceon Python x = [1,23] y = [str(i) for i in x] #in strings umwandeln ",".join(y) # "1,23" \sourceoff für die Umwandlung benutzen. Du kannst aber auch direkt mit Listen bzw. Tupeln arbeiten. Hier eine Pseudocode-Lösung, die du selbst implementieren darfst: Wir wollen testen, ob die Liste a eine zusammenhängende Teilfolge der Liste b ist. Dazu sei k die Länge von a. Teste jetzt, ob die ersten k Elemente von b gleich a sind (b[0:k] == a). Dann sieh dir die nächsten Elemente von b (von Position 1 bis k+1) an usw. bis du ein Match gefunden hast, falls es denn eines gibt.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1619
Wohnort: Chile, Ulm
  Beitrag No.4, eingetragen 2021-02-23

\quoteon(2021-02-23 14:01 - haegar90 im Themenstart) What I would like is: \sourceon tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) (tuple1).sequenceisin(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) (tuple1).sequenceisin(tuple2) False Is there a simple way to do this? \sourceoff Is there a simple way to do this? \quoteoff \sourceon tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) str(tuple1)[1:-1] in str(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) str(tuple1)[1:-1] in str(tuple2) False \sourceoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.5, vom Themenstarter, eingetragen 2021-02-23

...noch nicht schön, aber es scheint zu funktionieren. \sourceon Python def ck_tpl(a, b): k = len(a) t = len(b) tpl_ab = [] ct = 0 if t >= k: for i in range(0, t-k): if b[i:k+i] == a[0:k]: tpl_ab = b[i:k + i] ct = i if ct == 0: tpl_ab = 'not in' return tpl_ab, b, ct a = [4, 5, 6, 47, 11, 7, 8] b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 4, 5, 6, 47, 11, 7, 8, 9, 10, 11] print(ck_tpl(a, b)) \sourceoff [Die Antwort wurde vor Beitrag No.1 begonnen.]


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.6, vom Themenstarter, eingetragen 2021-02-23

Hallo Goswin, das gefällt mir 😃 \quoteon(2021-02-23 15:26 - Goswin in Beitrag No. 4) \quoteon(2021-02-23 14:01 - haegar90 im Themenstart) What I would like is: \sourceon tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) (tuple1).sequenceisin(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) (tuple1).sequenceisin(tuple2) False Is there a simple way to do this? \sourceoff Is there a simple way to do this? \quoteoff \sourceon tuple1 = ([1, 2, 3]) tuple2 = ([1, 2, 3, 4, 5]) str(tuple1)[1:-1] in str(tuple2) True tuple1 = ([1, 2, 3]) tuple2 = ([1, 3, 2, 4, 5]) str(tuple1)[1:-1] in str(tuple2) False \sourceoff \quoteoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.7, eingetragen 2021-02-24

Hier noch zwei Vorschläge, die keinerlei "Magie" benötigen: \sourceon Python def is_sub_sequence(short,long): i,j = 0,0 while i < len(short): if j >= len(long): return False if short[i] == long[j]: i += 1 j += 1 return True def is_sub_sequence_iter(short,long): long_iter = iter(long) for i in short: b = False for j in long_iter: if i == j: b = True break if not b: return False return True \sourceoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.8, vom Themenstarter, eingetragen 2021-02-25

Hallo DerEinfaeltige, heute erst gesehen. Die Vorschläge sind bestimmt die 'sauberen' Lösungen. Habe gerade noch diesen Vorschlag gebastelt: \sourceon Python def ck_tpl_2(sht, lng): return [True for i in lng if sht[0: len(sht)] == lng[i: len(sht)+i]] \sourceoff Man könnte anstelle von 'True' auch 'i' zurückgeben als Position ab der die Tuples übereinstimmen.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.9, eingetragen 2021-02-25

Dein Code macht allerdings etwas anderes als die Vorschläge aus dem obigen Post. Meine Lösung findet bspw. auch [1,3] in [1,2,3]. Ob das gewünscht oder unerwünscht ist, musst du wissen. Noch Vorschläge für deinen Code, die ohne Strings auskommen: \sourceon Python # Find starting indeces of short in long # e.g.: findSubsequence([2,3],[1,2,3,4,2,3]) -> [1,4] def findSubsequence(short,long): states = [(0,0)] indices = [] for i in range(len(long)): _states = [] for j,k in states: if long[i] == short[k]: if k == len(short)-1: indices.append(j) else: _states.append((j,k+1)) _states.append((i+1,0)) states = _states return indices def findSubsequenceNaive(short,long): indices = [] for i in range(len(long)-len(short)+1): if all(long[i+j]==short[j] for j in range(len(short))): indices.append(i) return indices def hasSubsequenceNaive(short,long): return any(all(long[i+j]==short[j] \ for j in range(len(short))) \ for i in range(len(long)-len(short)+1)) from random import randint def buildTestData(n,k,r): long = [randint(1,r) for i in range(n)] short = [randint(1,r) for i in range(k)] return short,long from timeit import timeit short, long = buildTestData(10000,10,2) for f in [findSubsequenceNaive,hasSubsequenceNaive,findSubsequence]: t=timeit(f"f(short,long)",globals=globals(),number=100) print(f"{f.__name__:20} took {t:.3f}s to calculate {f(short,long)}") findSubsequenceNaive took 23.584s to calculate [1436, 1472, 3276, 4921, 5229, 6539, 7977, 8191, 8625, 8689, 8739] hasSubsequenceNaive took 5.194s to calculate True findSubsequence took 2.160s to calculate [1436, 1472, 3276, 4921, 5229, 6539, 7977, 8191, 8625, 8689, 8739] \sourceoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.10, vom Themenstarter, eingetragen 2021-02-25

Cool 😃 da gibt es was zu lernen, auch interessant die Laufzeiten; damit werde ich mich auch jetzt mal vertraut machen 👍, hatte ich bisher noch nie verwendet. In diesem Zusammenhang: Stimmt es dass Python bei einem Prozessor (z.B. mit 8 Kernen) immer nur einen einzigen Kern davon als Rechenleistung nutzen kann ? \sourceon Performance-Test ck_tpl_3 took 2.890s to calculate [32499] findSubsequenceNaive took 2.580s to calculate [32499] hasSubsequenceNaive took 2.320s to calculate True findSubsequence took 1.781s to calculate [32499] \sourceoff \sourceon Python def ck_tpl_3(sht, lng): return [i for i in lng if sht[0: len(sht)] == lng[i: len(sht)+i]] \sourceoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.11, eingetragen 2021-02-25

Natürlich kann Python grundsätzlich mehrere Kerne/Threads nutzen. Dazu muss man aber natürlich auch parallel programmieren. Serieller Code läuft immer auf einem Kern (bzw. genauer gesagt in einem Thread). Das hat nichts mit Python zu tun.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.12, vom Themenstarter, eingetragen 2021-02-25

Danke.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.13, vom Themenstarter, eingetragen 2021-02-25

\showon Vergleich mit ck_tpl \sourceon Python # Find starting indeces of short in long # e.g.: findSubsequence([2,3],[1,2,3,4,2,3]) -> [1,4] def findSubsequence(short, long): states = [(0, 0)] indices = [] for i in range(len(long)): _states = [] for j, k in states: if long[i] == short[k]: if k == len(short) - 1: indices.append(j) else: _states.append((j, k + 1)) _states.append((i + 1, 0)) states = _states return indices def findSubsequenceNaive(short, long): indices = [] for i in range(len(long) - len(short) + 1): if all(long[i + j] == short[j] for j in range(len(short))): indices.append(i) return indices def hasSubsequenceNaive(short, long): return any(all(long[i + j] == short[j] \ for j in range(len(short))) \ for i in range(len(long) - len(short) + 1)) def ck_tpl(a, b): k = len(a) t = len(b) ct = [] if t >= k: for i in range(0, t-k): if b[i:k+i] == a[0:k]: ct.append(i) return ct from random import randint def buildTestData(n, k, r): long = [randint(1, r) for i in range(n)] short = [randint(1, r) for i in range(k)] return short, long from timeit import timeit short, long = buildTestData(100000, 15, 2) #print(short) #print(long) for f in [ck_tpl, findSubsequenceNaive, hasSubsequenceNaive, findSubsequence]: t = timeit(f"f(short,long)", globals=globals(), number=100) print(f"{f.__name__:20} took {t:.3f}s to calculate {f(short, long)}") ck_tpl took 2.019s to calculate [3631, 6769, 25552, 57315, 89816] findSubsequenceNaive took 5.827s to calculate [3631, 6769, 25552, 57315, 89816] hasSubsequenceNaive took 0.209s to calculate True findSubsequence took 3.270s to calculate [3631, 6769, 25552, 57315, 89816] # 15 aus 100.000 \sourceoff \showoff


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
viertel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen
  Beitrag No.14, eingetragen 2021-02-25

Der Vergleich mit der Suche einer Zeichenfolge in einem String(Text) wurde ja schon gegeben. Die Suche nach einem „Untertupel“ ist genau das gleiche, nur eben mit Zahlen statt Zeichen. Und dafür gibt es Algorithmen, siehe wiki: String-Matching-Algorithmus.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.15, vom Themenstarter, eingetragen 2021-02-26

\quoteon(2021-02-25 14:35 - haegar90 in Beitrag No. 10) ....In diesem Zusammenhang: Stimmt es dass Python bei einem Prozessor (z.B. mit 8 Kernen) immer nur einen einzigen Kern davon als Rechenleistung nutzen kann ? \quoteon(2021-02-25 14:56 - DerEinfaeltige in Beitrag No. 11) Natürlich kann Python grundsätzlich mehrere Kerne/Threads nutzen. Dazu muss man aber natürlich auch parallel programmieren. Serieller Code läuft immer auf einem Kern (bzw. genauer gesagt in einem Thread). Das hat nichts mit Python zu tun. \quoteoff \quoteoff Wollte mich mal mit dem Threading anfreunden und habe dazu Infos gesucht. Das hört sich hier so an als wäre dennoch immer nur ein einziger Kern aktiv und die Nutzung mehrehrer Kerne läuft seriell aber nicht parallel (Threading mit "standard" Python). Dann wäre die verfügbare Rechenleistung effektiv auch nur die von einem einzigen Kern, selbst wenn man Threads programmiert ? Oder wie ist das zu verstehen ? @viertel Danke für den Hinweis.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.16, eingetragen 2021-02-26

Es steht im Grunde dabei: Nutze bspw. "multiprocessing".


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
  Beitrag No.17, vom Themenstarter, eingetragen 2021-02-26

Ja, danke, und damit ist es ein umfassenderes Thema. Das fasse ich erst einmal nicht an da es mir recht kompliziert und zeitaufwendig erscheint. Die dazu gegebenen Hinweise unerwartete Fehler nicht ausschließen.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
haegar90 hat die Antworten auf ihre/seine Frage gesehen.
haegar90 hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]