0

重み付きの要素のリストがあります。

{ id1, weight1 },
{ id2, weight2 },
...
{ idN, weightN }

重みは小さな整数です（たとえば、1000未満、多くの場合50未満）。リスト内のIDの総数も1000未満です。（それぞれidが1回だけリストされます。）

クエリごとに、リストから「十分にランダムな」要素を返す必要があります。Eすべての重みの合計に比例するクエリを実行する場合E、各要素要素が同じ回数、 その値に正確に比例する必要があります。weightこれは、の値が小さい場合E（たとえば、最大50 *重みの合計）で機能することに注意してください。質問の最後にある注記も参照してください。

これまでのところ、要素IDを循環リストに入れ、重みを掛けて複製し、リストをシャッフルすることで、このタスクを解決します。各クエリはリストの先頭を返し、先頭の位置をインクリメントします。

しかし、この場合、もう1つの条件があります。

クエリに追加のパラメータがあります：フィルタ。フィルタはのマップですid => is_enabled。特定のに対してis_enabledfalseの場合、結果から除外する必要があります。上記の制限の値は、有効な要素に対してのみ計算されます。つまり、無効にされた要素の重みはクエリから除外されます。ididE

フィルタはクエリごとに「一意」でありid、リストにそれぞれのエントリが含まれます。（これは、2 ^ 1000の潜在的なフィルター値を意味することに注意してください。）

これを効率的に解決する方法はありますか？マルチサーバークラスターで効率的なアルゴリズムが必要です。

注1：私が信じているように、状態を保存せずに要素を完全にランダムに選択すると（回答の1つで示唆されているように）、機能しないことを強調したいと思います。無限の数のクエリに対してのみ、正確に比例した数の要素を提供します。乱数ジェネレーターには、長期間にわたって不公平な値を返す完全な権利があります。

注2：このタスクは、ランダム性の品質に制限を課しません。考えてみると、上記の単純なケースのソリューションでリストをシャッフルする必要はありません。良いランダム性の方が優れていますが、まったく必要ありません。

注3： 2 ^ 1000の潜在的なフィルター値は、フィルター値に関連付けられたものを保存できないことを意味することに注意してください。メモリが多すぎることになります。最新の（または頻繁に使用される）フィルター用に何かを保存することはできますが、そのデータを失うわけにはいかないため、アイテムリストのオフセットなどを保存することはできません。

注4：クエリでメタ情報を返したり、クライアントに状態を保存させたりすることはできません（とにかく、Diacleticusに感謝します）。2つのクライアントが誤って同じフィルターを使用する可能性があるため、使用できません（一部のフィルターは他のフィルターよりも人気があります）。この場合、両方のクエリに同じ状態を使用する必要があります。実際、クライアントが複数のクエリを実行することは、比較的まれなイベントです。

4

3 に答える 3

0

私があなたの質問を理解したかどうか見てみましょう。

Mathematicaでコードを段階的に投稿し、コメント付きの出力で簡単にフォローできるようにします。

この回答は、決定論的で順序付けられた出力（つまり、非シャッフル）を提供します。本当にランダム置換が必要な場合は、この同じアルゴリズムを使用して事前に完全にフィルター処理されたシーケンスを生成し、それをシャッフルして、値を1つずつ消費します。

プログラム

まず、2つの定数を定義します。

n = 10; (* nbr of ids *)
m = 3;  (* max weight - 1 *)

出力を段階的に確認できるように、数値は小さくしています。

次に、使用するランダムな{id、weight}テーブルを定義します。IDとして素数を使用します。 

weights = Table[{Prime@k, RandomInteger[m] + 1}, {k, n}]

出力：

{{2, 3}, {3, 2}, {5, 3}, {7, 1}, {11, 1}, 
{13, 3}, {17, 1}, {19,4}, {23, 1}, {29, 2}}

次に、重み値を累積します

accumulator = Accumulate[Table[k[[2]], {k, weights}]]

出力：

{3, 5, 8, 9, 10, 13, 14, 18, 19, 21}

そして、両方のテーブルをマージして、アキュムレータをidテーブルに入れます。

weightsAcc = MapThread[Append, {weights, accumulator}]

出力：

{{2, 3, 3}, {3, 2, 5}, {5, 3, 8}, {7, 1, 9}, {11, 1, 10}, 
 {13, 3, 13}, {17, 1, 14}, {19, 4, 18}, {23, 1, 19}, {29, 2, 21}}

次に、デフォルト値（trueまたはfalse）を使用してフィルターを初期化します。Trueを使用しました： 

filter = Table[{k[[1]], True}, {k, weights}]

出力：

{{2, True}, {3, True}, {5, True}, {7, True}, {11, True}, {13, True}, 
 {17, True}, {19, True}, {23, True}, {29, True}}

秘訣は、フィルターをidsベクトルと同期させ続けることです。そのため、次のようにフィルターを更新する関数を定義します。 

updateFilter[filter_, newValuePair_] :=Return@
         ReplaceAll[filter, {newValuePair[[1]], x_} -> newValuePair];

そして、それを使用して2つの値を変更します。 

filter = updateFilter[filter, {2, False}];
filter = updateFilter[filter, {5, False}];
Print@filter

出力：

{{2,False},{3,True},{5,False},{7,True},{11,True},{13,True},
 {17,True},{19,True},{23,True},{29,True}}

次に、クエリを定義します。2つのグローバル変数（agrhhhh！）と2つの関数を使用して、同期を取ります。

i = 1; j = 0; (* GLOBAL state variables *)

Adjustij[w_] := (                      (* parm w is weightsAcc *)
   j++;                                (* increment accumulator comparator*)
   If[j == w[[i, 3]], i++];            (* if current id exhausted, get next*)
   If[i == Length@w, i = 1; j = 0];    (* wraparound table when exhausted*)
);   

query[w_, filter_] :=                  (* parm w is weightsAcc *)
 (
  Adjustij[w];
  While[Not@filter[[i, 2]], Adjustij[w]];       (* get non filtered ids only *)
  Return[w[[i, 1]]];
  )

もちろん、whileループは、フィルターFalseを使用してIDをスキップするだけで高速化できますが、この方法の方が意図が明確だと思います。

ここで、クエリを30回実行します。 

 Table[query[weightsAcc, filter], {30}]

そして取得： 

{3, 3, 7, 11, 13, 13, 13, 17, 19, 19, 19, 19, 23, 3, 3, 7, 11, 13, \
 13, 13, 17, 19, 19, 19, 19, 23, 3, 3, 7, 11}

これは、適切な重みを持つ（周期的に）リストです。ただし、フィルターがFALSEの値は除きます。

HTH！

編集：コメントに答えるために分割されたサーバーとクライアントのコード

異なるフィルターを使用して同時クエリを処理できます

フィルタの状態はクライアントに保存されます。

サーバー-実装された関数とコード：

Clear["Global`*"];

(*Server Implemented  Functions follows*)

AdjustFilterState[fs_] := Module[{i, j}, (    (*fs = filterstate, i,j localvars*)
     i = fs[[1]]; (*local vars*)              (*w  = weights with accs*)
     j = fs[[2]];
     j++;                                     (* increment accumulator comparator*)
     If[j == weightsAcc[[i, 3]], i++];        (* if current id exhausted, get next*)
     If[i == Length@weightsAcc, i = 1; j = 0];(* wraparound table when exhausted*)
     Return[{i, j}];);
   ];


query[filter_, fs_] := Module[{fsTemp},       (*fs = filterstate*)
   (
    fsTemp = AdjustFilterState[fs];           (* local var *)

    While[Not@filter[[fsTemp[[1]], 2]],       (* get non filtered ids only *)
       fsTemp = AdjustFilterState[fsTemp]
    ];

    Return[{weightsAcc[[fsTemp[[1]], 1]], fsTemp}]; (*return[value,{filterState}]*)
   )
   ];

initFilter[] := masterFilter; (*Init filters to your defult vallue*)

(*The trick is to get the filter coordinated with the list value*)
updateFilter[f_, newValuePair_] :=
 Return@ReplaceAll[f, {newValuePair[[1]], x_} -> newValuePair];

(*Server Code - Just initialize the whole thing
   The SERVER stores ONLY the weights vectors and a master filter initialized*)

n = 10; (* nbr of ids *)                                (*init vars*)
m = 3;  (*max weight - 1 *)

weights = Table[{Prime@k, RandomInteger[m] + 1}, {k, n}]; (*random weights to test*)
accumulator = Accumulate[Table[k[[2]], {k, weights}]];    
weightsAcc = MapThread[Append, {weights, accumulator}];   (*add acummulator to list*)
masterFilter= Table[{k[[1]],True}, {k,weights}]; (* only ONE virgin filter in server*)

クライアントコード：

(* Client Code 
   The CLIENT stores only the filter and the filterState*)
(* Set up filter and filterstate *)

filter = initFilter[];
filter = updateFilter[filter, {2, False}];  (*specify particular values*)
filter = updateFilter[filter, {5, False}];

filterState = {1,0}; (* these replace the previous GLOBAL state variables *)

ValuesList = {};  (*for storing results *)

Do[
 q1 = query[filter, filterState]; (* do the query *)
 AppendTo[ValuesList, q1[[1]]];   (* first element of return is the value *)
 filterState = q1[[2]];           (* second element is updated filter state *)
 , {30}  (*do 30 times*)
 ];
Print@ValuesList                 (* print results vector *)
于 2010-11-13T05:06:43.653 に答える
0

異なるフィルターごとに追跡する必要があるように思われます。つまり、新しいフィルターが導入されるたび、またはすべての要素が古いフィルターに費やされるたびに、新しいシャッフルリストを作成する必要があります。

編集：比例値を使用するようになったので、シャッフルされたリストを完全に削除し、統計でシャッフルすることができます。クエリごとに、1つのカウンターをrandom（0..sum_of_all_enabled_weights_for_the_query）に設定します。リストの先頭から移動し、要素がクエリに対して有効になっている場合に発生するすべての重みをこのカウンターから減算し、無効になっている場合は無視します。カウンターが負になった場合、あなたは自分自身が要素であることに気づきました。

于 2010-11-13T01:24:04.477 に答える
-1

おそらく私は解決策を見つけました：

  1. id->number_of_queries_leftの初期値がであるストア。number_of_queries_leftたとえば、weight * 10リストが頻繁に更新されることはありません。正確に比例した要件が維持されると思います）。
  2. 各クエリで：
    1. idフィルタからランダムを選択します。ここで、is_enabledはですtrue。
    2. number_of_queries_leftそのためのデクリメントid。
    3. 結果がゼロ以下の場合は、それidを使用済みとしてマークし、別のものを選択します。
    4. すべての値が使用され、何も見つからない場合id->number_of_queries_leftは、フィルターで有効になっているすべてのIDを再初期化します（「再充電」）。

動作するようです。どう思いますか？

アップデート1：

id->number_of_queries_leftフィルタ値ごとに値を分けておく必要があるように見えるのではないかと心配です。メモリの制限のためにそれを買う余裕はありません（2 ^ 1000の潜在的なフィルター値があります）。私は正しいですか？

number_of_queries_left誰かが共有カウンターの結果をよりよく理解するのを手伝ってくれませんか？

アップデート2：

アイデアのクレジットはDiacleticusに送られます（この回答へのコメントを参照してください）。

フィルタで有効になっているすべてのアイテムをリセットせずid->number_of_queries_leftに、それぞれの重みでインクリメントするとどうなりますか？これでプロポーションが決まると思います。（またはそれをする必要がありますか？）

唯一の問題は、このアルゴリズムでは各number_of_queries_leftカウンターが非常に負になる可能性があることです。（上記を参照してください。値を確認するたびにデクリメントします。）

したがって、悲観的なケースでは、すべてのカウンターをインクリメントしても、それらのいずれもゼロを超えることはありません。値が正になるまでインクリメントループを効果的に実行するので、これはおそらく問題ありません。

アップデート3：

いいえ、値が正になるまでインクリメントループを実行することはできません。

これにより、重みが串刺しになります。その負の部分には「物理的な意味」がありません。クエリから返された値を表すものではありません。

したがって、ハイブリッドアプローチ：

「リチャージ」を行うときは、各カウンターを。ずつインクリメントしますweight + -min(0, current_counter_value)。これはアトミックに実行する必要がありますが、実行可能に見えます。

それでも、この場合、重量処理が公平になるかどうかはわかりません。

コメント？

于 2010-11-13T01:40:11.700 に答える