Re: Algorithm for randomly choosing a question
Omer Zak <w1-W6cp89mEpD1mR6Xm/[email protected]> Sun, 08 Jul 2012 11:14:30 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <1341735270.10101.24.camel@c4> |
--VGBmOeRkO6DXYoVm1aHQoBf6E49lJGRza2L3XTt
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Hello Nadav,
Thanks for your answer.
I ended up implementing something similar to your proposal.
The questions are stored in a SQLite database, so I don't mind at all
O(N) disk space consumption. I did want O(1) RAM consumption, as RAM is
to be considered as a scarce resource in smartphones.
The number of probability classes is finite (3 if to be exact). In
principle, it is possible to have a more sophisticated algorithm for
selecting the next question (with unlimited, time varying probability
classes) but I don't think that the subject matter warrants this kind of
sophistication.
The disk files for each probability class are being kept implicitly - as
result sets of queries for each probability class.
The actual performance of the algorithm (O(1), O(N) or whatever)
actually depends upon the DB performance, which I didn't bother to
benchmark or fine tune as a function of the number of questions.
I did not (even implicitly) implement the optimization that you
suggested for O(1) disk filee modifications.
--- Omer
On Sun, 2012-07-08 at 10:23 +0300, Nadav Har'El wrote:
> 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.
--
Sent from a PC running a top secret test version of Windows 97.
My own blog is at http://www.zak.co.il/tddpirate/
My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
--VGBmOeRkO6DXYoVm1aHQoBf6E49lJGRza2L3XTt
Content-Type: text/html; charset=UTF-8
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>Hello Nadav,<br>
Thanks for your answer.<br>
<br>
I ended up implementing something similar to your proposal.<br>
The questions are stored in a SQLite database, so I don't mind at all<br>
O(N) disk space consumption. I did want O(1) RAM consumption, as RAM is<br>
to be considered as a scarce resource in smartphones.<br>
<br>
The number of probability classes is finite (3 if to be exact). In<br>
principle, it is possible to have a more sophisticated algorithm for<br>
selecting the next question (with unlimited, time varying probability<br>
classes) but I don't think that the subject matter warrants this kind of<br>
sophistication.<br>
<br>
The disk files for each probability class are being kept implicitly - as<br>
result sets of queries for each probability class.<br>
The actual performance of the algorithm (O(1), O(N) or whatever)<br>
actually depends upon the DB performance, which I didn't bother to<br>
benchmark or fine tune as a function of the number of questions.<br>
<br>
I did not (even implicitly) implement the optimization that you<br>
suggested for O(1) disk filee modifications.<br>
<br>
--- Omer<br>
<br>
On Sun, 2012-07-08 at 10:23 +0300, Nadav Har'El wrote:<br>
> 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>
Sent from a PC running a top secret test version of Windows 97.<br>
My own blog is at <a href="http://www.zak.co.il/tddpirate/">http://www.zak.co.il/tddpirate/</a><br>
<br>
My opinions, as expressed in this E-mail message, are mine alone.<br>
They do not represent the official policy of any organization with which<br>
I may be affiliated in any way.<br>
WARNING TO SPAMMERS: at <a href="http://www.zak.co.il/spamwarning.html">http://www.zak.co.il/spamwarning.html</a><br>
<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:w1-W6cp89mEpD1mR6Xm/[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=X3oDMTJwbjQ0N3QwBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODkEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQxNzM1MjI2?act=reply&messageNum=5189">Reply <span style="font-weight: 700;">via web post</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlNWpzNWRhBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MTczNTIyNg--" style="font-weight: 700;">Start a New Topic</a>
</div>
<a href="http://groups.yahoo.com/group/hackers-il/message/5185;_ylc=X3oDMTM0ODFqaHN2BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODkEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQxNzM1MjI2BHRwY0lkAzUxODU-">Messages in this topic</a>
(<span style="font-weight: 700;">5</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=X3oDMTJmNWk3anJ1BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDE3MzUyMjY-?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=X3oDMTJlcTk1MWI2BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM0MTczNTIyNg--" 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=X3oDMTJkdjRpczBnBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzQxNzM1MjI2" 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=5189/stime=1341735226/nc1=4507179/nc2=4836045/nc3=3848641" 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 -->
--VGBmOeRkO6DXYoVm1aHQoBf6E49lJGRza2L3XTt--