题
我的列表中有一系列数据点(元组),格式如下:
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
解决方案
有关完整,这里与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)]
其他提示
你的代码是 O(n2)。这是一个 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']]
的一种方式做到这一点(在速度没有承诺):
将您的元组的列表分为两个列表:
[1,2,2,3,4]
和['a','b','a','d','c']
由于第一列表进行排序,你可以只保留迭代,直到你得到一个元素超出了范围。然后,你知道的开始和结束元素的索引,所以你可以只切串了第二阵。继续,直到你已经得到了所有的时间间隔。
我不知道如何高效那将是与传统的Python列表,但如果你的数据集够大,你可以尝试使用NumPy的阵列,这将切片真的很快。
这是你的代码,我假设我之前的评论是正确的。这里的问题似乎是性能是O(n ^ 2) - 你重复的列表理解(它迭代所有项目)多次
我说,用一个简单的for循环。如果当前项在同一个组与前一个属于,将其添加到现有的内部列表[[“一”],[“b”的〕〕 - > [[“一”],[“B”,“C “]]。如果没有,将其添加到新的内部列表,也许第一加法空填充列表。
扩展在上午的回答,请使用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()
下面是一个使用的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
如何使用迭代器惰性求?
这应该是你的初始溶液的当量:
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]]