Liste auf Teilinhalt prüfen

[Freumel]

Guten Abend zusammen,

ich habe mehrere Listen die ich miteinander vergleichen möchte. Wenn die Listen 100% übereinstimmen ist es schonmal gut. Allerdings soll jetzt auch auf teilweise gleiche Abschnitte geprüft werden:

Code: Alles auswählen

reference = [1,2,3,4,5,6,7]
a = [2,3,4]
b = [1,2,9]
c = [1,2,3,4,5,6,7,8]
d = [1,2,5,6]

Die Listen a, b und c sollen mit der Referenz verglichen werden. Dabei ist a und c jeweils True und b und d False.
Gibt es hier eine schönere Möglichkeit als verschachtelte Schleifen?

Vielen Dank schonmal

[__deets__]

Jein. Lineares suchen wird es immer bleiben, aber es gibt Algorithmen die durch geschickte Analyse etwas schneller werden: https://de.wikipedia.org/wiki/Knuth-Mor ... lgorithmus

Pythons String suche sollte das können. Ggf hilft also ein wandeln zu strings um das ganze zu beschleunigen. Das meint natürlich für dein Beispiel zb "1234567", NICHT "[1, 2, 3, 4, 5, 6, 7]".

[Sirius3]

@__deets__: meinst Du nicht eher ',1,2,3,4,5,6,7,'?

[__deets__]

Nein, eigentlich meinte ich “”.join(liste). Statt str(liste). Ich tippe hier viel auf dem iPad, da ist gerade Code immer ätzend. Würde man Kommas einführen, könnte das glaube ich den den Algorithmus negative beeinflussen. Wirklich in Erinnerung habe ich den aber nach nicht - ist schon etwas her, das Grundstudium

[DeaD_EyE]

Sliding Window wäre jetzt das erste, was mir im Sinn kommt.

Du iterierst über die referenz-liste solange, bis dein Fenster voll ist. Dann vergleichst du dieses Fenster mit dem Muster.
Wenn es übereinstimmt, hast du einen Treffer. Falls nicht, ein neues Element von der referenz zum Fenster hinzufügen und das erste Element verwerfen.
Das mit Worten zu beschreiben, ist viel komplizierter, als Programmcode.

Code: Alles auswählen

from collections import deque


def sliding_window(iterable, size):
    ret_type = type(iterable)
    iterable = iter(iterable)
    window = deque(maxlen=size)
    while True:
        if len(window) == size:
            yield ret_type(window)
        try:
            cur = next(iterable)
            window.append(cur)
        except StopIteration:
            break
            
def contains(reference, pattern):
    if type(reference) != type(pattern):
        raise TypeError('Reference and pattern must have the same type.')
    window_size = len(pattern)
    for window in sliding_window(reference, window_size):
        if window == pattern:
            return True
    return False

Die erste Funktion sliding_window lässt sich vereinfachen, wenn man als Eingangstyp z.B. immer eine Sequenz erwartet.
Dann könnte man auch mit slicing arbeiten und müsste keinen iterator erzeugen.
Wenn man lange genug drüber nachdenkt, lässt sich sliding_window auch noch verbessern. (ggf. mit etwas aus itertools)
Die zweite Funktion vergleicht nur.

Hier nochmal ein Generator, der slicing verwendet.

Code: Alles auswählen

def sliding_window_slicing(reference, size):
    for cursor in range(len(reference) - size + 1):
        yield reference[cursor:cursor+size]