0

次のような形式の一連のデータポイント（タプル）がリストにあります。

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

各タプルの最初の項目は整数であり、確実にソートされます。各タプルの2番目の値は、任意の文字列です。

シリーズの最初の値でリストにグループ化する必要があります。したがって、間隔が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
4

7 に答える 7

2

それを行う1つの方法（速度についての約束はありません）：

タプルのリストを2つのリストに分割します [1,2,2,3,4]。['a','b','a','d','c']

最初のリストは並べ替えられているので、範囲外の要素に到達するまで、リストを繰り返し処理し続けることができます。次に、開始要素と終了要素のインデックスがわかっているので、2番目の配列から文字列をスライスするだけです。すべての間隔が得られるまで続けます。

従来のPythonリストでどれほど効率的かはわかりませんが、データセットが十分に大きい場合は、NumPy配列を使用してみてください。これにより、非常に高速にスライスされます。

于 2009-10-11T00:02:23.157 に答える
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']]
于 2009-10-11T00:06:01.097 に答える
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))]

上記は、各グループに少なくとも1つのアイテムがあることを前提としていることに注意してください。そうでない場合、スクリプトから異なる結果が得られます。

>>> 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)]
于 2009-10-11T00:23:40.173 に答える
1

あなたのコードから、私は私の前のコメントが正しいと仮定しています。ここでの問題は、パフォーマンスがO（n ^ 2）であるということのようです。リスト内包（すべての項目を繰り返す）を複数回繰り返します。

つまり、単純なforループを使用します。現在のアイテムが前のアイテムと同じグループに属している場合は、既存の内部リストに追加します[["a"]、["b"]]-> [["a"]、["b"、 "c "]]。そうでない場合は、それを新しい内部リストに追加します。おそらく最初に空のパディングリストを追加します。

于 2009-10-11T00:11:51.927 に答える
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()
于 2009-10-11T00:16:34.693 に答える
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
于 2009-10-13T16:57:37.303 に答える
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]]
于 2009-10-11T00:25:13.463 に答える