Deterministisch eine ID in einer Liste von gewichteten Buckets zuweisen

Ich bin n Split-Tests auf einer Website ausgeführt. Ich möchte eine gleichmäßig verteilte Integer-Benutzer-ID einem der n Buckets zuweisen, und deterministisch erhält derselbe Benutzer immer den gleichen Test.Deterministisch eine ID in einer Liste von gewichteten Buckets zuweisen

An dieser Stelle kann ich einfach einen Index in der Liste der Split-Tests auswählen, indem ich die Benutzer-ID um n modde. Was ist, wenn ich bestimmte Tests gewichten möchte?

Zum Beispiel wird Bucket # 1/21 zu 90% der Zeit zugeordnet und die restlichen 20 Tests werden zu 0,5% der Zeit zugewiesen.

Ich habe das Gefühl, ich kann irgendwie die Größe meiner Liste vergrößern und benutze immer noch die Mod-Technik, um dies zu erreichen, aber potentiell riesige, temporäre Listen im Speicher zu haben, scheint unelegant zu sein.

Quelle

2010-12-22 Bluu

Wenn die meisten Buckets unterschiedliche Größen haben, wobei Größe als Prozentsatz von IDs definiert ist, müssen Sie dies irgendwie im Speicher darstellen. Wie sonst würden Sie diese Prozentsätze sonst noch wissen?

Eine Lösung zu verwenden ist, sagen wir 100 virtuelle Buckets, von denen jeder 1% der IDs darstellt. Ordnen Sie dann 90 der virtuellen Buckets dem Bucket # 1/21 zu. Dann können Sie eine Mod 100 ausführen und wenn sie in die ersten 90 virtuellen Buckets fällt, weisen Sie die ID Bucket # 1 zu. Sie können die optimale Anzahl virtueller Buckets ermitteln, indem Sie den Bucket-Prozentsatz jedes Buckets durch die GCD aller Prozentsätze dividieren, was in Ihrem Beispiel 0,5 (GCD (90, 0,5)) ist.

In Ihrem Beispiel gibt es nur eine eindeutige Bucket-Größe. Die beste Lösung hängt wirklich davon ab, welche Arten von Vereinbarungen Sie haben könnten.

Quelle

2010-12-22 23:41:29 marcog

Um zu verdeutlichen, ist die optimale Anzahl von virtuellen Buckets die SUMME des Bucket-Prozentsatzes geteilt durch den GCD. Ich konnte das in Python naiv mit einer Liste kodieren, die auf die optimale Zahl wächst. Ich frage mich, ob dies mit weniger Speicher gemacht werden kann, zB indem nur die Nummernbereiche aufgezeichnet werden, in denen die Buckets fallen, was wie die gewählte Antwort hier aussehen würde http://stackoverflow.com/questions/2140787/select-random- k-Elemente-aus-einer-Liste-Wobei-Elemente-Gewichte haben. Wenn du Pseudocode veröffentlichen könntest, wäre das großartig. Sonst werde ich meine Lösung bald posten. – Bluu

Könnten Sie auch klarstellen, was Sie mit einer bestimmten Bucket-Größe meinen? Welche anderen Arrangements gibt es? – Bluu

@Bluu In Bezug auf die eindeutige Löffelgröße war Ihr Beispiel 1x90% + 20x0.5%. Der 90% Eimer ist der einzige, der sich vom Rest unterscheidet. – marcog

Deterministisch eine ID in einer Liste von gewichteten Buckets zuweisen

Antwort

Verwandte Themen