0

我有一个带有权重的元素列表：

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

权重是小整数（例如，小于 1000，通常小于 50）。列表中的 id 总数也小于 1000。（每个id只列出一次。）

对于每个查询，我必须从列表中返回一个“足够随机”的元素。如果我进行E查询，其中与所有权重的总和成正比，则每个元素元素必须 与其值完全成比例E的相同次数。请注意，这应该适用于较小的值（例如，最多 50 * 权重总和）。另请参阅问题末尾的注释。weightE

到目前为止一切顺利，我将通过将元素 ID 放入循环列表中来解决此任务，将它们复制权重时间，然后重新排列列表。每个查询都返回列表的头部，然后增加头部位置。

但在这种情况下，我还有一个附加条件：

我对查询有附加参数：过滤器。过滤器是 的映射id => is_enabled。如果is_enabled对于给定的 是 false id，id则应将其从结果中排除。上述E限制中的值仅针对启用的元素计算。也就是说，禁用的元素权重将从查询中排除。

过滤器对于每个查询都是“唯一的”，并且包含列表中每个查询的条目id。（请注意，这意味着 2^1000 个潜在过滤器值。）

有没有办法有效地解决这个问题？我需要算法在多服务器集群上高效。

注 1：我想强调的是，我相信，完全随机选择元素（如其中一个答案所建议的那样），而不存储任何状态，是行不通的。它只会在无限数量的查询中给出完全成比例的元素数量。随机数生成器完全有权在很长一段时间内返回不公平的值。

注 2：此任务对随机性的质量没有限制。仔细想想，在上面的简单案例解决方案中，甚至没有必要对列表进行洗牌。好的随机性更好，但根本没有必要。

注意 3：请注意，2^1000 个潜在过滤器值确实意味着我无法存储与过滤器值相关的任何内容——这将需要太多内存。我可以为最近的（或经常使用的）过滤器存储一些东西，但我不能存储项目列表偏移量之类的东西，因为我不能丢失这些数据。

注意 4：我们不能通过查询返回元信息并让客户端为我们存储状态（无论如何，这是个好主意，谢谢，Diacleticus）。我们不能，因为两个客户端可能会不小心使用相同的过滤器（某些过滤器比其他过滤器更受欢迎）。在这种情况下，我们必须对两个查询使用相同的状态。事实上，客户端执行多个查询是一种相对罕见的事件。

4

3 回答 3

0

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

编辑：现在我们使用比例值，我们可以完全删除打乱列表，让统计数据为我们打乱它。对于每个查询，将一个计数器设置为随机（0..sum_of_all_enabled_weights_for_the_query）。从列表的开头开始，如果元素为查询启用，则从该计数器中减去所有权重，如果禁用则忽略它。如果 counter 变为负数，那么您发现自己是一个元素。

于 2010-11-13T01:24:04.477 回答
0

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

我将一步一步地在 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}}

现在我们定义我们的查询。我们将使用两个全局变量（agrhhhh！）和两个函数来使事物同步：

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

当然，可以通过过滤器 False 跳过 id 来加速 while 循环，但我认为这样的意图更清楚。

现在我们执行 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 *)
于 2010-11-13T05:06:43.653 回答
-1

也许我找到了解决方案：

  1. Store 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 重新初始化（“recharge”）。

看起来它应该工作。你怎么看？

更新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 回答