Группировка точек данных в серии

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

Для полноты, вот решение с 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)]

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

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

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

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

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

Answer 4

Вот ленивый подход, который использует пошаговое поведение 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

Answer 5

Расширяя ответ 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()

Answer 6

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

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

Answer 7

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

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

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]]