ユーザーイベントストリームでユーザーのp％を無作為にサンプリングする方法

Question

の無制限のユーザーからp％のユーザーを公平にサンプリングするアルゴリズムを探しています。

素朴なアルゴリズムは次のようになります。

//This is naive.. what is a better way?? 
def userIdToRandomNumber(userId: Int): Float = userId.toString.hashCode % 1000)/1000.0 

//An event listener will call this every time a new event is received 
def sampleEventByUserId(event: Event) = { 
    //Process all events for 3% percent of users 
    if (userIdToRandomNumber(event.user.userId) <= 0.03) { 
     processEvent(event) 
    } 
} 

は、（モジュロ演算等、そのない正確のpので、値を離散化され、ハッシュコードは短い文字列を好む場合があります）しかし、このコードに問題があります。

上記の関数userIdToRandomNumberの乱数に対するuserIdの確定的なマッピングを見つける "より正確な"方法はありましたか？ここで

Answer 1

hashCodeの代わりに下記の方法をお試しください。でも、短い文字列のために、整数として文字の値は、合計が分裂を避けるため、また100上に行くことを確認してください、あなたは、私は決定論的解決策が出ている

def inScope(s: String, p: Double) = modN(s, 100) < p * 100 

    def modN(s: String, n: Int): Int = { 
    var sum = 0 
    for (c <- s) { sum += c } 
    sum % n 
    } 

Answer 2

は、データセットが十分に大きいと仮定すると、非常に単純なマッピングです：

• すべてのユーザーのために、generate a random numbe R xを、[0, 1]に言います。
• x <= p場合は、そのユーザ

これを選んで、大規模なデータセット上の実際に使用する方法であり、あなたに完全にランダムな結果が得られます！

私はあなたがScalaでこれを簡単にコーディングできることを望んでいます。

---

EDIT：コメントの中で、あなたが決定論に言及。私はそれを解釈して、もしあなたが再びサンプリングすれば、同じ結果が得られます。そのためには、ユーザーごとにxを保存するだけです。

また、これは任意の数のユーザー（無限でも可能です）でも機能します。ユーザーごとにxを生成するだけで済みます。マッピングは単にuserId -> xです。

EDIT2：あなたの質問のアルゴリズムは偏っています。 p = 10%とし、1100ユーザー（userIds 1-1100）があるとします。最初の1000ユーザーIDは10%、次は100、チャンスは100%です。また、ハッシュはユーザIDを新しい値にマッピングしますが、モジュロ1000があなたに一様なサンプルを与えるという保証はありません！

Answer 3

丸め誤差を避けるため、ランダムにサンプルユーザーへ（ランダム番号ジェネレータが完全にランダムであると仮定して）完全にランダムなストリームから：