A-RES calls for the selection of m distinct random items out of a population of size n, each item with weight.

but my case is:

a huge stream of input(some item maybe conflict many times with different weight)

ex (itemID: weight) : a:10, b:5, ... a: 20... b:20, c:30...

select m distinct item from this population. "a" weight should be sum all a's weight.

my question : is there any algorithm can do this case ?

  • $\begingroup$ The part "a weight should be sum all a's weight" is bit unclear. $\endgroup$
    – codeR
    Commented Jul 4 at 9:01
  • $\begingroup$ If you want to sum all the weights for the selected items, you simply do a sampling first, then add up the weights by scanning the entire stearm once again. $\endgroup$
    – codeR
    Commented Jul 4 at 9:03


Your Answer

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

Browse other questions tagged or ask your own question.