Поиск самого длинного пробега в списке

Учитывая список данных, я пытаюсь создать новый список, в котором значение в позиции i является длиной самого длинного запуска, начиная с позиции i в исходном списке. Например, данный

x_list = [1, 1, 2, 3, 3, 3]

Должен вернуться:

run_list = [2, 1, 1, 3, 2, 1]

Мое решение:

freq_list = []
current = x_list[0]
count = 0
for num in x_list:
    if num == current:
        count += 1
    else:
        freq_list.append((current,count))
        current = num
        count = 1
freq_list.append((current,count))

run_list = []
for i in freq_list:
    z = i[1]
    while z > 0:
        run_list.append(z)
        z -= 1

Во-первых, я создаю список freq_list кортежей, где каждый элемент первого кортежа является элементом из x_list, а второй - номером общего прогона.

В этом случае:

freq_list = [(1, 2), (2, 1), (3, 3)]

Имея это, я создаю новый список и добавляю соответствующие значения.

Однако мне было интересно, есть ли более короткий путь/другой способ сделать это?

Ответы

Ответ 1

Здесь простое решение, которое выполняет итерацию по списку назад и увеличивает счетчик каждый раз, когда число повторяется:

last_num = None
result = []
for num in reversed(x_list):
    if num != last_num:
        # if the number changed, reset the counter to 1
        counter = 1
        last_num = num
    else:
        # if the number is the same, increment the counter
        counter += 1

    result.append(counter)

# reverse the result
result = list(reversed(result))

Результат:

[2, 1, 1, 3, 2, 1]

Ответ 2

Это возможно с помощью itertools:

from itertools import groupby, chain

x_list = [1, 1, 2, 3, 3, 3]

gen = (range(len(list(j)), 0, -1) for _, j in groupby(x_list))
res = list(chain.from_iterable(gen))

Результат

[2, 1, 1, 3, 2, 1]

объяснение

  • Сначала используйте itertools.groupby для группировки одинаковых элементов в вашем списке.
  • Для каждого элемента в вашей groupby создайте объект range который отсчитывает назад от длины числа последовательных элементов до 1.
  • Превратите это все в генератор, чтобы избежать создания списка списков.
  • Используйте itertools.chain для цепи диапазонов от генератора.

Замечание по эффективности

Производительность будет уступать решению Aran-Fey. Хотя itertools.groupby - O (n), он сильно использует дорогие вызовы __next__. Они не масштабируются так же, как итерация в простых for петель. См. Документацию itertools для псевдокода groupby.

Если производительность является вашей главной задачей, придерживайтесь цикла for.

Ответ 3

Вы выполняете обратный кумулятивный счет для смежных групп. Мы можем создать функцию накопленного счета Numpy с помощью

import numpy as np

def cumcount(a):
    a = np.asarray(a)
    b = np.append(False, a[:-1] != a[1:])
    c = b.cumsum()
    r = np.arange(len(a))
    return r - np.append(0, np.flatnonzero(b))[c] + 1

а затем сгенерировать наш результат с помощью

a = np.array(x_list)

cumcount(a[::-1])[::-1]

array([2, 1, 1, 3, 2, 1])

Ответ 4

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

def gen(iterable):  # you have to think about a better name :-)
    iterable = iter(iterable)
    # Get the first element, in case that fails
    # we can stop right now.
    try:
        last_seen = next(iterable)
    except StopIteration:
        return
    count = 1

    # Go through the remaining items
    for item in iterable:
        if item == last_seen:
            count += 1
        else:
            # The consecutive run finished, return the
            # desired values for the run and then reset
            # counter and the new item for the next run.
            yield from range(count, 0, -1)
            count = 1
            last_seen = item
    # Return the result for the last run
    yield from range(count, 0, -1)

Это также будет работать, если вход не может быть reversed (некоторые генераторы/итераторы не могут быть отменены):

>>> x_list = (i for i in range(10))  # it a generator despite the variable name :-)
>>> ... arans solution ...
TypeError: 'generator' object is not reversible

>>> list(gen((i for i in range(10))))
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

И он работает для вашего ввода:

>>> x_list = [1, 1, 2, 3, 3, 3]
>>> list(gen(x_list))
[2, 1, 1, 3, 2, 1]

Это можно упростить, используя itertools.groupby:

import itertools

def gen(iterable):
    for _, group in itertools.groupby(iterable):
        length = sum(1 for _ in group)  # or len(list(group))
        yield from range(length, 0, -1)

>>> x_list = [1, 1, 2, 3, 3, 3]
>>> list(gen(x_list))
[2, 1, 1, 3, 2, 1]

Я также сделал некоторые тесты и, согласно этим решениям Aran-Feys, является самым быстрым, за исключением длинных списков, в которых выигрывает решение piRSquareds:

enter image description here

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

from itertools import groupby, chain
import numpy as np

def gen1(iterable):
    iterable = iter(iterable)
    try:
        last_seen = next(iterable)
    except StopIteration:
        return
    count = 1
    for item in iterable:
        if item == last_seen:
            count += 1
        else:
            yield from range(count, 0, -1)
            count = 1
            last_seen = item
    yield from range(count, 0, -1)

def gen2(iterable):
    for _, group in groupby(iterable):
        length = sum(1 for _ in group)
        yield from range(length, 0, -1)

def mseifert1(iterable):
    return list(gen1(iterable))

def mseifert2(iterable):
    return list(gen2(iterable))

def aran(x_list):
    last_num = None
    result = []
    for num in reversed(x_list):
        if num != last_num:
            counter = 1
            last_num = num
        else:
            counter += 1
        result.append(counter)
    return list(reversed(result))

def jpp(x_list):
    gen = (range(len(list(j)), 0, -1) for _, j in groupby(x_list))
    res = list(chain.from_iterable(gen))
    return res

def cumcount(a):
    a = np.asarray(a)
    b = np.append(False, a[:-1] != a[1:])
    c = b.cumsum()
    r = np.arange(len(a))
    return r - np.append(0, np.flatnonzero(b))[c] + 1

def pirsquared(x_list):
    a = np.array(x_list)
    return cumcount(a[::-1])[::-1]

from simple_benchmark import benchmark
import random

funcs = [mseifert1, mseifert2, aran, jpp, pirsquared]
args = {2**i: [random.randint(0, 5) for _ in range(2**i)] for i in range(1, 20)}

bench = benchmark(funcs, args, "list size")

%matplotlib notebook
bench.plot()

Python 3.6.5, NumPy 1.14

Ответ 5

Вот простой итеративный подход к его достижению с помощью collections.Counter:

from collections import Counter

x_list = [1, 1, 2, 3, 3, 3]
x_counter, run_list = Counter(x_list), []

for x in x_list:
    run_list.append(x_counter[x])
    x_counter[x] -= 1

который вернет вам run_list как:

[2, 1, 1, 3, 2, 1]

В качестве альтернативы, здесь один лайнер для достижения этой цели с использованием перечисления списков с enumerate но он неэффективен из-за итеративного использования list.index(..):

>>> [x_list[i:].count(x) for i, x in enumerate(x_list)]
[2, 1, 1, 3, 2, 1]

Ответ 6

Вы можете подсчитать последовательные равные элементы, а затем добавить обратный отсчет от count-of-items к 1 к результату:

def runs(p):
    old = p[0]
    n = 0
    q = []
    for x in p:
        if x == old:
            n += 1
        else:
            q.extend(range(n, 0, -1))
            n = 1
            old = x

    q.extend(range(n, 0, -1))

    return q

(Через пару минут) О, это то же самое, что и код MSeifert, но без итеративного аспекта. Эта версия кажется почти такой же быстрой, как метод Аран-Фей.