找到列表中最长的连续序列

Question

给定一个数据列表，我试图创建一个新的列表，在该列表中，位置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)]

有了这个，我创建一个新列表并附加适当的值。

但是，我想知道是否有更短的方法/其他方法可以做到这一点？

- meriam

---

提示：尝试从后往前遍历x_list。您注意到任何明显的模式了吗？ :) 建议翻译：“提示：尝试反向遍历 x_list。您是否注意到任何清晰的模式？ :)” - k_ssb

Answer 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]

- Aran-Fey

---

我喜欢这个答案，因为a）使用本地Python编写，b）具有O（n）运行时间，c）易于阅读/理解。 - Levi Muniz

Answer 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 循环。

- jpp

---

你能否评论一下这种方法的大O复杂度与@Aran-Fey答案相比？我的timeit测试表明，对于长度为5的列表，该解决方案需要5.93秒进行100万次评估，而@Aran-Fey的答案只需要2.998秒（3次中的最佳结果）。对于长度为10000的列表，你的答案需要约10.54秒，而另一个答案在1000次评估中只需要0.92秒。是groupby后跟随其结果迭代使得这种方法如此昂贵吗？ - Autonomous

Answer 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])

- piRSquared

Answer 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)

这也适用于无法反转输入的情况（某些生成器/迭代器无法反转）：

>>> x_list = (i for i in range(10))  # it's 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的解决方案是最快的，除了长列表，piRSquared的解决方案获胜:

如果您想确认结果，这是我的基准测试设置:

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

- MSeifert

Answer 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]

- Moinuddin Quadri

Answer 6

你可以计算连续相同的项，然后将从项目计数到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的代码相同，但没有可迭代的方面。 这个版本似乎几乎和Aran-Fey展示的方法一样快。

- Andrew Morton