I'll do a small simplification in order to use a much simpler model: I assume that we have one list (duplicates allowed) and one set (no duplicates allowed).

Then for each member of the list, the probability of having a match in the set is P(1) = 1e6/2**32.

Since we've assumed a list, all the probabilities of having matches are independent, and the expectation value is simply 1e6 * P(1) = 1e6 * 1e6/2**32 = 232.83.

If the number of matches is a Poisson distribution (and I suspect it is, in this example), then the standard deviation is simply the square root of the expectation value, so 15.5.

It is hard for me to estimate how big an error I've made by this simplification; I'll update the node if I get an idea of how to estimate it.

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags :
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
For:
Use:
& &
< <
> >
[ [
] ]

Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
Log In ^{?}
remember me
What's my password?
Create A New User
Chatterbox ^{?}
[ Corion ] : Yesterday I encountered an interesting data structure problem. I have a remote program that emits events, and my client listens for these events with one-shot callbacks, that is, I register the callback and if the event gets generated that callback ...
[ Lady_Aleena ] : robby_dobby , every day. Chaos is my life with few controls.
[ Corion ] : ... gets called once. The data structure for that is just a hash of arrays, mapping the event type to a queue of registered one-shots, and the first one-shot from the queue gets removed and called.
[ Corion ] : But now I want to register a one-shot for two events, of which only one will arrive, so my data structure doesn't work anymore...
[ Lady_Aleena ] : Corion , ouchy.
[ Corion ] : (maybe I should write this up as a SoPW) - currently, the "most efficient" data structure I come up with is a single array which I scan for the first fitting one-shot. Not efficient but I don't expect more than five outstanding one-shots anyway
[ choroba ] : can't you create a meta-key corresponding to the disjunction of the events?
[ robby_dobby ] : Corion : Heh. This whole thing smells of Strategy Pattern or MVC pattern.
[ Corion ] : And performance linear to the number of registered one-shots doesn't feel that bad. Maybe I should collect statistics on how many callbacks are outstanding ;)
[ Corion ] : choroba : Yes, but the longer I thought about efficient hashes mapping the event type back to their callbacks, and how to keep them in sync, the more I thought that all that optimization might just not be worth it, even if it's horribly inelegant

How do I use this? | Other CB clients
Other Users ^{?}
Others musing on the Monastery: (9)As of 2017-05-29 07:52 GMT
Sections ^{?}
Information ^{?}
Find Nodes ^{?}
Leftovers ^{?}
Voting Booth ^{?}