| |
| Autor |
  Python: Prüfen, ob ein Tuple ein Teil eines anderen ist |
|
haegar90
Aktiv 
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
|
 Notiz  Profil
|
Nuramon
Senior 
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.
|
Notiz Profil
|
haegar90
Aktiv
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.🤔
|
Notiz Profil
|
Nuramon
Senior
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.
|
Notiz Profil
|
Goswin
Senior 
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
|
Notiz Profil
|
haegar90
Aktiv 
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.]
|
Notiz Profil
|
haegar90
Aktiv
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
|
Notiz Profil
|
DerEinfaeltige
Senior
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
|
Notiz Profil
|
haegar90
Aktiv
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.
|
Notiz Profil
|
DerEinfaeltige
Senior
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
|
Notiz Profil
|
haegar90
Aktiv
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
|
Notiz Profil
|
DerEinfaeltige
Senior
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.
|
Notiz Profil
|
haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 667
Wohnort: Gog
| Beitrag No.12, vom Themenstarter, eingetragen 2021-02-25
|
Notiz Profil
|
haegar90
Aktiv
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
|
Notiz Profil
|
viertel
Senior
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.
|
Notiz Profil
|
haegar90
Aktiv
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.
|
Notiz Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2935
| Beitrag No.16, eingetragen 2021-02-26
|
Es steht im Grunde dabei:
Nutze bspw. "multiprocessing".
|
Notiz Profil
|
haegar90
Aktiv
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.
|
Notiz Profil
|
haegar90 hat die Antworten auf ihre/seine Frage gesehen.
haegar90 hat selbst das Ok-Häkchen gesetzt. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
