11

入力データがあり、そのデータの平均、95 パーセンタイル、および 99 パーセンタイルを計算したい - 最後の 1000 の値に最も関心があります。いつでも、このオブジェクトにクエリを実行して、3 つの値のいずれかを取得したいと考えています (これは、mod 1000 で見られる数値が 0 である場合だけでなく、いつでも発生する可能性があります)。最後の 1000 サンプルを保持せずにこれら 3 つの値を取得する方法はありますか?

これは完璧である必要はないので、いくつかのトリックを使用して適切な見積もりを得ることができます。また、速度も別の懸念事項です。ありがとう

(私はこれを C++ で行いますが、それほど重要ではないと思います)

4

2 に答える 2

7

少なくとも、最新の 1000 個の要素のキューを維持する必要があります。

移動平均を維持するには、最新の 1000 要素の移動合計を維持します。新しい要素をキューに追加すると、その値が合計に追加され、キューから削除したばかりの最も古い要素の値も減算されます。合計を 1000 で割った値を返します。

実行中の N パーセンタイルを維持するには、2 つのヒープを維持し、ヒープ内の要素の数を維持します。「下位」ヒープには値の下位 N% があり、「上位」ヒープには上位 (1-N)% があります (たとえば、下位 95 パーセンタイル ヒープには 950 要素があり、上位 5 パーセンタイル ヒープには50 の要素があります)。いつでも、上位ヒープから最下位の要素を返すことができます。これがパーセンタイルです。最近の値のキューから要素を削除すると、ヒープからも値が削除されます。これによりヒープのバランスが取れていない場合 (たとえば、下のヒープに 951 個の要素があり、上のヒープに 49 個の要素がある)、要素をシフトしてバランスをとります (たとえば、下のヒープから一番上の要素を削除し、上のヒープに追加します)。

2 つのパーセンタイルが必要なため、3 つのヒープを使用します。下のヒープには下の 950 要素があり、中央には次の 40 の要素があり、上のヒープには最高の 10 があります。 99 パーセンタイルの上位ヒープの要素。

ヒープ要素の追加と削除は O(lg(n)) であるため、キューと 3 つのヒープに新しい要素を追加するコストです。ヒープから最も古いキュー要素を削除し (O(lg(n)))、新しいキュー要素を適切なヒープ (O(lg(n))) に追加し、必要に応じてヒープのバランスを調整します (再び、O(lg(n)))。新しい要素を、最上位の要素がヒープより大きい最下位のヒープに追加します。要素、すなわち

if (newElement < lowestHeap.maxElement) {
    lowestHeap.add(newElement)
} else if (newElement < middleHeap.maxElement) {
    middleHeap.add(newElement)
} else { 
    highestHeap.add(newElement)
}

ヒープで要素の重複が許可されていることを確認してください

于 2013-05-08T23:19:37.853 に答える