将数据点分组为序列

Question

我有一系列的数据点（元组），它们的格式像这样：

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

Answer 1

有一种方法可以做到这一点（速度方面不敢保证）：

把你的元组列表分成两个列表：[1,2,2,3,4] 和 ['a','b','a','d','c']

因为第一个列表是排好序的，你可以一直遍历这个列表，直到遇到一个超出范围的元素。这样，你就知道了开始和结束元素的索引，然后可以直接从第二个数组中切出对应的字符串。继续这个过程，直到你找出所有的区间。

我不太确定用传统的Python列表效率如何，但如果你的数据集足够大，可以试试使用NumPy数组，这样切片会快很多。

Answer 2

你的代码的复杂度是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']]

Answer 3

为了完整性，这里提供了一个使用 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)]