Antworte auf:  Python: Prüfen, ob ein Tuple ein Teil eines anderen ist von haegar90
Forum:  Programmieren, moderiert von: matph

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.17, eingetragen 2021-02-26 08:39    [Diesen Beitrag zitieren]

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.  


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2869
 Beitrag No.16, eingetragen 2021-02-26 08:10    [Diesen Beitrag zitieren]

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



haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.15, eingetragen 2021-02-26 07:30    [Diesen Beitrag zitieren]

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.


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen

 Beitrag No.14, eingetragen 2021-02-25 16:50    [Diesen Beitrag zitieren]

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: 660
Wohnort: Gog

 Beitrag No.13, eingetragen 2021-02-25 15:40    [Diesen Beitrag zitieren]

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




haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.12, eingetragen 2021-02-25 15:16    [Diesen Beitrag zitieren]

Danke.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2869
 Beitrag No.11, eingetragen 2021-02-25 14:56    [Diesen Beitrag zitieren]

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.


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.10, eingetragen 2021-02-25 14:35    [Diesen Beitrag zitieren]

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]]



DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2869
 Beitrag No.9, eingetragen 2021-02-25 13:20    [Diesen Beitrag zitieren]

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]


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.8, eingetragen 2021-02-25 11:16    [Diesen Beitrag zitieren]

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.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2869
 Beitrag No.7, eingetragen 2021-02-24 08:50    [Diesen Beitrag zitieren]

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
 
 


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.6, eingetragen 2021-02-23 16:18    [Diesen Beitrag zitieren]

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



haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.5, eingetragen 2021-02-23 16:11    [Diesen Beitrag zitieren]

...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.]


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1616
Wohnort: Chile, Ulm

 Beitrag No.4, eingetragen 2021-02-23 15:26    [Diesen Beitrag zitieren]

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


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2873
 Beitrag No.3, eingetragen 2021-02-23 14:59    [Diesen Beitrag zitieren]

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.


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Beitrag No.2, eingetragen 2021-02-23 14:48    [Diesen Beitrag zitieren]

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: 2873
 Beitrag No.1, eingetragen 2021-02-23 14:37    [Diesen Beitrag zitieren]

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.


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 660
Wohnort: Gog

 Themenstart: 2021-02-23 14:01    [Diesen Beitrag zitieren]

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?


 
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]