Взвешенный выбор с фильтрами

Question

У меня есть список элементов с весами:

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

Веса - это маленькие целые числа (скажем, менее 1000, часто менее 50). Общее количество идентификаторов в списке также меньше 1000. (Каждый id указан только один раз.)

Для каждого запроса я должен вернуть "достаточно случайный" элемент из списка. Если я сделаю E запросы, где E пропорционально сумме всех весов, то же количество раз каждый элемент элемента должен быть точно пропорционален его элементу weight значение. Обратите внимание, что это должно работать для меньших значений E (скажем, до 50 * сумма весов). Смотрите также примечание в конце вопроса.

Пока все хорошо, я бы решил эту задачу, поместив идентификаторы элементов в круговой список, продублировав их значениями веса, а затем перетасовав список. Каждый запрос возвращает заголовок списка, а затем увеличивает позицию заголовка.

Но в этом случае у меня есть еще одно условие:

У меня есть дополнительный параметр к запросу: фильтр. Фильтр - это карта id => is_enabled, Если is_enabled ложно для данного id, тот id следует исключить из результатов. E Значение в вышеуказанном ограничении рассчитывается только для включенных элементов. То есть веса отключенных элементов должны быть исключены из запроса.

Фильтры являются "уникальными" для каждого запроса и включают записи для каждого id в списке. (Обратите внимание, что это подразумевает 2^1000 потенциальных значений фильтра.)

Есть ли способ решить это эффективно? Мне нужно, чтобы алгоритм был эффективным на многосерверном кластере.

Примечание 1: Я хочу подчеркнуть, что, как я полагаю, выбор элементов совершенно случайно (как предложено в одном из ответов) без сохранения какого-либо состояния не будет работать. Это даст точно пропорциональное количество элементов только на бесконечном количестве запросов. Генератор случайных чисел имеет полное право возвращать несправедливые значения в течение длительного периода времени.

Примечание 2: Эта задача не накладывает никаких ограничений на качество случайности. Если подумать, даже не нужно перетасовывать список в простом решении выше. Хорошая случайность лучше, но не обязательна.

Примечание 3: Обратите внимание, что 2^1000 потенциальных значений фильтра означают, что я не могу ничего хранить, связанных со значением фильтра - это потребует слишком много памяти. Я могу хранить что-то для самых последних (или часто используемых) фильтров, но я не могу хранить такие вещи, как смещение списка элементов, поскольку я не могу позволить себе потерять эти данные.

Примечание 4: Мы не можем вернуть метаинформацию с запросом и позволить клиентам сохранять для нас состояние (в любом случае, хорошая идея, спасибо, Dialecticus). Мы не можем, потому что два клиента могут случайно использовать один и тот же фильтр (некоторые фильтры более популярны, чем другие). В этом случае мы должны использовать одно и то же состояние для обоих запросов. Фактически, клиент, выполняющий более одного запроса, является относительно редким событием.

Answer 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 для всех идентификаторов, которые включены в фильтр ("перезарядка").

Похоже, это должно работать. Как вы думаете?

Обновление 1:

Я беспокоюсь, что похоже, что я должен держать id->number_of_queries_left значение отдельно для каждого значения фильтра. Я не могу себе этого позволить из-за ограничений памяти (есть 2^1000 потенциальных значений фильтра). Я прав?

Может ли кто-нибудь помочь мне лучше понять последствия совместного number_of_queries_left счетчик, пожалуйста?

Обновление 2:

Кредиты за идею идут к Dialecticus (см. Комментарии к этому ответу).

Что если мы не сбросим id->number_of_queries_left для всех включенных элементов в фильтре, но вместо этого увеличить их на соответствующие веса? Я думаю, что это должно исправить пропорции. (Или должен?)

Единственная проблема заключается в том, что с этим алгоритмом каждый number_of_queries_left Счетчик может идти очень отрицательно. (См. Выше, мы уменьшаем его каждый раз, когда хотим посмотреть на его значение.)

Таким образом, в пессимистическом случае, даже увеличивая все счетчики, мы не будем приводить ни одного из них выше нуля. Это, вероятно, нормально, так как мы фактически просто запустим цикл приращения, пока любое значение не станет положительным.

Обновление 3:

Нет, мы не можем просто запустить цикл приращения, пока любое значение не станет положительным.

Это будет искажать веса: эта отрицательная часть не имеет "физического смысла" - она ​​не представляет значения, возвращаемые из запроса.

Таким образом, гибридный подход:

При выполнении "перезарядки" увеличивайте каждый счетчик на weight + -min(0, current_counter_value), Это должно быть сделано атомарно, но это выглядит выполнимо.

Тем не менее, я не уверен, что управление весом будет справедливым в этом случае.

Комментарии?

Answer 2

Мне кажется, что вы должны следить за каждым отдельным фильтром. Это означает, что вы должны создавать новый перемешанный список каждый раз, когда вводится новый фильтр, или когда все элементы расходуются на старый фильтр.

РЕДАКТИРОВАТЬ: Теперь, когда мы работаем с пропорциональными значениями, мы можем полностью удалить перетасованный список и позволить статистике перемешать его для нас. Для каждого запроса установите один случайный счетчик (0..sum_of_all_enabled_weights_for_the_query). Перейдите от начала списка и вычтите из этого счетчика все веса, которые вы встретите, если элемент включен для запроса, и просто проигнорируйте его, если он отключен. Если счетчик становится отрицательным, то вы оказались элементом.

Answer 3

Посмотрим, понял ли я твой вопрос.

Я опубликую код в Mathematica шаг за шагом, и закомментированный вывод, чтобы легко следовать ему.

Этот ответ обеспечивает детерминированный и упорядоченный вывод (т. Е. Не тасование). Если вам действительно нужна случайная перестановка, вы заранее генерируете полностью отфильтрованную последовательность с помощью того же алгоритма, перемешиваете ее и используете значения по одному.

Программа

Сначала мы определяем две константы:

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

Я оставляю цифры маленькими, чтобы мы могли шаг за шагом проверять вывод.

Теперь мы определим случайную таблицу {id, weight} для работы. Мы используем простые числа в качестве идентификаторов:

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}  

И мы объединяем обе таблицы, чтобы получить аккумуляторы в таблицу идентификаторов:

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

Хитрость заключается в том, чтобы синхронизировать фильтр с вектором идентификаторов, поэтому мы определяем функцию для обновления фильтра таким образом:

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

Конечно, цикл while можно было бы ускорить, просто пропустив идентификаторы с фильтром False, но я думаю, что намерение проясняется таким образом.

Сейчас мы выполним запрос 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 *)