#python #python-3.x
#python #python-3.x
Вопрос:
У меня есть большой список чисел в python, и я хочу написать функцию, которая находит разделы списка, где одно и то же число повторяется более n раз. Например, если n равно 3, то моя функция должна возвращать следующие результаты для следующих примеров:
При применении к example = [1,2,1,1,1,1,2,3] функция должна возвращать [(2,6)] , потому что example[2:6] — это последовательность, содержащая одно и то же значение.
При применении к example = [0,0,0,7,3,2,2,2,2,1] функция должна возвращать [(0,3), (5,9)], потому что оба примера [0:3] и пример [5:9] содержат повторяющиеся последовательности одного и того же значения.
При применении к example = [1,2,1,2,1,2,2,1,2,1,2] функция должна возвращать [], потому что нет последовательности из трех или более элементов с одинаковым числом.
Я знаю, что мог бы написать кучу циклов, чтобы получить то, что я хочу, но это кажется неэффективным, и мне было интересно, есть ли более простой вариант получить то, что я хотел.
Комментарии:
1. Пожалуйста, укажите код, с которым вы пробовали.
2. На самом деле вы хотите найти параметры среза , в которых повторяются разделы списка, а не индексы. Вы бы сбились на единицу.
3. Второй пример либо неверен, либо определение n неверно. В начале есть 3 нуля, поэтому ноль не повторяется более n раз .
Ответ №1:
Используйте itertools.groupby и enumerate :
>>> from itertools import groupby
>>> n = 3
>>> x = [1,2,1,1,1,1,2,3]
>>> grouped = (list(g) for _,g in groupby(enumerate(x), lambda t:t[1]))
>>> [(g[0][0], g[-1][0] 1) for g in grouped if len(g) >= n]
[(2, 6)]
>>> x = [0,0,0,7,3,2,2,2,2,1]
>>> grouped = (list(g) for _,g in groupby(enumerate(x), lambda t:t[1]))
>>> [(g[0][0], g[-1][0] 1) for g in grouped if len(g) >= n]
[(0, 3), (5, 9)]
Чтобы понять groupby: просто поймите, что каждая итерация возвращает значение ключа, который используется для группировки элементов итерации, вместе с новым lazy-iterable, который будет повторяться по группе.
>>> list(groupby(enumerate(x), lambda t:t[1]))
[(0, <itertools._grouper object at 0x7fc90a707bd0>), (7, <itertools._grouper object at 0x7fc90a707ad0>), (3, <itertools._grouper object at 0x7fc90a707950>), (2, <itertools._grouper object at 0x7fc90a707c10>), (1, <itertools._grouper object at 0x7fc90a707c50>)]
Комментарии:
1. Спасибо, это определенно намного эффективнее, чем то, что я делал. Я хотел бы понять, как именно это работает. Я понимаю, что делают enumerate(x) и ключевая функция, но что именно возвращает groupby? Почему нам нужна вторая половина, а не первая? После вызова этой функции я начинаю теряться.
2. Аккуратный. Вероятно, наиболее эффективно, если вам нужны все группы, но мне интересно, не будет ли это медленнее, если вам не нужны все подпоследовательности сразу и вы будете удовлетворены их генератором.
3. @FilipMalczak Если я вас правильно понял, то этого легко достичь, заменив понимание списка в конце еще одним выражением генератора.
4. Да, в принципе, но вся groupby(…) выполняется до понимания. Я думаю, вы могли бы обернуть его в другой генератор, используемый в понимании, или даже встроить его. Мне просто интересно, не будет ли какое-то решение, которое даст каждую подпоследовательность, как только она будет найдена, немного быстрее.
5. @FilipMalczak Да, это должно быть выполнение двух проходов по списку, но если вы обернете его в генератор, вы можете выжать из него последний бит эффективности.
Ответ №2:
Вы можете сделать это за один цикл, следуя текущему алгоритму:
def find_pairs (array, n):
result_pairs = []
prev = idx = 0
count = 1
for i in range (0, len(array)):
if(i > 0):
if(array[i] == prev):
count = 1
else:
if(count >= n):
result_pairs.append((idx, i))
else:
prev = array[i]
idx = i
count = 1
else:
prev = array[i]
idx = i
return result_pairs
И вы вызываете функцию следующим образом: find_pairs(list, n) . Это наиболее эффективный способ выполнить эту задачу, поскольку она имеет сложность O (len (array)). Я думаю, это довольно просто понять, но если у вас есть какие-либо сомнения, просто спросите.
Комментарии:
1. Это хороший ответ, в котором представлены «классические» методы императивного программирования. При этом вы должны исправить свой отступ.
2. Этот ответ не будет работать, если последовательность заканчивается в конце массива. Алгоритм в его нынешнем виде не обнаружит разницы с предыдущим элементом и не перейдет в блок else. Он также будет считаться неправильно, если есть две монотонные подпоследовательности подряд. В этом случае он начнет считать один индекс слишком поздно в последней подпоследовательности.
Ответ №3:
Вы могли бы использовать это. Обратите внимание, что ваш вопрос неоднозначен относительно роли n . Я предполагаю, что здесь должна быть сопоставлена серия из n равных значений. Если он должен иметь не менее n 1 значений, то замените >= на > :
def monotoneRanges(a, n):
idx = [i for i, v in enumerate(a) if not i or a[i-1] != v] [len(a)]
return [r for r in zip(idx, idx[1:]) if r[1] >= r[0] n]
# example call
res = monotoneRanges([0,0,0,7,3,2,2,2,2,1], 3)
print(res)
Выводит:
[(0, 3), (5, 9)]
Комментарии:
1. Хорошо, но вам нужно иметь дело с крайним случаем:
monotoneRanges([0,0,0,7,3,2,2,2,2,1,0], 3)2. @juanpa.arrivillaga, спасибо, что заметили это. Я думаю, что я исправил это с добавленным
not iусловием.