0

There are many typical questions like Return random `list` item by its `weight`

Imagine more advanced problem.

You have N sources of pair (item_id, weight) information. Let's call them Shards. Shards contain lists of pairs (item_id, weight).

And you have central node, let's call it Central.

The problem is: on Central choose random item from The Big List (the list virtually merged from all lists on all shards) according to their weight through all weights.

For example, we have two shards:

+-------+---------+--------+
| shard | item_id | weight |
+-------+---------+--------+
|   1   |     1   |    7   |
|   1   |     2   |    4   |
|   1   |     3   |    2   |
|   2   |     4   |    5   |
|   2   |     5   |    1   |
+-------+---------+--------+

(Let item_id will be unique through all shards.)

First problem:

How to choose item_id randomly but weighted through all shards? I.e. total_weight == 7+4+2+5+1 == 19, so 1 will be chosen with probability of 7/19, 2 - 4/19, 3 - 2/19 and so on.

Second problem:

How to range all items from all shards randomly, but weighted through all shards?

I.e. ideal ranging will be: 1, 4, 2, 3, 5 (according to their weights),

but there may be another ranging like 1, 2, 4, 3, 5, but slightly less frequently than previous,

...

and worst case 5, 3, 2, 4, 1 can also appear, but with very-very little probability.

Is there common problem in computer science for this?

1
  • What do you mean by your second problem? The sum of the weights for the items from a shard should indicate how likely it is that an item from that shard gets chosen. If the weight distribution over the shards is really skewed, then the shard selection will be anything but random, while the item selection still is. Sep 6, 2016 at 11:12

1 Answer 1

1

In problem 1, you do not use the information to which shard a certain item belongs. So this is actually just choosing an item randomly with weights. You can use the method in the post you linked to.

For problem 2 I think you could repeatedly apply problem 1. First you choose the first item and then you recalculate your list and weightings. This can be done smartly by for example substracting the weight of the item you choose first from the total weight. Then repeat for the second item, etc...

More concrete, suppose you apply problem 1 once, and it chooses 4 weightedly at random. Then you would apply problem 1 again on:

+---------+--------+

| item_id | weight |

+---------+--------+

|     1   |    7   |

|     2   |    4   |

|     3   |    2   |

|     5   |    1   |

+---------+--------+

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.