带滤波器的加权拾取[闭合]

在我看来,你必须对每一个不同的过滤器进行跟踪。这意味着您必须在每次引入新的过滤器或在所有元素都用于旧过滤器时构建一个新的无序列表。

编辑:现在我们使用比例值,我们可以完全删除无序列表,并让统计数据为我们进行无序处理。对于每个查询,将一个计数器设置为随机(0..sum_of_all_enabled_weights_For_the_query)。从列表的开头开始,从这个计数器中减去如果查询启用了元素,则会出现的所有权重,如果查询禁用了元素,则忽略它。如果计数器变为负数,那么你发现自己是一个元素。

看看我是否理解你的问题。

我将一步一步地在Mathematica中发布代码,并将注释输出轻松地跟踪它。

这个答案提供了一个确定性和有序的输出(即非洗牌)。如果你真的需要一个随机排列,你可以用同样的算法预先生成一个完全过滤的序列,洗牌它,然后一个一个地使用这些值。

程序

首先我们定义两个常数:

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)初始化过滤器。我用的是真的:

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];  

并使用它更改两个值:

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}}  

现在我们定义查询。我们将使用两个全局变量(agrhhh!)还有两个功能可以使事情同步:

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循环可以加速,只要跳过filter 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的值除外。

啊!

编辑:服务器和客户端代码被拆分以回答注释

它可以用不同的过滤器处理并发的查询

过滤器状态存储在客户端。

服务器实现的功能和代码:

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 *)

也许我找到了解决办法:

1. 商场 id->number_of_queries_left ,其中初始值为 number_of_queries_left 比如说, weight * 10 (因此列表不会经常刷新)-- 确切地 成比例的 我认为,这一要求将得到遵守。
2. 每次查询:
   1. 随机选取 id 从过滤器,其中 is_enabled 是 true .
   2. 减量 剩余查询数 为了这个 身份证件 .
   3. 如果结果小于或等于零,则标记 身份证件 像以前一样,再挑一个。
   4. 如果使用了所有值但未找到任何值,请重新初始化 id->剩余查询数 对于过滤器中启用的所有ID(“充值”)。

看起来应该有用。你怎么认为?

更新1:

我担心看起来我不得不 id->剩余查询数 为每个筛选器值分别设置值。由于内存限制,我负担不起(有2^1000个潜在的筛选值)。我说得对吗?

有谁能帮助我更好地理解 剩余查询数 柜台,请问?

更新2:

这个想法的功劳归于 Diacleticus (见对此答案的评论)。

如果我们不重置 id->剩余查询数 对于过滤器中的所有启用项,而是按其各自的权重递增?我认为这应该能确定比例。(或者应该这样做?)

唯一的问题是使用这个算法 剩余查询数 计数器可能会非常负。(见上文,我们每次想查看它的值时都会将其递减。)

因此,在悲观的情况下,即使把所有计数器递增,我们也不会使它们中的任何一个超过零。这可能是可以的,因为我们将有效地运行增量循环,直到任何值变为正值。

更新3:

不,在任何值变为正值之前,我们不能只运行增量循环。

这将扭曲权重:负数部分没有“物理意义”——它不表示查询返回的值。

因此,一种混合方法:

进行“充值”时,将每个计数器递增 weight + -min(0, current_counter_value) . 这应该是原子式的,但看起来是可行的。

不过,我不确定在这种情况下,重量处理是否公平。

评论?