代码之家 › 专栏 › 技术社区 › Corey Goldberg

将数据点分组为序列

series algorithm python

Corey Goldberg · 技术社区 · 17 年前

我在列表中有一系列数据点(元组),格式如下:

points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')]

每个元组中的第一个项是一个整数,可以确保对它们进行排序。每个元组中的第二个值是一个任意字符串。

我需要按序列中的第一个值将它们分组到列表中。因此,如果间隔为3,上述列表将分为:

[['a', 'b', 'a', 'd'], ['c']]

我编写了以下函数,它在小数据集上工作得很好。但是,它对大输入是有意义的。有什么关于如何重写/优化/缩小这一点的提示,以便我可以处理大型数据集吗?

def split_series(points, interval):
    series = []

    start = points[0][0]
    finish = points[-1][0]

    marker = start
    next = start + interval
    while marker <= finish:
        series.append([point[1] for point in points if marker <= point[0] < next])
        marker = next
        next += interval

    return series

7 回复 | 直到 17 年前

Nicholas Riley 17 年前

为了完整性,这里有一个解决方案 itertools.groupby 但字典解决方案可能更快(更不用说更容易阅读)。

import itertools
import operator

def split_series(points, interval):
    start = points[0][0]

    return [[v for k, v in grouper] for group, grouper in
            itertools.groupby((((n - start) // interval, val)
                               for n, val in points), operator.itemgetter(0))]

请注意,上面假设每个组中至少有一个项目,否则它将给出来自脚本的不同结果,即:

>>> split_series([(1, 'a'), (2, 'b'), (6, 'a'), (6, 'd'), (11, 'c')], 3)
[['a', 'b'], ['a', 'd'], ['c']]

而不是

[['a', 'b'], ['a', 'd'], [], ['c']]

这是一个固定的字典解决方案。在某种程度上,字典查找时间将开始占主导地位,但也许它足够快,您喜欢这样。

from collections import defaultdict

def split_series(points, interval):
    offset = points[0][0]
    maxval = (points[-1][0] - offset) // interval
    vals = defaultdict(list)
    for key, value in points:
        vals[(key - offset) // interval].append(value)
    return [vals[i] for i in xrange(maxval + 1)]

RichieHindle 17 年前

你的代码是O(N ^二 )这里有一个O(N)解决方案:

def split_series(points, interval):
    series = []
    current_group = []
    marker = points[0][0]
    for value, data in points:
        if value >= marker + interval:
            series.append(current_group)
            current_group = []
            marker += interval
        current_group.append(data)

    if current_group:
        series.append(current_group)

    return series

points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')]
print split_series(points, 3)  # Prints [['a', 'b', 'a', 'd'], ['c']]

perimosocordiae 17 年前

一种方法(不承诺速度):

将元组列表分为两个列表: [1,2,2,3,4] 和 ['a','b','a','d','c']

由于第一个列表是经过排序的,所以您可以一直对它进行迭代,直到到达超出范围的元素为止。然后,您知道开始和结束元素的索引,这样您就可以从第二个数组中分割出字符串。继续,直到你有了所有的时间间隔。

我不确定传统的python列表有多高效,但是如果您的数据集足够大,您可以尝试使用一个numpy数组,它将很快切片。

Steve314 17 年前

根据你的代码,我假设我之前的评论是正确的。这里的问题似乎是性能是O(n^2)-您重复列表理解(它迭代所有项)多次。

我说,使用一个简单的for循环。如果当前项目与上一个项目属于同一组,请将其添加到现有内部列表[[“A”]、[“B”]->[“A”]、[“B”、“C”]。如果没有,请将其添加到新的内部列表中,或者首先添加空的填充列表。

ABentSpoon Ungue 17 年前

展开AM的答案,使用默认的dict,floor将键按间隔进行划分,以正确地将它们分开。

from collections import defaultdict
def split_series(points, interval):
    vals = defaultdict(list)
    for key, value in points:
        vals[(key-1)//interval].append(value)
    return vals.values()

Ants Aasma 17 年前

下面是一个使用xrange的步骤行为的懒惰方法:

def split_series(points, interval):
    end_of_chunk = interval
    chunk = []
    for marker, item in points:
        if marker > end_of_chunk:
            for end_of_chunk in xrange(end_of_chunk, marker, interval):
                yield chunk
                chunk = []
            end_of_chunk += interval
        chunk.append(item)
    yield chunk

user3850 17 年前

使用迭代器进行延迟计算怎么样?

这应等同于您的初始解决方案:

from itertools import groupby

def split_series(points, interval):
    """
    >>> points = [(1, 'a'), (2, 'b'), (2, 'a'), (3, 'd'), (4, 'c')]
    >>> print list(split_series(points, 3))
    [['a', 'b', 'a', 'd'], ['c']]
    """

    def interval_key(t):
        return (t[0] - points[0][0]) // interval

    groups = groupby(points, interval_key)

    for group in groups:
        yield [v for _, v in group[1]]