## Re: [hackers-il] Algorithm for randomly choosing a question

Expand Messages
• ... sent before completed (whoops again)... I ment: you do not have to store weights of ALL the questions, just for the questions the user had seen (and you
Message 1 of 7 , Jul 7, 2012
• 0 Attachment

On Sun, Jul 8, 2012 at 12:38 AM, Amit Aronovitch wrote:

On Sun, Jul 8, 2012 at 12:28 AM, Amit Aronovitch wrote:

On Sat, Jul 7, 2012 at 9:06 AM, Om er Zak <w1@...> wrote:
On Sat, 2012-07-07 at 08:20 +0300, Ori Idan wrote:
[... description of the problem was snipped ...]
>         My wish is to have an algorithm which requires only bounded
>         number of
>         computations of random numbers (i.e. no loop) to accomplish
>         the above.
>         Assume that N is large, so keeping lists of questions in
>         memory is ruled
>         out.
>

(rather long, but nicely written and not hard to follow)

Whoops, missed the "N is large" thing (so O(n) memory might be too high, even if you just keep weights...). Still, a nice read to share.
I guess there's no escape from trading some memory for the time improvement...

sent before completed (whoops again)...

I ment: you do not have to store weights of ALL the questions, just for the questions the user had seen (and you have to store a list of these anyway). Since you know how many the user had already chosen, and the sum of their weights - first choose (using a single dart) whether you want a question from the seen set, or the unseen one (which is supposedly much larger). If the larger is chosen, choose uniformly. If the smaller (stored) set is selected, choose using the alias method or some simpler alternative.

• Hi! ... Keep three lists with pointers to unasked wrong and correct questions, moving questions between them. First choose from which list to pick your
Message 2 of 7 , Jul 8, 2012
• 0 Attachment
Hi!

On Sat, Jul 7, 2012 at 7:53 AM, Omer Zak <w1@...> wrote:
I want the application to be able to select any question randomly, but
with different weights, so that:
- A question the user never saw has weight of (say) 0.5.
- A question the user answered wrongly has weight of 1 (i.e. such a
question is twice more likely to be presented than a question never
seen).
- A question the user answered correctly has weight of 0.005 (i.e. it is
100 times less likely to be seen again than a question never seen
before).

Keep three lists with pointers to "unasked" "wrong" and "correct" questions, moving questions between them.
First choose from which list to pick your question (abuse length of list * weight for each list.)
Than pick up a random question from your chosen list.
if RAM is a problem, keep the lists offline :-)

Udi.
Your message has been successfully submitted and would be delivered to recipients shortly.