最も頻繁な要素をキャッシュするデータ構造

Question

整数のストリームを読み込んだとします。同じ整数がストリームに複数回現れることがあります。今では、最も頻繁に出現するN個の整数のキャッシュを保持したいと考えています。キャッシュは、ストリーム要素の頻度によってソートされます。

どのようにJavaで実装しますか？

Answer 1

はGuava Multisetとsort it by frequency

Answer 2

int、insideのオブジェクトモデルを作成してCountプロパティを作成します。 Vectorコレクションを拡張するSortedVectorコレクションを作成します。整数が現れるたびに、ベクトルが存在しない場合はベクトルに追加します。それ以外の場合は、countプロパティ+ = 1を更新して、Vector内のCollections.sort（this）を呼び出します。

Answer 3

あなたは番号の範囲を知っています使用しますか？もしそうなら、配列を使うのが理にかなっています。たとえば、数値の範囲が0から10の間であることがわかっていたら、サイズ10の配列を作成します。この配列の各要素は、指定した数を見た回数を数えます。次に、最も頻繁に見られる番号を覚えておくだけです。

array[10]; 
freq_index = -1; 
freq_count = -1; 

readVal(int n){ 
    array[n]+=1; 
    if array[n] > freq_count 
    freq_index = n; 
    freq_count = array[n]; 
} 

数字の分布がまばらな場合はもちろん、このアプローチは悪いです。

私は優先キューを試してみました。

Answer 4

あなたがバイナリインデックス付きの木を使用したい、リンク内のコードは（コードAFAICT同じになる）C++のためのものであり、Javaのに変換することはかなり簡単です：

Paper Peter Fenwick

Implementation in C++

Answer 5

public class MyData implements Comparable<MyData>{ 
    public int frequency = 0; 
    public Integer data; 
    @Override 
    public int compareTo(MyData that) { 
    return this.frequency - that.frequency; 
    } 

} 

それはこれに興味深い部分は、それらの数を処理する方法であるPriorityQueue