´in´ für Teil-Listen (wie beim String)

[Üpsilon]

Hallo ihr Lieben,

Code: Alles auswählen

>>> "baum" in "baumhaus"
True
>>> [3,4] in [1,2,3,4,5]
False
>>>

Das fand ich überraschend. Gibt es etwas Eingebautes, um zu gucken, ob eine Liste eine Teil-Liste einer anderen Liste ist? Danke.

[DasIch]

Gibt es nicht. Allerdings gibt es sowas für sets:

Code: Alles auswählen

>>> {3, 4} < {1, 2, 3, 4, 5}
True

[Üpsilon]

Danke, aber das ist für mich leider keine Lösung, weil bei mir die Reihenfolge wichtig ist. Hab mir dann selbst was gebraut.

[eckhard]

In

http://python.6.x6.nabble.com/testing-i ... 51757.html

stehen einige interessante Lösungen.

eckhard

[BlackJack]

@eckhard: Soweit ich sehe steht da nur eine Lösung für das vorliegende Problem, die von Steven D'Aprano. Beide Listen vorher in Zeichenketten umwandeln und dann damit den ``in``-Test zu machen sehe ich jetzt mal nicht als Lösung an, das ist eher ein Hack der nur für Listen funktioniert bei denen das zufällig funktioniert, aber halt nicht im allgemeinen Fall.

[snafu]

Wie wäre es damit?

Code: Alles auswählen

from collections import Sequence

def contains_sequence(seq, subseq):
    if not isinstance(seq, Sequence) or not isinstance(subseq, Sequence):
        raise TypeError('seq and subseq must be sequences')
    if not subseq:
        return True
    try:
        i = seq.index(subseq[0])
    except ValueError:
        # subseq[0] not in seq
        return False
    stop = i + len(subseq)
    if not isinstance(subseq, type(seq)):
        # Different types are never equal
        subseq = type(seq)(subseq)
    return seq[i:stop] == subseq

EDIT: Dieser Ansatz ist Mist, merke ich gerade. Er basiert auf dem ersten Vorkommen von ``subseq[0]`` und schaut sich nur die Elemente direkt nach diesem Vorkommen an. Es kann aber sein, dass erst ein späteres Vorkommen die gesuchte Untersequenz enthält.

[snafu]

Hier die verbesserte Version:

Code: Alles auswählen

from collections import Sequence

def contains_sequence(seq, subseq):
    if not isinstance(seq, Sequence) or not isinstance(subseq, Sequence):
        raise TypeError('seq and subseq must be sequences')
    if not subseq:
        return True
    if not isinstance(subseq, type(seq)):
        subseq = type(seq)(subseq)
    start = 0
    while True:
        try:
            start = seq.index(subseq[0], start)
        except ValueError:
            return False
        stop = start + len(subseq)
        if seq[start:stop] == subseq:
            return True
        start += 1

[DasIch]

Das kann man richtig sogar in wesentlich kürzer lösen, sofern man sich die paranoiden Typprüfungen spart.

Code: Alles auswählen

def startswith_sequence(sequence, subsequence):
    return sequence[:len(subsequence)] == subsequence


def contains_sequence(sequence, subsequence):
    return any(
        startswith_sequence(sequence[i:], subsequence)
        for i in range(len(sequence) - len(subsequence) + 1)
    )

EDIT: Leicht optimiert.

[snafu]

@DasIch
Deine Variante beinhaltet sicherlich weniger Quelltext. Falls die Ausführungszeit eine Rolle spielt, würde ich diese Variante allerdings nicht benutzen wollen, da sie eine quadratische Laufzeit hat. Aus diesem Grund hatte ich `.index()` benutzt und finde dessen Einsatz auch nach wie vor sinnvoll.

Hier nochmal eine Version basierend auf `any()` und `.index()` (ohne "paranoide Typprüfungen"):

Code: Alles auswählen

def iter_candidates(seq, subseq):
    sublen = len(subseq)
    start = 0
    while True:
        try:
            start = seq.index(subseq[0], start)
        except ValueError:
            return
        yield (start, start + sublen)
        start += 1

def contains_sequence(seq, subseq):
    if not subseq:
        return True
    return any(
        seq[start:stop] == subseq
        for start, stop in iter_candidates(seq, subseq)
    )

EDIT: Genau genommen ist die Laufzeit bei mir auch quadratisch. Aber der Worst Case ist eben unwahrscheinlicher. Mit anderen Worten: Es werden potenziell weniger Teillisten erzeugt und überprüft als ohne den Einsatz von `.index()`.

[BlackJack]

Wobei in beiden Lösungen potentiell viele Listenkopien durch slicing erstellt werden. Das ist IMHO einer der Fälle wo man in Python Code schreiben muss/sollte der eher nach C oder Java aussieht, so mit Zählschleifen über Indexwerte. Eben das was Steven D'Aprano in der weiter oben verlinkten Mailingliste gemacht hat.

In der Programmiersprache Io haben Listen eine `containsAll()`-Methode — sowas fehlt in Python irgendwie.

[snafu]

Unter Einbeziehung der Ideen aus dem verlinkten Thread:

Code: Alles auswählen

def iter_candidates(seq, subseq):
    for i, item in enumerate(seq):
        if item == subseq[0]:
            yield i

def contains_sequence(seq, subseq):
    if not subseq:
        return True
    if len(subseq) > len(seq):
        return False
    for start in iter_candidates(seq, subseq):
        for i, subitem in enumerate(subseq):
            if seq[start + i] != subitem:
                break
        else:
            return True
    return False

[snafu]

Hier nochmal etwas gekürzt mittels `all()`:

Code: Alles auswählen

def contains_sequence(seq, subseq, start=0):
    if not subseq:
        return True
    if len(subseq) > len(seq):
        return False
    while True:
        try:
            start = seq.index(subseq[0], start)
        except ValueError:
            return False
        if all(seq[start + i] == subitem for i, subitem in enumerate(subseq)):
            return True
        start += 1

EDIT: Übrigens deutlich langsamer als mein Slicing-basierter Ansatz.

Wenn ich den Code ab der Stelle mit `all()` wie folgt ersetze:

Code: Alles auswählen

stop = start + len(subseq)
        if seq[start:stop] == subseq:
            return True
        start += 1

...dann spuckt mir ein ``timeit contains_sequence([1,2,5,1,2,6,1,2,3,4,5], [1,2,3,4,5])`` Laufzeiten aus, die nur halb so groß sind wie mit dem `enumerate()`-basierten Loop.

[Sirius3]

@snafu: das Kopieren von relativ kurzen Listslices geht ja auch viel schneller als eine enumerate-Schleife in Python. Und wenn Du bei all sowieso bis zum Schluß testen mußt, gibt es wohl keinen Fall, wo die all-Methode schneller wäre, es sei denn, der Speicher wird knapp. Als Kompromiss könnte man ja Junks von 100-Elementen vergleichen, dann hat man den nativen Geschwindigkeitsvorteil und keine große Speicherverschwendung.

[BlackJack]

Das ist einfach etwas was in C programmiert sein sollte wenn's effizient sein soll und IMHO eine Methode auf `list` sein sollte. Wenn ich Python 3 verwenden würde, dann würde ich hier glatt mal in den Archiven stöbern ob das schon mal diskutiert wurde und ggf. eine Implementierung schreiben.

[snafu]

Das ist einfach etwas was in C programmiert sein sollte wenn's effizient sein soll und IMHO eine Methode auf `list` sein sollte.

Sowohl auf `list` als auch auf `tuple`, finde ich. Da kann man jetzt entweder an beiden APIs Änderungen vornehmen oder `containsAll()` als allgemeine Funktion schreiben und diese z.B. über das `operator`-Modul anbieten. Ich habe mal zum Spaß etwas auf Basis des `PySequence`-Protokolls geschrieben. Ich werde das noch ein bißchen ausarbeiten und stelle es vielleicht dann in ein paar Tagen als Verbesserungsvorschlag vor.

[snafu]

Ich habe mal eine bespielhafte Implementierung in C auf den Python-Bugtracker gesetzt. Es kamen auch schon ein paar Rückmeldungen. Der Tenor ist anscheinend, dass man die Idee grundsätzlich nicht schlecht findet, aber sich nicht sicher ist, ob dies Teil der Standardbibliothek werden soll. Eine endgültige Entscheidung steht aber wohl noch aus. Für Interessierte: http://bugs.python.org/issue25898

[Üpsilon]

boah, da hab ich ja was losgetreten :O Danke!
Meine Lösung sieht i.wie so aus (hab es grade nicht dabei):

Code: Alles auswählen

def ist_teilliste(kleine_liste, grosse_liste):
    if len(kleine_liste) > len(grosse_liste): return False
    if grosse_liste[:len(kleine_liste)] == kleine_liste: return True
    return ist_teilliste(kleine_liste[1:], grosse_liste)

... Unglaubliche Effizienz durch Rekursion ...

[snafu]

Hier mal aus Spaß an der Freude eine Iterator-basierte Umsetzung:

Code: Alles auswählen

#!/usr/bin/env python3

from collections import deque
from itertools import chain, islice

def dropuntil(iterable, needle):
    """
    Advance `iterable` until a sequence with all items of `needle` (with
    respect to their order) is found. Then yield all remaining items
    starting with the first item of `needle`. Yield nothing if `iterable`
    does not contain the given needle.
    """
    iterator = iter(iterable)
    window = deque(maxlen=len(needle))
    window.extend(islice(iterator, len(needle)))
    if len(window) == len(needle):
        while any(a != b for a, b in zip(window, needle)):
            try:
                window.append(next(iterator))
            except StopIteration:
                return
        yield from chain(window, iterator)

def main():
    print(list(dropuntil([1,2,9,3,4,3,5,2,3,4,2,3], [2,3])))
    print(list(dropuntil([1,2,9,3,4,3,5,2,3,4,2,3], [8,9])))
    print(''.join(dropuntil('xxxhamyyyspamzzzeggs', 'spam')))

if __name__ == '__main__':
    main()

[snafu]

Hier nochmal mit `map` anstelle der Generator Comprehension zur Performancesteigerung:
http://pastebin.com/LUYUi5Zk

[BlackJack]

Ich würde es ja als `dropwhile()` implementieren. Die `needle` hat der Aufrufer ja schon, wenn er die vor dem Ergebnis haben möchte, kann er den `chain()`-Aufruf selber machen. Wenn er die `needle`-Daten dagegen nicht braucht, dann macht die Funktion erst ein `chain()` was der Aufrufer mit einem `islice()` wieder ”rückgängig” machen muss, also zwei Iteratorindirektionen zusätzlich.