Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Python: Prüfen, ob ein Tuple ein Teil eines anderen ist
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Python: Prüfen, ob ein Tuple ein Teil eines anderen ist
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 ?

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?



-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2848
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-02-23


Hallo,

2021-02-23 14:01 - haegar90 im Themenstart schreibt:
EDIT: Das funktioniert.
Python
def tpl_ctt(b, a):
    ans = True
    for i in iter(b):
        ans &= i in a
    return ans

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
Python
a = "23"
b = "123"
a in b # True
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  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.🤔




-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2848
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-02-23


Wenn du mit Strings arbeiten willst, dann könntest du z.B.
Python
x = [1,23] 
y = [str(i) for i in x] #in strings umwandeln
",".join(y) # "1,23"
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  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1616
Wohnort: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-02-23


2021-02-23 14:01 - haegar90 im Themenstart schreibt:
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?
Is there a simple way to do this?

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



-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen. (Kol.2:9)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-02-23


...noch nicht schön, aber es scheint zu funktionieren.
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))


[Die Antwort wurde vor Beitrag No.1 begonnen.]


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-02-23


Hallo Goswin,

das gefällt mir 😃

2021-02-23 15:26 - Goswin in Beitrag No. 4 schreibt:
2021-02-23 14:01 - haegar90 im Themenstart schreibt:
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?
Is there a simple way to do this?

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




-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-02-24


Hier noch zwei Vorschläge, die keinerlei "Magie" benötigen:
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
 
 


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
Python
def ck_tpl_2(sht, lng):
    return [True for i in lng if sht[0: len(sht)] == lng[i: len(sht)+i]]

Man könnte anstelle von 'True' auch 'i' zurückgeben als Position ab der
die Tuples übereinstimmen.



-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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]



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 ?
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]
Python
def ck_tpl_3(sht, lng):
    return [i for i in lng if sht[0: len(sht)] == lng[i: len(sht)+i]]




-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2021-02-25


Danke.


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2021-02-25


Vergleich mit ck_tpl
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





-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.


-----------------
Bild



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2021-02-26


2021-02-25 14:35 - haegar90 in Beitrag No. 10 schreibt:
....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 ?

2021-02-25 14:56 - DerEinfaeltige in Beitrag No. 11 schreibt:
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.


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.


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2021-02-26


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




-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.  



-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90 hat die Antworten auf ihre/seine Frage gesehen.
haegar90 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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]