Grouping data points into series

Asked
Viewd606

0

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[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
  • 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 и т. Д.?

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

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

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

    Corey Goldberg11 октября 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, поэтому я думаю, что поиск по словарю будет быстрее. (В случае сомнений, конечно, бенчмарк.)

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

    Corey Goldberg11 октября 2009, 00:36
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
 
  • also, this seems to be slightly faster than the defaultdict version

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

    Corey Goldberg13 октября 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.

    Ants Aasma13 октября 2009, 19:44
1

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

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

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

    Corey Goldberg11 октября 2009, 02:37
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']]
 
  • Linked list would make this O(log(n)) problem, but i have no idea how to implement this efficently in python.

    Luka Rahne11 октября 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

    Corey Goldberg11 октября 2009, 02:20
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]]
 
2

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

Разбейте список кортежей на два списка: [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.

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