0

我在列表中有一系列数据点（元组），格式如下：

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
4

7 回答 7

2

为了完整起见，这里有一个解决方案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)]
于 2009-10-11T00:23:40.173 回答
2

一种方法（没有速度承诺）：

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

由于第一个列表已排序，因此您可以继续迭代它，直到找到超出范围的元素。然后，您知道开始和结束元素的索引，因此您可以从第二个数组中切出字符串。继续，直到你得到所有的间隔。

我不确定传统 Python 列表的效率如何，但如果您的数据集足够大，您可以尝试使用 NumPy 数组，它会非常快速地切片。

于 2009-10-11T00:02:23.157 回答
2

您的代码是 O(n 2 )。这是一个 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']]
于 2009-10-11T00:06:01.097 回答
1

扩展 Am 的答案，使用 defaultdict，然后将键除以间隔以正确分解它们。

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()
于 2009-10-11T00:16:34.693 回答
1

这是一种使用 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
于 2009-10-13T16:57:37.303 回答
1

从您的代码中，我假设我之前的评论是正确的。这里的问题似乎是性能为 O(n^2) - 您多次重复列表理解（迭代所有项目）。

我说，使用一个简单的 for 循环。如果当前项与前一项属于同一组，则将其添加到现有内部列表 [["a"], ["b"]] -> [["a"], ["b", "c "]]。如果没有，请将其添加到一个新的内部列表中，也许首先添加空的填充列表。

于 2009-10-11T00:11:51.927 回答
0

使用迭代器进行惰性评估怎么样？

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

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]]
于 2009-10-11T00:25:13.463 回答