Нахождение индекса попарных элементов
Учитывая цель ('b', 'a') и входы:
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
Цель состоит в том, чтобы найти местоположение непрерывного ('b', 'a') элемент и получить вывод:
>>> find_ba(x0)
0
>>> find_ba(x1)
0
>>> find_ba(x2)
None
>>> find_ba(x3)
1
С использованием pairwise рецепт:
from itertools import tee
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
Я мог бы сделать это, чтобы получить желаемый результат:
def find_ba(x, target=('b', 'a')):
try:
return next(i for i, pair in enumerate(pairwise(x)) if pair == target)
except StopIteration:
return None
Но это потребовало бы от меня перебрать все пары символов, пока я не найду первый экземпляр. Есть ли способ найти индекс попарных элементов без зацикливания всех символов?
Отвечая на вопрос @MatthiasFripp в комментариях:
Ваши элементы находятся в списках или типах (как показано) или в генераторе (например, чтение из дескриптора файла)?
X * - это все кортежи строк. Таким образом, они могут быть доступны через индекс. Но если ответ / решение может работать для кортежей и генератора, это будет здорово!
Можете ли вы сказать, сколько списков вам нужно искать и как долго они находятся? Это помогло бы предложить стратегию поиска.
Длина кортежей не фиксирована. Они могут быть размером> 2.
15 ответов
Самый быстрый общий алгоритм поиска будет иметь O(n) средняя производительность (так называемый линейный поиск), это означает, что у вас нет альтернативы (кроме, может быть, для постоянного фактора), чем для обработки каждого элемента.
Учитывая ваш вопрос:
Есть ли способ найти индекс попарных элементов без зацикливания всех символов?
Это возможно (это все еще O(n) хотя), только глядя на каждый второй элемент:
from itertools import count
def find_ab(tup):
for idx in count(start=1, step=2):
try:
if tup[idx] == 'b':
if tup[idx+1] == 'a':
return idx
elif tup[idx] == 'a':
if tup[idx-1] == 'b':
return idx-1
except IndexError:
break
В худшем случае он все равно будет сравнивать все элементы, но пропустит один элемент для каждого элемента с нечетным индексом, который не является 'b' или же 'a',
Это немного похоже на мошенничество, поэтому позвольте мне объяснить, почему обычные альтернативы невозможны в вашем случае:
Бинарный поиск
Бинарный поиск нужно только сравнить log(n) элементы, но это требует сортировки последовательности. Ваши примеры не отсортированы, поэтому для их сортировки потребуется O(n*log(n)) операции - которые не просто обрабатывали бы каждый элемент один раз, но обрабатывали бы некоторые из них несколько раз. Не то чтобы я все же знал разумный способ сортировки соседних элементов.
Поиск корзины (или хеш-таблицы)
У вас есть кортежи, поэтому создание хэш-таблицы (dict) не имеет смысла, потому что для создания этой структуры вам потребуется обработать каждый элемент.
Но если вы планируете сделать несколько таких поисков для пар, вы можете создать словарь один раз (O(n)) и делать много поисков потом в O(1):
d = {}
for idx, pair in enumerate(pairwise(x0)):
if pair not in d: # keep only the first index for each pair
d[pair] = idx
>>> d.get(('b', 'a'), None)
0
Однако этот подход намного медленнее, если вы хотите искать только одну пару, потому что вы теряете "поведение короткого замыкания" (останавливается, как только найдено совпадение), и вы обрабатываете все элементы при создании словаря.
Другие подходы
Помимо общих подходов:
O(n)линейный поискO(log(n))бинарный поиск (для отсортированных данных)O(1)поиски (для поиска с хэшированием или других проблем поиска, которые просто нужно искать в некоторых "корзинах")
Как правило, вы можете использовать любую структуру или знания о ваших данных, чтобы уменьшить количество элементов, которые необходимо обработать. Проблема в основном в том, что (возможно) уже нет существующих структур данных для этих, и самодельные реализации часто оказываются на порядки медленнее, чем наивные подходы "обрабатывать все элементы". Но если у вас есть метаинформация о ваших последовательностях, вы можете использовать ее.
Заключительные замечания
Рецепт для парного на самом деле довольно хороший, но вы также можете использовать iteration_utilities.successive 1 Последнее, что я проверил, было примерно в 1,5-2 раза быстрее, чем рецепт. Даже если вы не измените подход и согласитесь с тем, что вам нужно обрабатывать все (или почти все) элементы, в худшем случае это может быть быстрее!
Эти данные, вероятно, были сгенерированы. Может быть, стоит на самом деле "искать" элементы при создании. Таким образом, вам не нужно делать дополнительный проход по данным вообще. Или вы могли бы создать dict при создании набора данных (что позволяет O(1) поиски потом). Иногда полезно посмотреть на процесс, который сгенерировал / загрузил / получил набор данных, если есть какой-то способ извлечения информации.
Теперь, после написания всего этого текста, мне нужно заявить очевидное:
Ваш подход действительно хорош. Даже если ему нужно обработать все элементы в худшем случае, он использует идеально подходит (pairwise -рецепт) для решения проблемы, и она должна работать очень быстро, даже для длинных входов. Для кортежа, содержащего 1 миллион 'z' на моем компьютере нужно всего 200 мс. Таким образом, вы можете обрабатывать несколько миллионов элементов в секунду (даже на старых и медленных компьютерах, таких как мой). Это, вероятно, недостаточно быстро для больших данных, но тогда чистый python не является хорошим языком для обработки больших данных (обычно вам нужно написать расширение C, использовать Cython или какой-либо NumPy, Pandas или производный подход). Так же next функция на генераторе ленива (если вы используете itertools.izip на python2 вместо zip), поэтому вы обрабатываете каждый кортеж только до тех пор, пока не найдете соответствие.
Лично я бы просто использовал ваш оригинальный подход. Или, если бы мне нужно было найти несколько пар, я бы просто создал словарь, о котором я упоминал ранее (возможно, даже сериализовал его), и выполнял поиск в нем.
Причина щедрости явно требует "достоверных и / или официальных источников". К счастью, "алгоритмы поиска" хорошо изучены, поэтому вы можете найти объяснения для каждого из упомянутых подходов в основных учебниках по алгоритмам. Например:
- Cormen, et. al - Введение в алгоритмы
Седжвик и Уэйн - Алгоритмы
Википедия: "Линейный поиск"
- Википедия: "Бинарный поиск"
- Википедия: "Hashtable" (это по сути
dict).
Также есть небольшой обзор временных сложностей типов Python в вики Python: "TimeComplexity". Для поиска вы должны проверить "Получить элемент" или "в".
1 Раскрытие информации: я являюсь автором этой сторонней библиотеки.
Не очень впечатляет, хотя это работает в вашем случае, проверьте это.
мы просто извлекаем индекс соответствующего элемента в выборке и проверяем, является ли он последовательным или нет.
def consecutive_index(src,sample):
result = None
il = [src.index(a) for a in sample if a in src]
if len(il) == len(sample) and len(range(il[0],il[-1]))==1:
result = il[0]
return result
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
sample = ('b', 'a')
##TEST your given combinations.
print consecutive_index(x0,sample) #expected 0
print consecutive_index(x1,sample) #expected 0
print consecutive_index(x2,sample) #expected None
print consecutive_index(x3,sample) #expected 1
Может быть, например, используя регулярные выражения? Ниже вы можете найти две функции. findPair будет возвращать значения точно так же, как в вашем примере. findPairs будет искать все неперекрывающиеся вхождения и возвращать их начальные позиции в списке.
import re
# Function looks for all non-overlapping occurrences of pair (b, a)
# and returns a list containing their starting positions
def findPairs(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return [x.regs[0][0] for x in list(re.finditer(y, x))]
except AttributeError:
return None
# Function looks for first occurrence of the pair (b, a)
# and returns starting position if there was a match
# or None when the match was not found
def findPair(x, b, a):
x = str().join(x)
y = str().join([str(b), str(a)])
try:
return re.search(y, x).regs[0][0]
except AttributeError:
return None
if __name__ == "__main__":
# first occurrence
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
outx0 = findPair(x0, 'b', 'a') # 0
outx1 = findPair(x1, 'b', 'a') # 0
outx2 = findPair(x2, 'b', 'a') # None
outx3 = findPair(x3, 'b', 'a') # 1
# multiple occurrences:
x4 = ('z', 'b', 'a', 'a', 'z', 'b', 'a', 'a')
outx4 = findPairs(x4, 'b', 'a') # [1, 5]
РЕДАКТИРОВАТЬ:
Если вы не хотите / не любите регулярные выражения, и вас интересует только первое вхождение, вы можете просто использовать метод find() и определите функцию для поиска пар как:
def findPairNoRe(x, b, a):
y = str().join([str(b), str(a)])
res = str().join(x).find(y)
if res == -1:
return None
else:
return res
Есть более короткие формулы для этого, но нет способа полностью избежать зацикливания. Тем не менее, вы можете ускорить его с помощью multiprocessing (см. конец). Во-первых, вот несколько методов поиска (все O(n)) с различными сочетаниями скорости и простоты.
Довольно простой, быстрый код для использования, если значения находятся в кортежах или списках:
def find_ba(tup, target):
last_check = len(tup)-len(target)
for i, c in enumerate(tup):
# note: the test below only uses c 95% of the time,
# which makes it pretty fast
if c == target[0] and i <= last_check and tup[i:i+len(target)] == target:
return i
return None
Не так просто, но быстрее, вдохновленный @MSeifert, но оптимизированный для более длинных целей:
def find_ba(tup, target):
import itertools
search = set(target)
target_len = len(target)
for i in count(start=1, step=target_len):
try:
if tup[i] in search: # O(1) reverse lookup
# search in this neighborhood
c = tup[i]
j = 0
while True:
try:
# find next occurrence of c in the target
j = target[j:].index(c)
except ValueError: # no more occurrences of c in target
break
# align tup and target and check for a match
if j >= i and tup[i-j:i-j+target_len] == target:
return i-j
except IndexError:
break
return None
Поскольку вы уже столкнулись с проблемой создания кортежей символов, вы можете вместо этого создать строки, а затем позволить Python выполнить оптимизацию в собственном коде C:
def find_ba(x, target):
# assuming x and target are both strings
pos = x.find(target)
return pos if pos >= 0 else None
(Хотя на самом деле вам, вероятно, лучше выполнять поиск при создании кортежей или строк, если это возможно.)
Если значения находятся в генераторах, то это будет работать (очень похоже на то, что у вас уже есть). Это будет более эффективно, чем создание длинных кортежей и их поиск, если основной источник работает медленно (например, чтение элементов с диска):
import itertools
def find_ba(lst, target):
a, b = itertools.tee(lst)
next(b)
for i, pair in enumerate(zip(a, b)):
if pair == target:
return i
return None
Примечание: на Python 2.7 используйте itertools.izip вместо zip на Python 2.7.
Основной способ ускорить это будет использовать multiprocessing библиотека. Если у вас есть большое количество входов для обработки, вы можете использовать multiprocessing.Pool.map отправить каждого другому работнику в круговом стиле. Если у вас есть только несколько входов, и каждый из них очень длинный, то вы можете использовать itertools.islice, чтобы разделить их на длинные куски, а затем отправить каждый кусок в multiprocessing.Pool.map пока не получишь удар; тогда вы можете начать обработку следующего ввода. По вашему вопросу я не могу сказать, какой из этих подходов был бы наиболее эффективным.
Решение:
Вы можете использовать numpy, где найти последовательность после построения массива парных последовательностей.
#np.roll(x1,-1) shifts the list leftwise one element. np.core.defchararray.add builds a paired sequence.
np.where(np.core.defchararray.add(x1,np.roll(x1,-1)) == 'ba')[0]
Тестовое задание
for x in [x0,x1,x2,x3]:
print (np.where(np.core.defchararray.add(x,np.roll(x,-1)) == 'ba'))[0]
[0]
[0]
[]
[1]
Вы можете сделать это путем преобразования списков в строку.
def findba(x,target):
x1 = "".join(x)
target1 = "".join(target)
if target1 in x1:
return x1.index(target1)
else:
return None
ab = ('b','a')
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
print findba(x0,ab)
print findba(x1,ab)
print findba(x2,ab)
print findba(x3,ab)
Без какого-либо обещания относительно характера данных (т. Е. Предположения, что они случайные), поиск не может быть лучше, чем O(n). В лучшем случае вы сможете уменьшить количество операций с точки зрения тильды (т.е. уменьшить его в несколько раз), оптимизировав проблему, используя конкретную информацию о том, что вы пытаетесь сделать, включая: размер цели, повторение символов в цель (при поиске 'b' 'b' 'a' мы можем посмотреть на любой другой символ и узнать, что это должен быть 'b', чтобы соответствовать нашей последовательности, а затем посмотреть на окружающие символы) или любую другую информацию, которую мы можем получить с помощью быстрый анализ на меньшем наборе данных (опять же, предполагая, что список последовательностей является неизвестной величиной). Например, одной вещью, которую я изучал, был поиск цели путем итерации по длине цели и определения, был ли это один из символов, которые мы искали. Проблема с этим, конечно же, заключается в том, что вместо поиска каждого индекса в списке (теперь мы касаемся элементов len(list)/len(target)), теперь мы выполняем больше операций с каждым элементом, к которому мы прикасаемся (другими словами, для 'b', 'a'мы ищем каждые два элемента, но мы ищем две вещи). Это ничего не значит с точки зрения уменьшения количества операций, однако это значительно уменьшило бы количество элементов, которые вы должны загрузить из вторичного хранилища памяти, предполагая, что вы планируете искать цели в довольно больших последовательностях, и именно поэтому вы избегают зацикливаться на каждом элементе. Существует также несколько способов, с помощью которых вы можете использовать многопараллельность для повышения эффективности поиска, если повышение эффективности является вашей единственной целью. (Просто не забывайте использовать многопроцессорность, а не многопоточность, если вы выбираете этот маршрут, так как модуль многопоточности в Python поддерживает только параллелизм, а не многопараллельность из-за того, что интерпретатор создает узкие места в потоках).
В качестве заключения и прямого ответа на вопрос, который вы задали, да, вполне возможно найти индекс попарных элементов, не просматривая каждый элемент в последовательности. Однако для этого потребуется сначала просмотреть конкретную информацию о проблеме, а затем применить эту информацию к поиску. Я думаю, что лучшим методом будет поиск, сначала проанализировав данные, а затем выполнить метод поиска, который наилучшим образом соответствует этим данным. Другими словами, если есть повторы, вы можете использовать это, но если нет, вы можете вернуться к другому поиску.
Это решение ищет первый элемент target с использованием index метод списка. Затем он проверяет, соответствует ли следующий элемент в списке второму элементу target, Если нет, то находит следующее вхождение 'b' и снова проверяет следующий элемент. Стирка промыть повторить.
Это не зацикливает все пары, но ищет первый элемент в ожидаемой паре, а затем проверяет следующий элемент.
def find_ba(x, target=('b','a')):
try:
ind = 0
while ind < len(x):
ind += x[ind:].index(target[0])
if x[ind+1] == target[1]:
return ind
ind += 1
except ValueError:
return None
Тестовое задание:
# 100 random letters
letters = ['f', 'y', 'h', 'u', 't', 'l', 'y', 'u', 'm', 'z', 'a', 'a',
'i', 't', 'g', 'm', 'b', 'l', 'z', 'q', 'g', 'f', 'f', 'b',
'b', 'a', 'c', 'z', 'n', 'j', 'v', 'b', 'k', 'j', 'y', 'm',
'm', 'f', 'z', 'x', 'f', 'q', 'w', 'h', 'p', 'x', 't', 'n',
'm', 'd', 'z', 'q', 'v', 'h', 'b', 'f', 'q', 'd', 'b', 's',
'a', 't', 'j', 'm', 'h', 'r', 'd', 'n', 'e', 'k', 'y', 'z',
'd', 'e', 'x', 'h', 'r', 'z', 'b', 'n', 'q', 'v', 't', 'q',
'f', 'w', 'b', 'w', 'f', 'c', 'f', 'h', 'q', 'o', 'r', 'f',
'w', 'w', 'n', 'v']
find_ba(letters) # 24
Метод с использованием zip для сравнения:
def find_ba1(x):
try:
return [(i,j) for i,j in zip(x[:-1], x[1:])].index(('b', 'a'))
except ValueError:
return None
И небольшой тест скорости:
%timeit find_ba(letters)
100000 loops, best of 3: 2.31 µs per loop
%timeit find_ba1(letters)
100000 loops, best of 3: 8.4 µs per loop
Как уже было сказано, вы не можете избежать зацикливания на всех персонажах. Вы можете сделать его ленивым и выполнять итерации только один раз над входным кортежем следующим образом (при условии Python 3):
from itertools import islice, tee
def find_ba(x):
pairs = zip(*(islice(g, i, None) for i, g in enumerate(tee(x, 2))))
return next(
(i for i, pair in enumerate(pairs) if pair == ('b', 'a')),
None)
Если вы неоднократно ищите разные цели в одних и тех же входах, вы можете избежать циклического обхода входов каждый раз, создавая хэш расположения всех уникальных строк, как показано в коде ниже. Это требует одной петли через каждый вход для начальной настройки, но тогда поиск почти мгновенный (без зацикливания).
# store first occurrence of each unique 2-char string (O(n))
x1_first = dict()
target_len = 2
for i in range(len(x1)):
x1_first.setdefault(x1[i:i+target_len], i)
# find first occurrence of a particular string without looping (O(1))
print x1_first.get(('a', 'b'), None)
Примечание: это очень похоже на один из ответов @MSeifert, но показывает, как обрабатывать произвольные целевые длины. Если у вас есть несколько целевых длин, о которых нужно беспокоиться, вам нужно будет создать отдельные dicts для каждой длины, что будет неэффективно для хранения. В этом случае вам, вероятно, будет лучше создать отсортированный список самых длинных возможных целей (например, 10 символов), а затем искать его с помощью деления пополам (см. Модуль bisect). Для более коротких подстрок вам потребуется отсканировать несколько совпадений и вытащить самую раннюю.
Я пытался сравнить метод Майферта и мой. Мой код был получен из кода MSeifert, но попытался развить еще один шаг, то есть перейти к следующему целевому слову вместо того, чтобы идти двумя шагами одновременно. Кстати, мой, как правило, быстрее, и не нуждается в какой-либо упаковке. Пожалуйста, дайте мне знать, если у кого-то есть вопросы или комментарии. Спасибо.
05/09/2017 исправления:
Чтобы ответить на комментарий @Matthias Fripp, я добавил тестовые наборы по 10 и 100 тысяч элементов. Мой по-прежнему быстрее для 10k элементов, но не 100k элементов. Поэтому мой код не оптимален. Я думаю, что мой метод не является "правильным" ответом, как указывал @MSeifert, потому что в первоначальном вопросе спрашивалось о способах не искать все элементы.
import random # to generate data
# Set up data
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
x4 = tuple([random.choice(x3) for i in xrange(10000)])
x5 = tuple([random.choice(x3) for i in xrange(100000)])
# Set up functions
# My code
def findPairwise(x,target):
currentX = x
cumulatedIdx=0
while(1):
try:
idx = currentX.index(target[0])
try:
if currentX[idx+1] == target[1]:
return(idx+cumulatedIdx)
except:
pass
except:
break
currentX = currentX[idx+2:]
cumulatedIdx += idx+2
# MSeifert's method
from itertools import count
def find_ab(tup,target):
for idx in count(start=1, step=2):
try:
if tup[idx] == target[0]:
if tup[idx+1] == target[1]:
return idx
elif tup[idx] == target[1]:
if tup[idx-1] == target[0]:
return idx-1
except IndexError:
break
Результат
In [109]: %timeit findPairwise(x0,target)
The slowest run took 8.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [110]: %timeit find_ab(x0,target)
The slowest run took 5.49 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.04 µs per loop
In [111]: %timeit findPairwise(x1,target)
The slowest run took 4.75 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.46 µs per loop
In [112]: %timeit find_ab(x1,target)
The slowest run took 5.04 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.99 µs per loop
In [113]: %timeit findPairwise(x2,target)
The slowest run took 4.66 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.56 µs per loop
In [114]: %timeit find_ab(x2,target)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.25 µs per loop
In [115]: %timeit findPairwise(x3,target)
The slowest run took 8.59 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.28 µs per loop
In [116]: %timeit find_ab(x3,target)
The slowest run took 6.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.65 µs per loop
In [151]: %timeit findPairwise(x4,target)
The slowest run took 5.46 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop
In [152]: %timeit find_ab(x4,target)
The slowest run took 6.21 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 1.92 µs per loop
In [153]: %timeit findPairwise(x5,target)
1000 loops, best of 3: 325 µs per loop
In [154]: %timeit find_ab(x5,target)
The slowest run took 4.35 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 3.45 µs per loop
Ответ на этот вопрос заключается в том, что нет, нет никакого способа найти пары без зацикливания всех символов. Потому что, если вы не смотрите на персонажа, вы не представляете, соответствует ли он одному из вашей пары или нет.
Вы можете скрыть итерацию, сделав ее неявной в рутине языка или библиотеки, но она обязательно должна быть. Неявное использование может сделать код более эффективным (например, если вы переместите цикл из интерпретатора Python на предварительно скомпилированный язык, такой как C). Или, возможно, нет.
(Неэффективный, глупый!) Пример сокрытия может быть
def find_ba( x, target=('b','a'), separator = '|' ):
t = separator.join(target)
try:
return ( separator.join([ c for c in x]).index(t) ) / 2
except ValueError:
return None
(Код, предоставленный Министерству глупых прогулок по контракту № SW/ 110O/Il0O/01L11000/22 и размещенный в открытом доступе).
Используя itertools, вы можете сделать это ленивым, но все же нужно выполнить итерации:
import itertools
def check(x, target):
for t in itertools.izip(x, itertools.islice(x, 1, len(x))):
if t == target:
return True
return False
check(x0, ('b', 'a'))
True
РЕДАКТИРОВАТЬ: использовать zip в python3
Как указал nigel222, нет способа (в худшем случае) избежать итерации по всему списку, так как вы должны сделать исчерпывающее сравнение, чтобы убедиться, что нужный элемент не содержится в вашей итерации.
Однако если вы собираетесь выполнять множество таких запросов по различным возможным подпоследовательностям, возможно, стоит сжать их в набор, поскольку наборы имеют поиск O(1).
...
my_pairwise = set(pairwise(x))
found_subsequences = [subsequence
for subsequence in collection_of_subsequences
if subsequence in my_pairwise]
Таким образом, итерация O (n) через ваш x происходит только один раз, и каждый последующий поиск равен O(1).
Это не практично, но решает ваше дело
def look_up(needle, haystack):
i = ''.join(haystack).find(''.join(needle))
return i if i > -1 else None
Итак, предполагая, что у нас есть это:
x0 = ('b', 'a', 'z', 'z')
x1 = ('b', 'a', 'z', 'z')
x2 = ('z', 'z', 'a', 'a')
x3 = ('z', 'b', 'a', 'a')
ba = ('b', 'a')
мы получаем это:
print(look_up(ba, x0)) # Prints: 0
print(look_up(ba, x1)) # Prints: 0
print(look_up(ba, x2)) # Prints: None
print(look_up(ba, x3)) # Prints: 1
А вот для нескольких случаев:
def look_up_multiple(needle, haystack):
needle_str = ''.join(needle)
haystack_str = ''.join(haystack)
indexes = []
i = 0
while i < len(haystack_str):
i = haystack_str.find(needle_str, i)
if i > -1:
indexes.append(i)
i += 2
return indexes
И давайте запустим это:
x = ('b', 'a', 'z', 'z', 'b', 'a')
ba = ('b', 'a')
print(look_up_multiple(ba, x)) # Prints: [0, 4]