Поиск значений списка в другом списке с использованием Python

Question

Я пытаюсь найти подсписку списка. Значение, если list1 говорит, что [1,5] находится в списке2, скажем [1,4,3,5,6], чем он должен вернуть True. То, что я до сих пор это:

for nums in l1: 
    if nums in l2: 
     return True 
    else: 
     return False 

Это было бы верно, но я пытаюсь вернуться Правда, только если песни1 в list2 в соответствующем порядке. Поэтому, если list2 является [5,2,3,4,1], он должен возвращать False. Я думал о том, как сравнивать значения индекса list1 с использованием <, но я не уверен.

Answer 1

Этот вопрос немного похож на домашнюю работу, и по этой причине я хотел бы потратить время и обсудить, что может произойти неправильно с фрагментом, указанным в вопросе.

Хотя вы используете слово в своей множественной форме для переменной nums, вам нужно понять, что Python будет использовать эту переменную для хранения одного элемента из l1 за раз и пройти через блок кода в этом " для блока ", один раз для каждого другого элемента.

Таким образом, результатом вашего текущего фрагмента будет выход с самой первой итерации с использованием True или False, если случайно попадают первые элементы в списке.

Редактировать: Да, A1, точно так же, как вы сказали: логика завершается с помощью True после первой итерации. Это происходит из-за «возврата», когда nums находится в l2.
Если вы ничего не должны были делать в случае «найденного», цикл будет продолжаться с завершением любой логики в блоке (здесь нет), и тогда она начнет следующую итерацию. Следовательно, он выйдет только с возвращаемым значением «False», если элемент из l1 не найден l2 (действительно, после самого первого такого не найденного элемента). Поэтому ваша логика почти правильна (если бы ничего не делалось в «найденном случае»), то одна потерянная была бы возвращена «True», систематически после цикла for (поскольку, если он не вышел с False значением внутри цикла, то все элементы l2 находятся в l1 ...).

Существует два способа изменить код, чтобы он ничего не делал для «найденного случая».
- используя pass, что является удобным способом проинструктировать Python ничего не делать;
«pass» обычно используется, когда «что-то», то есть какое-то действие синтаксически требуется, но мы ничего не хотим делать, но его также можно использовать при отладке и т. Д.
- переписывая тест как «не в», вместо этого

if nums not in l2: 
    return False 
#no else:, i.e. do nothing at all if found 

Теперь ... Вступление в подробности.
В вашей программе может быть недостаток (с предлагаемыми изменениями), то есть он будет рассматривать l1 как подсписку l2, даже если l1 скажет 2 элемента со значением 5, в котором l2 имеет только одно такое значение. Я не уверен, что такое рассмотрение является частью проблемы (возможно, понимание состоит в том, что оба списка являются «наборами», без каких-либо дублирующих элементов). Однако, если дубликаты были допущены, вам придется немного усложнить логику (возможным способом было бы сделать внутреннюю копию l2 и каждый раз «nums» найти в копии l2, чтобы удалить этот элемент.

Другой что возможно, список можно назвать только подсписком, если его элементы найдены в том же порядке, что и элементы в другом списке ... Опять же все зависит от способа определения проблемы ...Кстати, некоторые предлагаемые решения, такие как Алекс Мартелли, написаны таким образом, потому что они решают проблему таким образом, что порядок элементов со списками имеет значение.

Answer 2

try: 
    last_found = -1 
    for num in L1: 
    last_found = L2.index(num, last_found + 1) 
    return True 
except ValueError: 
    return False 

index метод списка L2 возвращает позицию, в которой первый аргумент (num) находится в списке; называется, как здесь, со вторым аргументом, он начинает искать в списке в этой позиции. Если index не находит то, что он ищет, он вызывает исключение ValueError.

Таким образом, этот код использует этот подход для поиска каждого элемента num от L1, на заказ, внутри L2. В первый раз ему нужно начать смотреть с позиции 0; каждый последующий момент времени, он должен начать смотреть с позиции сразу после последней, где он нашел предыдущий элемент, то есть last_found + 1 (поэтому в начале мы должны установить last_found = -1, чтобы начать смотреть с позиции 0 в первый раз).

Если каждый элемент в L1 найден таким образом (то есть он найден в L2 после позиции, где был найден предыдущий элемент), то два списка удовлетворяют заданному условию, а код возвращает True. Если какой-либо элемент L1 когда-либо не найден, код ловит результирующее исключение ValueError и просто возвращает False.

Другой подход заключается в использовании итераторов над двумя списками, которые могут быть сформированы с помощью встроенной функции iter. Вы можете «продвигать» итератор, вызывая встроенный next; это повысит StopIteration, если нет «следующего элемента», то есть итератор исчерпан. Вы также можете использовать for на итераторе для более гладкого интерфейса, где это применимо. Подход низкого уровня с использованием ИТЭР/следующая идея:

i1 = iter(L1) 
i2 = iter(L2) 
while True: 
    try: 
    lookfor = next(i1) 
    except StopIteration: 
    # no more items to look for == all good! 
    return True 
    while True: 
    try: 
     maybe = next(i2) 
    except StopIteration: 
     # item lookfor never matched == nope! 
     return False 
    if maybe == lookfor: 
     break 

или немного выше уровня:

i1 = iter(L1) 
i2 = iter(L2) 
for lookfor in i1: 
    for maybe in i2: 
    if maybe == lookfor: 
     break 
    else: 
    # item lookfor never matched == nope! 
    return False 
# no more items to look for == all good! 
return True 

В самом деле, единственным важным использование iter здесь, чтобы получить i2 - с внутренним контуром, поскольку for maybe in i2 гарантирует, что внутренний цикл не будет начинать смотреть с самого начала каждый раз, но, скорее, он будет продолжать смотреть, где он последний раз. Внешний цикл может также использоваться для for lookfor in L1:, так как он не имеет проблемы с перезапуском.

Ключ, здесь - этопредложение циклов, которое срабатывает, если и только если цикл не был прерван break, а скорее естественным путем.

Работая над этой идеей, нам снова напомнили о операторе in, который также можно использовать для продолжения, где он в последний раз оставался простым использованием итератора. Большое упрощение:

i2 = iter(L2) 
for lookfor in L1: 
    if lookfor not in i2: 
    return False 
# no more items to look for == all good! 
return True 

Но теперь мы понимаем, что это именно скороговоркой абстрагируется от коротких замыкания any и all встроенных «короткого замыкания аккумулятора» функции, так что ...:

i2 = iter(L2) 
return all(lookfor in i2 for lookfor in L1) 

, который, я считаю, почти так же прост, как вы можете получить.Единственный неэлементарный бит, оставшийся здесь, - это то, что вы должны использовать только iter(L2), только один раз, чтобы убедиться, что оператор in (по сути внутренний цикл) не перезапускает поиск с самого начала, а скорее продолжает каждый раз, откуда последний раз.

Answer 3

У меня есть чувство, что это более интенсивным, чем ответ Алекса, но здесь была моя первая мысль:

def test(list1, list2): 
    try: 
     for num in list1: 
      list2 = list2[list2.index(num):] 
    except: return False 
    else: return True 

Edit: Просто попробовал. Его быстрее. Это близко.

Редактировать 2: Перемещена попытка/исключение из цикла (вот почему другие должны смотреть на ваш код). Спасибо, гниблер.

Answer 4

Я думаю, что это решение является самым быстрым, поскольку оно выполняет итерацию только один раз, хотя и в более длинном списке и выходит до окончания итерации, если совпадение найдено. (Edit: Тем не менее, это не так сжато или же быстро, как последнее решение Алекса)

def ck(l1,l2): 
    i,j = 0,len(l1) 
    for e in l2: 
     if e == l1[i]: 
      i += 1 
     if i == j: 
      return True 
    return False 

Улучшение был предложен Анурагом Uniyal (см комментария) и находит свое отражение в приведенных ниже разборках.

Вот некоторые результаты скорости для диапазона соотношений размера списка (список l1 в список 10-элемент, содержащий случайные значения от 1-10. Список l2 находится в диапазоне от 10-1000 в длину (а также содержат случайные значения от 1 -10)

код, который сравнивает запускать раз и участки результаты:.

import random 
import os 
import pylab 
import timeit 

def paul(l1,l2): 
    i = 0 
    j = len(l1) 
    try: 
     for e in l2: 
      if e == l1[i]: 
       i += 1 
    except IndexError: # thanks Anurag 
     return True 
    return False 

def jed(list1, list2): 
    try: 
     for num in list1: 
      list2 = list2[list2.index(num):] 
    except: return False 
    else: return True 

def alex(L1,L2): # wow! 
    i2 = iter(L2) 
    return all(lookfor in i2 for lookfor in L1) 

from itertools import dropwhile 
from operator import ne 
from functools import partial 

def thc4k_andrea(l1, l2): 
    it = iter(l2) 
    try: 
     for e in l1: 
      dropwhile(partial(ne, e), it).next() 
     return True 
    except StopIteration: 
     return False 


ct = 100 
ss = range(10,1000,100) 
nms = 'paul alex jed thc4k_andrea'.split() 
ls = dict.fromkeys(nms) 
for nm in nms: 
    ls[nm] = [] 

setup = 'import test_sublist as x' 
for s in ss: 
    l1 = [random.randint(1,10) for i in range(10)] 
    l2 = [random.randint(1,10) for i in range(s)] 
    for nm in nms: 
     stmt = 'x.'+nm+'(%s,%s)'%(str(l1),str(l2)) 
     t = timeit.Timer(setup=setup, stmt=stmt).timeit(ct) 
     ls[nm].append(t) 

pylab.clf() 
for nm in nms: 
    print len(ss), len(ls[nm]) 
    pylab.plot(ss,ls[nm],label=nm) 
    pylab.legend(loc=0) 

    pylab.xlabel('length of l2') 
    pylab.ylabel('time') 

pylab.savefig('cmp_lsts.png') 
os.startfile('cmp_lsts.png') 

результаты:

Answer 5

У меня есть трудное время, видя такие вопросы, и не желая, чтобы обработка списка Python была больше похожа на Haskell's. Это кажется намного более простым решением, чем все, что я мог придумать в Python:

contains_inorder :: Eq a => [a] -> [a] -> Bool 
contains_inorder [] _ = True 
contains_inorder _ [] = False 
contains_inorder (x:xs) (y:ys) | x == y = contains_inorder xs ys 
           | otherwise = contains_inorder (x:xs) ys 

Answer 6

Это должно быть легко понять и избежать углового случая хорошо, как вам не нужно работать с индексами:

def compare(l1, l2): 
    it = iter(l2) 
    for e in l1: 
     try: 
      while it.next() != e: pass 
     except StopIteration: return False 
    return True 

он пытается сравнить каждый е lement из l1 к следующему элементу в l2.
Если нет следующего элемента (StopIteration), он возвращает false (он посетил весь l2 и не нашел текущий e), иначе он его нашел, поэтому он возвращает true.

Для более быстрого выполнения может помочь поставить блок попробовать вне для:

def compare(l1, l2): 
    it = iter(l2) 
    try: 
     for e in l1: 
      while it.next() != e: pass 
    except StopIteration: return False 
    return True 

Answer 7

ультра-оптимизированная версия решения Андреа:

from itertools import dropwhile 
from operator import ne 
from functools import partial 

def compare(l1, l2): 
    it = iter(l2) 
    try: 
     for e in l1: 
      dropwhile(partial(ne, e), it).next() 
     return True 
    except StopIteration: 
     return False 

Это можно записать еще более функциональный стиль :

def compare(l1,l2): 
    it = iter(l2) 
    # any(True for ..) because any([0]) is False, which we don't want here 
    return all(any(True for _ in dropwhile(partial(ne, e), it)) for e in l1)