Boolescher Ausdruck für if Liste ist in anderen Liste

Was ist eine effiziente Möglichkeit zu überprüfen, ob eine Liste in einer anderen Liste ist? Etwas wie:Boolescher Ausdruck für if Liste ist in anderen Liste

[2,3] in [1,2,3,4]  #evaluates True 
[1,5,4] in [5,1,5,4] #evaluates True 
[1,2] in [4,3,2,1]  #evaluates False

Bestellung innerhalb der Liste zählt.

Quelle

2016-08-11 Sarah Pierson

Müssen die Elemente aus der ersten Liste in der zweiten Liste fortlaufend sein? Was zum Beispiel sollte [1,2] in [1,3,2] zurückkehren? –

false, weil es konsekutiv sein muss –

Diese Frage ist nichts wie http://stackoverflow.com/questions/3313590/check-for-presence-of-a-sublist-in-python, die die Daten ist binär und verwendet Verkettung. Die Daten können hier beliebige numerische Werte sein, z. [2, 55, 100]. In diesem Fall ist die vorgeschlagene Lösung in der Frage "Duplikat" nicht anwendbar. – Alexander

def check_ordered_sublist_in_list(sub_list, main_list): 
    sub_list = np.array(sub_list) 
    main_list = np.array(main_list) 
    return any(all(main_list[n:(n + len(sub_list))] == sub_list) 
       for n in range(0, len(main_list) - len(sub_list) + 1)) 

>>> check_ordered_sublist_in_list([2, 3], [1, 2, 3, 4]) 
True 

>>> check_ordered_sublist_in_list([1, 5, 4], [5, 1, 5, 4]) 
True 

>>> check_ordered_sublist_in_list([1, 2], [4, 3, 2, 1]) 
False

Dieser wandelt die Listen Arrays NumPy (für die Recheneffizienz) und verwendet dann das Schneiden zu überprüfen, ob die sub_list innerhalb der Scheibe enthalten ist. Jeder Erfolg gibt True zurück.

Quelle

2016-08-11 01:10:31 Alexander

Dies scheint wie ein Missbrauch von "numpy". Die 'np.arrays' zu konstruieren ist eine ziemlich teure Operation. Dies wird höchstwahrscheinlich negieren, welche rechnerische Effizienz auch immer mit der Verwendung von "numpy" erzielt wird, nur um einige einfache Slices auszuführen (besonders, da die Listen in dem Beispiel sehr klein sind). – pzp

@pzp Möglicherweise, aber die Listen sind in diesem einfachen Beispiel nur klein. Tatsächliche Anwendungsfälle sind in der Regel sehr viel komplexer. Ich stimme jedoch zu, dass die von @mfripp vorgeschlagene "is_in" -Lösung effizienter ist. – Alexander

Die Verwendung von "ordered_sublist" im Funktionsnamen scheint redundant zu sein - sind nicht alle Listen in Python geordnet? – martineau

Sie könnten so:

def is_in(short, long): 
    return any(short==long[i:i+len(short)] for i in range(len(long)-len(short)+1)) 

is_in([2,3], [1,2,3,4]) # True 
is_in([1,5,4], [5,1,5,4]) # True 
is_in([1,2], [4,3,2,1]) # False

Wenn Sie wirklich auf Geschwindigkeit, sind diese Ausdrücke 20-30% schneller:

def segments(long, length): 
    return [long[i:i+length] for i in range(len(long)-length+1)] 

def is_in_seg(short, long): 
    return short in segments(long, len(short)) 

is_in_seg([1,5,4], [5,1,5,4])  # true 
[1,5,4] in segments([5,1,5,4], 3) # true

Und das ist 47% schneller, aber es nutzt Tupeln anstelle von Listen:

import itertools 
def segments_zip(long, length): 
    return itertools.izip(*[long[i:] for i in xrange(length)]) 

(2,3) in segments_zip((1,2,3,4), 2) # True 
(1,5,4) in segments_zip((5,1,5,4), 3) # True 
(1,2) in segments_zip((4,3,2,1), 2) # False

Die zusätzliche Geschwindigkeit kommt itertools.izip verwenden, welche Segmente zu erzeugen stoppen kann, wenn ein Spiel gefunden; Verwendung von xrange, wodurch vermieden wird, dass die gesamte Bereichsliste erstellt wird; und von Tupeln, die im Allgemeinen etwas schneller als Listen sind. Aber der kleine Geschwindigkeitsvorteil wird verschwinden, wenn Sie Listen in Tupel konvertieren müssen, um sie zu verwenden.

Quelle

2016-08-11 01:33:08

Boolescher Ausdruck für if Liste ist in anderen Liste

Antwort

Verwandte Themen