シリーズにデータポイントをグループ化

StackOverflow https://stackoverflow.com/questions/1549412

  •  20-09-2019
  •  | 
  •  

質問

Iのような形式のリスト中のデータ点（タプル）のシリーズを持っています 

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

各タプルの最初の項目は整数であり、それらはソートさが保証されています。各タプルの2番目の値は任意の文字列である。

私は彼らがシリーズで彼らの最初の値によってリストにグループ化する必要があります。

：SO 3の間隔を考えると、上記の項目に分割されます 
[['a', 'b', 'a', 'd'], ['c']]

私は小さなデータセットに正常に動作し、以下の機能を、書きました。しかし、それは大きな入力に対してinneficientされます。 /最適化/ mininizeを書き換える方法上の任意のヒントを、このように私は大規模なデータセットを処理することができますか？

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（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']]
それ（速度になした約束を）行うには、

片道ます：

二つのリストにタプルのリストをブレーク： [1,2,2,3,4]と['a','b','a','d','c']

最初のリストがソートされているので、あなたが範囲外の要素に到達するまで、反復処理を続けるだけのことができます。あなただけの二番目の配列のうち、文字列をスライスすることができますので、その後、あなたは、開始と終了の要素のインデックスを知っています。あなたはすべての間隔を持ってまで続けます。

私はそれが伝統のPythonのリストになりますどのように効率的にわからないんだけど、あなたのデータセットが十分に大きければ、あなたは本当にすぐにスライスしますnumpyの配列を、使用してみてください可能性があります。

あなたのコードから、私は私の前のコメントが正しいと仮定しています。ここでの問題は、パフォーマンスがO（N ^ 2）であることのように見える - 。あなたが（すべてのアイテムを反復処理）リスト内包複数回繰り返す。

私は、forループの簡単なを使用し、言います。現在のアイテムが前のものと同じグループに属している場合、既存の内部リストに追加[[ "A"]、[ "B"]] - > [[ "A"]、[ "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]]
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top