Die gewichteten Plektrum mit Filter [geschlossen]

StackOverflow https://stackoverflow.com/questions/4170336

  •  09-10-2019
  •  | 
  •  

Frage

Ich habe eine Liste von Elementen mit Gewichten: 

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

Die Gewichte sind kleine ganze Zahlen (beispielsweise weniger als 1000, oft weniger als 50). Gesamtzahl der IDs in der Liste ist weniger als 1000 als gut. (Jeder id wird nur einmal aufgeführt.)

Für jede Abfrage Ich habe ein „random genug“ Element aus der Liste zurückzukehren. Wenn ich E Abfragen tun, wo E auf die Summe aller Gewichte proportional ist, muss die gleiche Anzahl, wie oft jedes Element Element genau proportional , um seinen weight Wert. Beachten Sie, dass dies für kleinere Werte von E arbeiten sollten (sagen wir bis zu 50 * Summe der Gewichte). Siehe auch Hinweis am Ende der Frage.

So weit so gut, würde ich diese Aufgabe lösen, indem Element-IDs in eine kreisförmige Liste, so dass ihnen das Gewicht mal duplizieren, dann die Liste schlurfen. Jede Abfrage gibt Kopf der Liste, und erhöht dann die Kopfposition.

Aber in diesem Fall hat er eine zusätzliche Bedingung:

Ich habe zusätzliche Parameter für die Abfrage: ein Filter. Ein Filter ist eine Karte von id => is_enabled. Wenn is_enabled für eine gegebene id falsch ist, sollte diese id aus den Ergebnissen ausgeschlossen. Der E Wert in der obigen Beschränkung berechnet nur für Elemente aktiviert. Das heißt, sind deaktiviert Elemente Gewichte von der Abfrage ausgeschlossen werden.

Filter sind „einzigartig“ für jede Abfrage und Einträge für jeden id in der Liste. (Beachten Sie, dass dies impliziert, 2 ^ 1000 mögliche Filterwerte.)

Gibt es eine Möglichkeit, diese effizient zu lösen? Ich brauche den Algorithmus effizient zu sein auf einem Multi-Server-Cluster.

Hinweis 1: Ich möchte betonen, dass, wie ich glaube, Elemente völlig wahllos Auswahl (wie in einer der Antworten vorgeschlagen), ohne dass der Staat zu speichern, wird nicht funktionieren. Es gibt genau proportionale Anzahl von Elementen nur auf unendliche Anzahl von Abfragen. Zufallszahlengenerator volles Recht hat, über einen langen Zeitraum unfaire Werte zurückzukehren.

Hinweis 2: erlegt diese Aufgabe keine Einschränkungen für die Qualität der Zufälligkeit. Kommen Sie, daran zu denken, ist es nicht einmal notwendig, die Liste in der einfachen Falllösung zu mischen oben. Gute Zufälligkeit ist besser, aber nicht notwendig, überhaupt nicht.

Hinweis 3: Bitte beachten Sie, dass 2 ^ 1000 mögliche Filterwerte bedeutet das, dass ich nichts speichern kann, mit dem Filterwert zugeordnet - es wird zu viel Speicher benötigen. Ich kann für etwas, speichere die letzten (oder häufig verwendet) Filter, aber ich kann nicht speichern Dinge wie Artikelliste versetzt, wie ich nicht leisten kann, diese Daten zu verlieren.

Hinweis 4: Wir können nicht Metainformationen mit der Abfrage zurückgeben und lassen Kunden für uns, den Zustand zu speichern (gute Idee, wie auch immer, danke, Diacleticus ). Wir können nicht, weil zwei Clients versehentlich den gleichen Filter verwenden können (einige Filter sind beliebter als andere). In diesem Fall müssen wir den gleichen Zustand für beide Abfragen verwenden. In der Tat tut Client mehr als eine Abfrage ein relativ seltenes Ereignis ist.

War es hilfreich?

Lösung 3

Vielleicht habe ich eine Lösung gefunden:

  1. Shop id->number_of_queries_left, wo Anfangswert für number_of_queries_left ist, sagen wir, weight * 10 (so dass die Liste nicht zu oft aufgefrischt wird - genau proportional Anforderung gehalten werden würde, denke ich, ).
  2. Bei jeder Abfrage:
    1. Wählen Sie eine zufällige id aus Filter, wo is_enabled true ist.
    2. Decrement number_of_queries_left für diese id.
    3. Wenn das Ergebnis kleiner oder gleich Null ist, Markierung, dass id wie verwendet und ein anderes wählen.
    4. Wenn alle Werte verwendet werden und keine gefunden, neu initialisieren id->number_of_queries_left für alle IDs, die in dem Filter ( „aufladen“) aktiviert sind.

Sieht aus wie es funktionieren soll. Was denken Sie?

Update 1:

Ich bin besorgt, dass es so aussieht, dass ich für jeden Filterwert id->number_of_queries_left Wert getrennt zu halten. Ich kann nicht leisten, dass aufgrund von Speicherbeschränkungen (es gibt 2 ^ 1000 mögliche Filterwerte). Bin ich richtig?

Kann jemand mir helfen, besser auf die Folgen des gemeinsamen number_of_queries_left Zähler zu verstehen, bitte?

Update 2:

Credits für die Idee gehen Diacleticus (siehe Kommentare zu dieser Antwort).

Was passiert, wenn wir nicht zurückgesetzt id->number_of_queries_left für alle aktivierten Elemente im Filter, sondern erhöhen sie durch ihre jeweiligen Gewichte? Ich denke, dass dies die Proportionen zu beheben. (Oder sollte es?)

Das einzige Problem ist, dass mit diesem Algorithmus jeden number_of_queries_left Zähler sehr negativ werden kann. (Siehe oben, wir verringern sie jedes Mal, wenn wir zu ihrem Wert suchen.)

Also, in einem pessimistischen Fall, auch durch alle Zähler erhöht wird, werden wir einen von ihnen über Null nicht bringen. Dies ist wahrscheinlich in Ordnung, da wir effektiv nur den Schritt Schleife laufen, bis jeder Wert positiv sein wird.

Update 3:

Nein, können wir nicht nur die Schritt Schleife laufen, bis jeder Wert wird positiv werden.

Damit werden die Gewichte Spieß., Dass negative Teil nicht „physischen Sinn“ hat - es spielt keine Werte repräsentieren, aus der Abfrage zurückgegeben

So wird ein hybrider Ansatz:

Wenn „aufladen“ zu tun, erhöhen Sie jeden Zähler um weight + -min(0, current_counter_value). Dies sollte atomar getan werden, aber das sieht machbar.

Aber ich bin mir nicht sicher, dass das Gewicht Handhabung Messe in diesem Fall sein wird.

Kommentare?

Andere Tipps

Es scheint mir, dass Sie eine Spur für jede unterschiedliche Filter halten müssen. Dies bedeutet, dass Sie jedes Mal, wenn ein neuer Filter eingeführt, um eine neue Shuffled Liste aufbauen müssen oder wenn alle Elemente für alte Filter ausgegeben werden.

EDIT: Nun, da wir mit proportionalen Werten arbeiten können wir die neu gemischt Liste sogar komplett löschen, und lassen Sie Statistiken mischen es für uns. Für jede Abfrage gesetzt einen Zähler zu zufälligen (0..sum_of_all_enabled_weights_for_the_query). Gehen Sie von Anfang der Liste, und subtrahiert von diesem Zähler alle Gewichte, dass Sie zusammen kommen, wenn das Element für die Abfrage aktiviert ist, und es einfach zu ignorieren, wenn sie deaktiviert ist. Wenn der Zähler negativ wird dann steht man ein Element.

Lassen Sie sich sehen, ob ich verstehe Ihre Frage.

Ich werde den Code in Mathematica Schritt für Schritt veröffentlichen, und die kommentierte Ausgabe, die es leicht zu folgen.

Diese Antwort stellt eine deterministische und geordnete Ausgabe (dh nicht-Trippeln). Wenn Sie wirklich eine zufällige Permutation benötigen, erzeugen Sie eine vollständige gefilterte Sequenz im Voraus mit dem gleichen Algorithmus, mische sie und verbrauchen die Werte eins nach dem anderen.

Das Programm

Faust wir definieren zwei Konstanten: 

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

Ich halte die Zahlen klein, so dass wir die Ausgabe Schritt für Schritt überprüfen.

Wir definieren nun eine zufällige {id, Gewicht} Tabelle zur Arbeit mit. Wir verwenden Primzahlen als ids: 

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

Ausgabe: 

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

Als nächstes werden wir akkumulieren die Gewichte Werte 

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

Ausgabe: 

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

Und wir fusionieren beiden Tabellen die Akkus in die ID-Tabelle zu erhalten: 

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

Ausgabe: 

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

Nun initialisieren wir die Filter, mit Standardwerten (true oder false). Ich verwendete True: 

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

Ausgabe: 

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

Der Trick ist, die Filter mit dem ids Vektor synchronisiert zu halten, so dass wir eine Funktion zur Aktualisierung des Filters auf diese Weise definieren: 

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

Und es verwendet, um zwei Werte zu ändern: 

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

Ausgabe: 

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

Nun definieren wir unsere Abfrage. Wir werden zwei globale Vars verwenden (agrhhhh!) Und zwei Funktionen, die Sache zu bekommen synchronisiert: 

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

Natürlich ist die while-Schleife nur beschleunigt werden, um die IDs mit Filter Falsch-Skipping, aber ich denke, dass die Absicht klarer ist auf diese Weise.

Jetzt führen wir die Abfrage 30-mal: 

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

und get: 

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

Welche unsere Liste (zyklisch) mit den richtigen Gewichten ist, mit Ausnahme der Werte mit dem Filter in FALSCH.

HTH!

Bearbeiten: Server und Client-Code gespaltet Kommentare zu beantworten

Es kann gleichzeitig querys mit verschiedenen Filtern bearbeitet

Der Filterzustand auf dem Client gespeichert ist.

Server-implementierter Funktionen und Code: 

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: 

(* 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 *)
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top