Python: Prüfen, ob ein Tuple ein Teil eines anderen ist
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Themenstart: 2021-02-23 14:01
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?
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.2, vom Themenstarter, eingetragen 2021-02-23 14:48
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.🤔
Nuramon
Senior Dabei seit: 23.01.2008 Mitteilungen: 2585
Beitrag No.3, eingetragen 2021-02-23 14:59
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.
Goswin
Senior Dabei seit: 18.09.2008 Mitteilungen: 1580
Herkunft: Chile, Ulm
Beitrag No.4, eingetragen 2021-02-23 15:26
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?
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.5, vom Themenstarter, eingetragen 2021-02-23 16:11
...noch nicht schön, aber es scheint zu funktionieren.
Python
def ck_tpl(a, b):
k =len(a)
t =len(b)
tpl_ab =[]
ct =0if t >= k:
for i inrange(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))
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.6, vom Themenstarter, eingetragen 2021-02-23 16:18
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?
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2694
Beitrag No.7, eingetragen 2021-02-24 08:50
Hier noch zwei Vorschläge, die keinerlei "Magie" benötigen:
Python
def is_sub_sequence(short,long):
i,j =0,0while i <len(short):
if j >=len(long):
returnFalseif short[i]==long[j]:
i +=1
j +=1returnTruedef is_sub_sequence_iter(short,long):
long_iter =iter(long)for i in short:
b =Falsefor j in long_iter:
if i == j:
b =Truebreakifnot b:
returnFalsereturnTrue
----------------- Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2694
Beitrag No.9, eingetragen 2021-02-25 13:20
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 inrange(len(long)):
_states =[]for j,k in states:
iflong[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 inrange(len(long)-len(short)+1):
ifall(long[i+j]==short[j]for j inrange(len(short))):
indices.append(i)return indices
def hasSubsequenceNaive(short,long):
returnany(all(long[i+j]==short[j] \
for j inrange(len(short))) \
for i inrange(len(long)-len(short)+1))fromrandomimport randint
def buildTestData(n,k,r):
long=[randint(1,r)for i inrange(n)]
short =[randint(1,r)for i inrange(k)]return short,longfromtimeitimporttimeit
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 -
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.10, vom Themenstarter, eingetragen 2021-02-25 14:35
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]]
# 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 inrange(len(long)):
_states =[]for j, k in states:
iflong[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 inrange(len(long) - len(short) + 1):
ifall(long[i + j]== short[j]for j inrange(len(short))):
indices.append(i)return indices
def hasSubsequenceNaive(short,long):
returnany(all(long[i + j]== short[j] \
for j inrange(len(short))) \
for i inrange(len(long) - len(short) + 1))def ck_tpl(a, b):
k =len(a)
t =len(b)
ct =[]if t >= k:
for i inrange(0, t-k):
if b[i:k+i]== a[0:k]:
ct.append(i)return ct
fromrandomimport randint
def buildTestData(n, k, r):
long=[randint(1, r)for i inrange(n)]
short =[randint(1, r)for i inrange(k)]return short,longfromtimeitimporttimeit
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
viertel
Senior Dabei seit: 04.03.2003 Mitteilungen: 27752
Herkunft: Hessen
Beitrag No.14, eingetragen 2021-02-25 16:50
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.
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.15, vom Themenstarter, eingetragen 2021-02-26 07:30
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 ?
haegar90
Aktiv Dabei seit: 18.03.2019 Mitteilungen: 565
Herkunft: Gog
Beitrag No.17, vom Themenstarter, eingetragen 2021-02-26 08:39
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.