1

ビルドオフと以前の質問:シングルパスでのジェネレーターの統計の計算。パイソン

前に述べたように、単一パスでジェネレーターから統計を計算することは非常に高速で、メモリ効率が高くなります。90 パーセンタイルや n 番目に小さいものなどの複雑な統計とランク属性は、多くの場合、標準偏差と平均 (上記で解決) よりも複雑な作業を必要とします。これらのアプローチは、map/reduce ジョブや、データをリストに入れたり、複数のパスを計算したりするのが非常に遅くなる大規模なデータセットを操作する場合に非常に重要になります。

以下は、ランク順に基づいてデータを検索するための O(n) クイックソート スタイルのアルゴリズムです。中央値、パーセンタイル、四分位数、十分位数を見つけるのに役立ちます。データが既にソートされている場合は、data[n] と同等です。ただし、分割/ピボットできるリスト内のすべてのデータが必要です。

単一パスでジェネレーターを使用して、中央値、パーセンタイル、四分位数、および十分位数を計算するにはどうすればよいですか?

完全なリストを必要とするクイックソート スタイルのアルゴリズム

import random

def select(data, n):
    "Find the nth rank ordered element (the least value has rank 0)."
    data = list(data)
    if not 0 <= n < len(data):
        raise ValueError('not enough elements for the given rank')
    while True:
        pivot = random.choice(data)
        pcount = 0
        under, over = [], []
        uappend, oappend = under.append, over.append
        for elem in data:
            if elem < pivot:
                uappend(elem)
            elif elem > pivot:
                oappend(elem)
            else:
                pcount += 1
        if n < len(under):
            data = under
        elif n < len(under) + pcount:
            return pivot
        else:
            data = over
            n -= len(under) + pcount
4

1 に答える 1

4

データの大部分を保存する必要があります。それを完全に保存するだけで報われるかもしれないところまで。近似アルゴリズムを受け入れる意思がない限り (データが独立していることがわかっている場合、これは非常に合理的な場合があります)。

次のデータセットの中央値を見つける必要があるとします。

0  1  2  3  4  5  6  7  8  9 -1 -2 -3 -4 -5 -6 -7 -8 -9

中央値は明らかに0です。ただし、最初の 10 個の要素しか見ていない場合は、その時点での最悪の推測です。したがって、n 要素ストリームの中央値を見つけるには、少なくともn/2候補要素をメモリに保持する必要があります。合計サイズがわからない場合は、nすべて保持する必要があります。

奇数サイズの状況ごとの中央値は次のとおりです。

0  _  1  _  2  _  3  _  4  _  4  _  3  _  2  _  1  _  0

それらは決して候補ではありませんでしたが、要素 5 ～ 9 も覚えておく必要があります。

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18

中央値が得られます9。サイズ n の一連の要素ごとに、この要素を中央値とするサイズ O(2*n) の連続した一連の要素を見つけることができます。しかし明らかに、これらのシリーズはランダム/独立ではありません。

統計的中央値、最頻値、歪度、尖度を推定するための「オンライン」(反復子) アルゴリズムを参照してください。関連するメソッドの概要については。

于 2012-07-04T16:22:16.993 に答える