Re: Algorithm for randomly choosing a question

Amit Aronovitch <[email protected]> Sun, 8 Jul 2012 00:48:33 +0300
Newsgroups	gmane.culture.hackers.israel
Message-ID	<CANFEmtd3=1zTo1GAtR8eC2oC6QgKWn5R20Jb8audJ3gJ0+DwXA@mail.gmail.com>
--f46d0444edf197226104c44457d8
Content-Type: text/plain; charset=ISO-8859-1

On Sun, Jul 8, 2012 at 12:38 AM, Amit Aronovitch <[email protected]>wrote:

>
>
> On Sun, Jul 8, 2012 at 12:28 AM, Amit Aronovitch <[email protected]>wrote:
>
>>
>> On Sat, Jul 7, 2012 at 9:06 AM, Om er Zak <w1-W6cp89mEpD1mR6Xm/[email protected]> 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.
>>> >
>>>
>>
>>
>> http://www.keithschwarz.com/darts-dice-coins/
>>
>> (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.

--f46d0444edf197226104c44457d8
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable




<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/htm=
l4/strict.dtd">
<html>
<head>
</head>







<body style=3D"background-color: #fff;">
<span style=3D"display:none">&nbsp;</span>

<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id=3D"ygrp-mlmsg" style=3D"position:relative;">
  <div id=3D"ygrp-msg" style=3D"z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->

    <div id=3D"ygrp-text" >
=20=20=20=20=20=20
=20=20=20=20=20=20
      <p><div dir=3D"ltr"><br><br><div class=3D"gmail_quote">On Sun, Jul 8,=
 2012 at 12:38 AM, Amit Aronovitch <span dir=3D"ltr">&lt;<a href=3D"mailto:=
[email protected]" target=3D"_blank">[email protected]</a>&gt;</span>=
 wrote:<br><blockquote class=3D"gmail_quote" style=3D"border-left:1px #ccc =
solid;">
<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div class=3D"im">On Su=
n, Jul 8, 2012 at 12:28 AM, Amit Aronovitch <span dir=3D"ltr">&lt;<a href=
=3D"mailto:[email protected]" target=3D"_blank">[email protected]</a>=
&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"border-left:1px #ccc solid;">

<div dir=3D"ltr"><br><div><div>On Sat, Jul 7, 2012 at 9:06 AM, Om er Zak <s=
pan dir=3D"ltr">&lt;<a href=3D"mailto:w1-W6cp89mEpD1mR6Xm/[email protected]" target=3D"_blank">w1@za=
k.co.il</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D=
"border-left:1px #ccc solid;">



On Sat, 2012-07-07 at 08:20 &#43;0300, Ori Idan wrote:<br>
[... description of the problem was snipped ...]<br>
<div>&gt; =A0 =A0 =A0 =A0 My wish is to have an algorithm which requires on=
ly bounded<br>
&gt; =A0 =A0 =A0 =A0 number of<br>
&gt; =A0 =A0 =A0 =A0 computations of random numbers (i.e. no loop) to accom=
plish<br>
&gt; =A0 =A0 =A0 =A0 the above.<br>
&gt; =A0 =A0 =A0 =A0 Assume that N is large, so keeping lists of questions =
in<br>
&gt; =A0 =A0 =A0 =A0 memory is ruled<br>
&gt; =A0 =A0 =A0 =A0 out.<br>
&gt;<br>
</div></blockquote></div><div><br><br><a href=3D"http://www.keithschwarz.co=
m/darts-dice-coins/" target=3D"_blank">http://www.keithschwarz.com/darts-di=
ce-coins/</a> <br></div><br>(rather long, but nicely written and not hard t=
o follow)<br>


=A0</div></div></blockquote></div><div><br>Whoops, missed the &quot;N is la=
rge&quot; thing (so O(n) memory might be too high, even if you just keep we=
ights...). Still, a nice read to share.<br>I guess there&#39;s no escape fr=
om trading some memory for the time improvement...<br>
=A0</div></div></div></blockquote><div>sent before completed (whoops again)=
...<br><br>I ment: you do not have to store weights of ALL the questions, j=
ust for the questions the user had seen (and you have to store a list of th=
ese anyway). Since you know how many the user had already chosen, and the s=
um 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 la=
rger). If the larger is chosen, choose uniformly. If the smaller (stored) s=
et is selected, choose using the alias method or some simpler alternative.<=
br>
<br></div></div><br></div>
</p>

    </div>
=20=20=20=20=20

    <!--~-|**|PrettyHtmlStart|**|-~-->
    <div style=3D"color: #fff; height: 0;">__._,_.___</div>

=20=20=20=20=20=20=20=20
=20=20
=20=20=20
    <div id=3D"ygrp-actbar" style=3D"clear: both; margin-bottom: 10px; whit=
e-space: nowrap; color: #666; padding-top: 15px;">
      <div>
        <a href=3D"mailto:[email protected]?subject=3DRe%3A%20%5Bhackers=
-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question" style=3D"mar=
gin-right: 0; padding-right: 0;">
	  Reply to <span style=3D"font-weight: 700;">sender</span></a> |
        <a href=3D"mailto:[email protected]?subject=3DRe%3A%20%5Bh=
ackers-il%5D%20Algorithm%20for%20randomly%20choosing%20a%20question">
	  Reply to <span style=3D"font-weight: 700;">group</span></a> |
        	  <a href=3D"http://groups.yahoo.com/group/hackers-il/post;_ylc=3D=
X3oDMTJwcnE4MG9rBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY=
0BG1zZ0lkAzUxOTEEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQyMDQ0MDU4?act=3Dreply&m=
essageNum=3D5191">Reply <span style=3D"font-weight: 700;">via web post</spa=
n></a> |
            	<a href=3D"http://groups.yahoo.com/group/hackers-il/post;_ylc=
=3DX3oDMTJldXFrbDl0BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2=
NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MjA0NDA1OA--" style=3D"font-weight:=
 700;">Start a New Topic</a>
      </div>

                <a href=3D"http://groups.yahoo.com/group/hackers-il/message=
/5185;_ylc=3DX3oDMTM0YnM2cWkzBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZA=
MxNzA1MDA2NzY0BG1zZ0lkAzUxOTEEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQyMDQ0MDU4B=
HRwY0lkAzUxODU-">Messages in this topic</a>
          (<span style=3D"font-weight: 700;">7</span>)
          </div>=20
<!------- Start Nav Bar ------>

<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-vital" style=3D"background-color: #e0ecee; font-family: Ver=
dana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
      <span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-tran=
sform: uppercase; ">Recent Activity:</span>

    <ul style=3D"list-style-type: none; margin: 0; padding: 0; display: inl=
ine;">
            <li style=3D"border-right: 1px solid #000; font-weight: 700; di=
splay: inline; padding: 0 5px; margin-left: 0;">
      <span class=3D"cat"><a href=3D"http://groups.yahoo.com/group/hackers-=
il/members;_ylc=3DX3oDMTJmY3IzbWdiBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc=
3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDIwNDQwNTg-?o=3D6" =
style=3D"text-decoration: none;">New Members</a></span>
      <span class=3D"ct" style=3D"color: #ff7900;">1</span>
    </li>
                                              </ul>
=20=20=20=20
  <div style=3D"clear: both; padding-top: 2px; color: #1e66ae;">
    <a href=3D"http://groups.yahoo.com/group/hackers-il;_ylc=3DX3oDMTJlNTRn=
OGU1BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGw=
Ec2xrA3ZnaHAEc3RpbWUDMTM0MjA0NDA1OA--" style=3D"text-decoration: none;">Vis=
it Your Group</a>
  </div>
</div>

=20=20
<div id=3D"ft" style=3D"font-family: Arial; font-size: 11px; margin-top: 5p=
x; padding: 0 2px 0 0; clear: both;">
  <a href=3D"http://groups.yahoo.com/;_ylc=3DX3oDMTJkNTA0bzZ0BF9TAzk3NDc2NT=
kwBGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZ=
QMxMzQyMDQ0MDU5" style=3D"float: left;"><img src=3D"http://l.yimg.com/a/i/u=
s/yg/logo/us.gif" height=3D"15" width=3D"137" alt=3D"Yahoo! Groups" style=
=3D"border: 0;"/></a>
  <div style=3D"color: #747575; float: right;">Switch to: <a href=3D"mailto=
:[email protected]?subject=3DChange Delivery Format: T=
raditional" style=3D"text-decoration: none;">Text-Only</a>, <a href=3D"mail=
to:[email protected]?subject=3DEmail Delivery: Digest" clas=
s=3D"margin-rt" style=3D"text-decoration: none;">Daily Digest</a> &bull; <a=
 href=3D"mailto:[email protected]?subject=3DUnsubscrib=
e" style=3D"text-decoration: none;">Unsubscribe</a> &bull; <a href=3D"http:=
//docs.yahoo.com/info/terms/" style=3D"text-decoration: none;">Terms of Use=
</a></div>
</div>

<!-- |**|end egp html banner|**| -->

  </div> <!-- ygrp-msg -->

  <!-- Sponsor -->
  <!-- |**|begin egp html banner|**| -->
  <div id=3D"ygrp-sponsor" style=3D"width:160px; float:right; clear:none; m=
argin:0 0 25px 0; background: #fff;">

<!-- Start Recommendations -->
<div id=3D"ygrp-reco">
     </div>
<!-- End Recommendations -->



  </div>   <!-- |**|end egp html banner|**| -->

  <div style=3D"clear:both; color: #FFF; font-size:1px;">.</div>
</div>

  <img src=3D"http://geo.yahoo.com/serv?s=3D97359714/grpId=3D1857332/grpspI=
d=3D1705006764/msgId=3D5191/stime=3D1342044058/nc1=3D3848641/nc2=3D5741392/=
nc3=3D4507179" width=3D"1" height=3D"1"> <br>

<div style=3D"color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->

</body>

<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
  <style type=3D"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;
  }
=20=20
  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.fi=
le-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;
  }=20

  #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;=20
  }=20
  -->
  </style>
</head>

<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->


--f46d0444edf197226104c44457d8--