Re: Algorithm for randomly choosing a question
Nadav Har'El <nyh-TS7m/[email protected]> Sun, 8 Jul 2012 10:23:12 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <[email protected]> |
--sd0i-ucaTSsmHZw8K6hNSPgY9MkWm1DBE5Ks90I Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit On Sat, Jul 07, 2012, Omer Zak wrote about "Re: [hackers-il] Algorithm for randomly choosing a question": > The proposed approach has the problem of memory consumption of order of > O(N) (where N is the number of the questions). I'd like to see an > algorithm whose memory consumption is closer to O(1) than to O(N). Omer, here is an O(1) *RAM* algorithm. Note that you still have O(N) disk usage, of course - there are N questions, and they need to be saved somewhere, and so is the history of the success for them. If you drop the O(1) memory requirement (which I think is an overkill for any type of modern computer), you can make things simpler. Note - I assume the number of probability classes (in your example, 1, 1/2 and 1/100, if I remember correctly) is constant (O(1)) and not O(N). Keep on disk a file for each probability class - one list of questions with normal probability (1), another list of questions with half probability, and a third list of questions with 1/100 probability. Each will be a list of numbers (indexing questions stored in a separate file). In *memory*, keep the number of questions in each class: n1, n2, n3, and the partial probability sums: p1 = n1*1 p2 = n1*1 + n2*(1/2.) p3 = n1*1 + n2*(1/2.) + n3*(1/100.) Each time you want to draw a random question, pick a random number between 0 and p3. If it's between 0 and p1, you decided to take a question from class 1. If it's between p1 and p2, you decided to take a question from class 3. If it's between p2 and p3, then from class 3. You decide *which* question to take in the obvious way - e.g., if you got a random number p between p1 and p2, then the question number in the class 2 list is m=(p-p1)/(1/2). You then need to look at the m'th position in the on-disk list of class 2 questions, to get the actual index of the question. Finally, when the user answers you need to update your data. You need to remove the question from the previous class (to do this in O(1) time, just move the last element of the list into the newly formed hole), and to add it to the new class (put it last), and of course update n1,n2,n3 and p1,p2,p3. Again, if you don't mind O(N) memory usage - actually just N*4 bytes - then I suggest that you do keep the list of questions - just their numbers - in memory. Then you won't need to read and write the disk all the time. Nadav. P.S. This is of course a variant on the classic shuffling (or random permutation) algorithm. In the shuffling algorithm, you need to draw random questions from the list, but after you used a question, you don't want to see it again (its probability becomes zero). Instead of keeping the used questions on the list (and getting O(N^2) time complexity for the whole shuffle operation), the trick is to move them to the end of the list, and to remember how many questions we still have (in the beginning of the list) to draw from. -- Nadav Har'El | Sunday, Jul 8 2012, 18 Tammuz 5772 nyh-TS7m/[email protected] |----------------------------------------- Phone +972-523-790466, ICQ 13349191 |If Barbie is so popular, why do you have http://nadav.harel.org.il |to buy her friends? --sd0i-ucaTSsmHZw8K6hNSPgY9MkWm1DBE5Ks90I Content-Type: text/html; charset=US-ASCII Content-Transfer-Encoding: 7bit <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> </head> <body style="background-color: #fff;"> <span style="display:none"> </span> <!--~-|**|PrettyHtmlStartT|**|-~--> <div id="ygrp-mlmsg" style="position:relative;"> <div id="ygrp-msg" style="z-index: 1;"> <!--~-|**|PrettyHtmlEndT|**|-~--> <div id="ygrp-text" > <p>On Sat, Jul 07, 2012, Omer Zak wrote about "Re: [hackers-il] Algorithm for randomly choosing a question":<br> > The proposed approach has the problem of memory consumption of order of<br> > O(N) (where N is the number of the questions). I'd like to see an<br> > algorithm whose memory consumption is closer to O(1) than to O(N).<br> <br> Omer, here is an O(1) *RAM* algorithm. Note that you still have O(N)<br> disk usage, of course - there are N questions, and they need to be saved<br> somewhere, and so is the history of the success for them.<br> If you drop the O(1) memory requirement (which I think is an overkill for<br> any type of modern computer), you can make things simpler.<br> <br> Note - I assume the number of probability classes (in your example,<br> 1, 1/2 and 1/100, if I remember correctly) is constant (O(1)) and not<br> O(N).<br> <br> Keep on disk a file for each probability class - one list of questions<br> with normal probability (1), another list of questions with half<br> probability, and a third list of questions with 1/100 probability.<br> Each will be a list of numbers (indexing questions stored in a separate<br> file).<br> <br> In *memory*, keep the number of questions in each class: n1, n2, n3,<br> and the partial probability sums:<br> p1 = n1*1<br> p2 = n1*1 + n2*(1/2.)<br> p3 = n1*1 + n2*(1/2.) + n3*(1/100.)<br> <br> Each time you want to draw a random question, pick a random number<br> between 0 and p3. If it's between 0 and p1, you decided to take a<br> question from class 1. If it's between p1 and p2, you decided to take<br> a question from class 3. If it's between p2 and p3, then from class 3.<br> <br> You decide *which* question to take in the obvious way - e.g., if you<br> got a random number p between p1 and p2, then the question number in the<br> class 2 list is m=(p-p1)/(1/2). You then need to look at the m'th<br> position in the on-disk list of class 2 questions, to get the actual<br> index of the question.<br> <br> Finally, when the user answers you need to update your data. You need<br> to remove the question from the previous class (to do this in O(1) time,<br> just move the last element of the list into the newly formed hole),<br> and to add it to the new class (put it last), and of course update<br> n1,n2,n3 and p1,p2,p3.<br> <br> Again, if you don't mind O(N) memory usage - actually just N*4 bytes -<br> then I suggest that you do keep the list of questions - just their<br> numbers - in memory. Then you won't need to read and write the disk<br> all the time.<br> <br> Nadav.<br> <br> P.S. This is of course a variant on the classic shuffling (or random<br> permutation) algorithm. In the shuffling algorithm, you need to draw<br> random questions from the list, but after you used a question, you don't<br> want to see it again (its probability becomes zero). Instead of keeping<br> the used questions on the list (and getting O(N^2) time complexity for<br> the whole shuffle operation), the trick is to move them to the end of<br> the list, and to remember how many questions we still have (in the<br> beginning of the list) to draw from. <br> <br> -- <br> Nadav Har'El | Sunday, Jul 8 2012, 18 Tammuz 5772<br> <a href="mailto:nyh%40math.technion.ac.il">nyh-TS7m/[email protected]</a> |-----------------------------------------<br> Phone +972-523-790466, ICQ 13349191 |If Barbie is so popular, why do you have<br> <a href="http://nadav.harel.org.il">http://nadav.harel.org.il</a> |to buy her friends?<br> </p> </div> <!--~-|**|PrettyHtmlStart|**|-~--> <div style="color: #fff; height: 0;">__._,_.___</div> <div id="ygrp-actbar" style="clear: both; margin-bottom: 10px; white-space: nowrap; color: #666; padding-top: 15px;"> <div> <a href="mailto:nyh-TS7m/[email protected]?subject=Re%3A%20%5Bhackers-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question" style="margin-right: 0; padding-right: 0;"> Reply to <span style="font-weight: 700;">sender</span></a> | <a href="mailto:[email protected]?subject=Re%3A%20%5Bhackers-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question"> Reply to <span style="font-weight: 700;">group</span></a> | <a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJwaGhyNzB2BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODgEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQxNzMyMjAw?act=reply&messageNum=5188">Reply <span style="font-weight: 700;">via web post</span></a> | <a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlaGlhMG90BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MTczMjIwMA--" style="font-weight: 700;">Start a New Topic</a> </div> <a href="http://groups.yahoo.com/group/hackers-il/message/5185;_ylc=X3oDMTM0MjNzdXZzBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODgEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQxNzMyMjAwBHRwY0lkAzUxODU-">Messages in this topic</a> (<span style="font-weight: 700;">4</span>) </div> <!------- Start Nav Bar ------> <!-- |**|begin egp html banner|**| --> <div id="ygrp-vital" style="background-color: #e0ecee; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;"> <span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span> <ul style="list-style-type: none; margin: 0; padding: 0; display: inline;"> <li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;"> <span class="cat"><a href="http://groups.yahoo.com/group/hackers-il/members;_ylc=X3oDMTJmYjA4cmwzBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDE3MzIyMDA-?o=6" style="text-decoration: none;">New Members</a></span> <span class="ct" style="color: #ff7900;">1</span> </li> </ul> <div style="clear: both; padding-top: 2px; color: #1e66ae;"> <a href="http://groups.yahoo.com/group/hackers-il;_ylc=X3oDMTJlb2ltbnU3BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM0MTczMjIwMA--" style="text-decoration: none;">Visit Your Group</a> </div> </div> <div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;"> <a href="http://groups.yahoo.com/;_ylc=X3oDMTJkdDc0cDI4BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzQxNzMyMjAw" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a> <div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a></div> </div> <!-- |**|end egp html banner|**| --> </div> <!-- ygrp-msg --> <!-- Sponsor --> <!-- |**|begin egp html banner|**| --> <div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;"> <!-- Start Recommendations --> <div id="ygrp-reco"> </div> <!-- End Recommendations --> </div> <!-- |**|end egp html banner|**| --> <div style="clear:both; color: #FFF; font-size:1px;">.</div> </div> <img src="http://geo.yahoo.com/serv?s=97359714/grpId=1857332/grpspId=1705006764/msgId=5188/stime=1341732200/nc1=3848642/nc2=4507179/nc3=5191954" width="1" height="1"> <br> <div style="color: #fff; height: 0;">__,_._,___</div> <!--~-|**|PrettyHtmlEnd|**|-~--> </body> <!--~-|**|PrettyHtmlStart|**|-~--> <head> <style type="text/css"> <!-- #ygrp-mkp { border: 1px solid #d8d8d8; font-family: Arial; margin: 10px 0; padding: 0 10px; } #ygrp-mkp hr { border: 1px solid #d8d8d8; } #ygrp-mkp #hd { color: #628c2a; font-size: 85%; font-weight: 700; line-height: 122%; margin: 10px 0; } #ygrp-mkp #ads { margin-bottom: 10px; } #ygrp-mkp .ad { padding: 0 0; } #ygrp-mkp .ad p { margin: 0; } #ygrp-mkp .ad a { color: #0000ff; text-decoration: none; } #ygrp-sponsor #ygrp-lc { font-family: Arial; } #ygrp-sponsor #ygrp-lc #hd { margin: 10px 0px; font-weight: 700; font-size: 78%; line-height: 122%; } #ygrp-sponsor #ygrp-lc .ad { margin-bottom: 10px; padding: 0 0; } a { color: #1e66ae; } #actions { font-family: Verdana; font-size: 11px; padding: 10px 0; } #activity { background-color: #e0ecee; float: left; font-family: Verdana; font-size: 10px; padding: 10px; } #activity span { font-weight: 700; } #activity span:first-child { text-transform: uppercase; } #activity span a { color: #5085b6; text-decoration: none; } #activity span span { color: #ff7900; } #activity span .underline { text-decoration: underline; } .attach { clear: both; display: table; font-family: Arial; font-size: 12px; padding: 10px 0; width: 400px; } .attach div a { text-decoration: none; } .attach img { border: none; padding-right: 5px; } .attach label { display: block; margin-bottom: 5px; } .attach label a { text-decoration: none; } blockquote { margin: 0 0 0 4px; } .bold { font-family: Arial; font-size: 13px; font-weight: 700; } .bold a { text-decoration: none; } dd.last p a { font-family: Verdana; font-weight: 700; } dd.last p span { margin-right: 10px; font-family: Verdana; font-weight: 700; } dd.last p span.yshortcuts { margin-right: 0; } div.attach-table div div a { text-decoration: none; } div.attach-table { width: 400px; } div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited { text-decoration: none; } div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited { text-decoration: none; } div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts { font-family: Verdana; font-size: 10px; font-weight: normal; } .green { color: #628c2a; } .MsoNormal { margin: 0 0 0 0; } o { font-size: 0; } #photos div { float: left; width: 72px; } #photos div div { border: 1px solid #666666; height: 62px; overflow: hidden; width: 62px; } #photos div label { color: #666666; font-size: 10px; overflow: hidden; text-align: center; white-space: nowrap; width: 64px; } #reco-category { font-size: 77%; } #reco-desc { font-size: 77%; } .replbq { margin: 4px; } #ygrp-actbar div a:first-child { /* border-right: 0px solid #000;*/ margin-right: 2px; padding-right: 5px; } #ygrp-mlmsg { font-size: 13px; font-family: Arial, helvetica,clean, sans-serif; *font-size: small; *font: x-small; } #ygrp-mlmsg table { font-size: inherit; font: 100%; } #ygrp-mlmsg select, input, textarea { font: 99% Arial, Helvetica, clean, sans-serif; } #ygrp-mlmsg pre, code { font:115% monospace; *font-size:100%; } #ygrp-mlmsg * { line-height: 1.22em; } #ygrp-mlmsg #logo { padding-bottom: 10px; } #ygrp-mlmsg a { color: #1E66AE; } #ygrp-msg p a { font-family: Verdana; } #ygrp-msg p#attach-count span { color: #1E66AE; font-weight: 700; } #ygrp-reco #reco-head { color: #ff7900; font-weight: 700; } #ygrp-reco { margin-bottom: 20px; padding: 0px; } #ygrp-sponsor #ov li a { font-size: 130%; text-decoration: none; } #ygrp-sponsor #ov li { font-size: 77%; list-style-type: square; padding: 6px 0; } #ygrp-sponsor #ov ul { margin: 0; padding: 0 0 0 8px; } #ygrp-text { font-family: Georgia; } #ygrp-text p { margin: 0 0 1em 0; } #ygrp-text tt { font-size: 120%; } #ygrp-vital ul li:last-child { border-right: none !important; } --> </style> </head> <!--~-|**|PrettyHtmlEnd|**|-~--> </html> <!-- end group email --> --sd0i-ucaTSsmHZw8K6hNSPgY9MkWm1DBE5Ks90I--