 # Grouping data points into series

Viewd606

I have a series of data points (tuples) in a list with a format like:

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

The first item in each tuple is an integer and they are assured to be sorted. The second value in each tuple is an arbitrary string.

I need them grouped in lists by their first value in a series. So given an interval of 3, the above list would be broken into:

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

I wrote the following function, which works fine on small data sets. However, it is inneficient for large inputs. Any tips on how to rewrite/optimize/mininize this so I can process large data sets?

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

start = points
finish = points[-1]

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

return series
``````
• would lazy evaluation solve your performance problem? itertools.groupby should almost do what you want

11 октября 2009, 00:06
• Я не совсем понимаю вашу группу. Вы хотите сказать, что с интервалом 3 группы будут включать диапазоны ключей 1–3, 4–6, 7–9 и т. Д.?

11 октября 2009, 00:04
• still not clear: if points where 5, would the key ranges be 5..7, 8..10, etc?

11 октября 2009, 00:22

## 7 ответов

Для полноты, вот решение с `itertools.groupby`, но словарное решение, вероятно, будет быстрее (не говоря уже о том, что его будет легче читать).

``` ```import itertools
import operator

def split_series(points, interval):
start = points

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
maxval = (points[-1] - 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)]
``` ```
• ваша версия dict - единственная, которая правильно печатала пустые группы. это также очень быстро. принимая этот ответ

11 октября 2009, 02:40
• if you factor out the key function, it actually becomes quite readable, i think

11 октября 2009, 00:26
• Хорошо, попробуй вот это. Поскольку itertools.groupby реализован на C (по крайней мере, в 2.6), будет сложно превзойти производительность, реализовав его на Python, поэтому я думаю, что поиск по словарю будет быстрее. (В случае сомнений, конечно, бенчмарк.)

11 октября 2009, 00:52
• i actually need to know when a group is empty, so can’t make that assupmtion.

11 октября 2009, 00:36

Вот ленивый подход, использующий пошаговое поведение 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
``` ```
• also, this seems to be slightly faster than the defaultdict version

13 октября 2009, 21:05
• ой .. у меня плохо. он дает правильный результат. Я стираю свой предыдущий комментарий и поддерживаю это решение.

13 октября 2009, 20:55
• Other than that it’s returning a generator instead of a list by design (the generator can then be materialized as a list as needed using `list()`), where does the output differ? Or is the problem the assumption that the chunks always start at 1? In that case it’s easy to modify to peel of the first marker-item pair from points, calculate the first end_of_chunk off of that and stick the item in the first chunk.

13 октября 2009, 19:44

Исходя из вашего кода, я предполагаю, что мой предыдущий комментарий верен. Проблема здесь, по-видимому, в том, что производительность равна O (n ^ 2) - вы повторяете понимание списка (которое повторяет все элементы) несколько раз.

Я советую использовать простой цикл for. Если текущий элемент принадлежит к той же группе, что и предыдущий, добавьте его в существующий внутренний список [["a"], ["b"]] -> [["a"], ["b", "c" "]]. Если это не так, добавьте его в новый внутренний список, возможно, сначала добавив пустые списки заполнения.

Расширяя ответ 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()
``` ```
• эта версия работает быстро, но в ней не хранятся пустые группы для пустых интервалов. см. ответ и комментарии Николаса Райли

11 октября 2009, 02:37

Ваш код - O (n 2 ). Вот решение O (n):

``` ```def split_series(points, interval):
series = []
current_group = []
marker = points
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']]
``` ```
• Linked list would make this O(log(n)) problem, but i have no idea how to implement this efficently in python.

11 октября 2009, 01:09
• this version is much faster and is very readable. but it doesn’t store empty groups for empty intervals. see Nicholas Riley’s answer and comments

11 октября 2009, 02:20

Как насчет использования итераторов для отложенного вычисления?

Это должно быть эквивалентом вашего исходного решения:

``` ```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 - points) // interval

groups = groupby(points, interval_key)

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

Один из способов сделать это (никаких обещаний по скорости):

Разбейте список кортежей на два списка: `[1,2,2,3,4]` и `['a','b','a','d','c']`

Поскольку первый список отсортирован, вы можете просто повторять его, пока не дойдете до элемента за пределами диапазона. Затем вы знаете индексы начального и конечного элементов, поэтому вы можете просто вырезать строки из второго массива. Продолжайте, пока не получите все интервалы.

Я не уверен, насколько эффективно это будет с традиционными списками Python, но если ваш набор данных достаточно велик, вы можете попробовать использовать массив NumPy, который будет очень быстро нарезать.

• A traditional Python list is an array, so the subscripting and slicing should be pretty efficient. IMO good answer.

11 октября 2009, 00:13