0

ヘビーヒッター向けの次のアルゴリズムを知っています。

Algorithm findHeavyHitters(epsilon, inputStream)
    integer k = ceiling(1 / epsilon) - 1
    initialize hashmap H of size k

    while an item i from the input stream arrives:
        if H[i] exists
            increment the value associated with H[i]
        elsif number of items in H < k
            put H[i] into map with value of 1
        elseif there exists an entry j with a value of 0
            remove j and put H[i] into map with value of 1
        else
            decrement all values in H by 1
    endwhile

    return H

間違っている場合は訂正してください。ただし、このアルゴリズムは O(n) では実行されません。O(1/epsilon) のスペース使用を維持しながら、O(n) で実行されるようにこのアルゴリズムを変更することは可能ですか?

データ ストリームの場合、アルゴリズムのポイントは、上位の epsilon*t 項目を返すことです。イプシロンはパーセンテージで与えられます (例: 少なくとも 10% の確率で発生するデータの場合、0.1 を入力)。

4

1 に答える 1

1

このアルゴリズムは、ハッシュ ルックアップが平均 O(1) であることに基づいて、平均時間 O(n) で実行されます。

実装の詳細は 2 つあります。まず、H のすべての値に触れる最後のステップ:

  • H のすべての値を 1 減らす

この O(1) を作成するには、0 に初期化される という 1 つの保存場所を追加baseします。次に、アルゴリズムを次のように変更します。

while an item i from the input stream arrives:
    if H[i] exists
        increment the value associated with H[i]
    elsif number of items in H < k
        put H[i] into map with value of base + 1
    elseif there exists an entry j with a value of base 
        remove j and put H[i] into map with value of base + 1
    else
        increment base
endwhile

base2 番目の問題は、O(1) で値 (または 0) を持つエントリを見つけることです。これは、要素を「櫛」、つまり二重にリンクされたリストのリンクされたリストに保持することで実行できます。各内部リンク リストには、特定の数のエントリが含まれます。外側のリンクされたリストには、カウント順のカウント リストが含まれており、ヘッドはカウントが最小のリストを指しています。このデータ構造を描くと、くしのように見えます。

[  base    ] -> entry a -> entry b -> entry c
    |
[ base + i ] -> entry d
    |
[ base + j ] -> entry e -> entry f
    |
   etc.

ハッシュ テーブルは、エントリを含むのではなく、エントリを指すようになりました。単一のエントリのカウントを増やすには、そのエントリをリストから削除し (リストに複数の要素が含まれている場合)、次のリストに挿入するか、エントリがあったリストの後に挿入される 1 要素のリストに入れます。 、次のリストに関連付けられたカウントに応じて。この操作は O(1) です。

くしのデータ構造は依然として O(k) です。ここで、k はハッシュ内の要素の数です。

二重にリンクされたリストの代わりに、単純な配列と、各カウントの最初のエントリのインデックスのリストを使用できます。エントリを次のカウント バケットに移動するには、最初にそのカウントの最後のエントリと交換し、次のカウント リストのカウントが1 より大きい、または 1 より大きい。スワップを実行するには、ハッシュ内のスワップされた 2 つのエントリの場所を更新する必要がありますが、それでも O(1) です。

于 2016-06-16T06:57:31.660 に答える