Re: Algorithm for randomly choosing a question
Omer Zak <w1-W6cp89mEpD1mR6Xm/[email protected]> Sat, 07 Jul 2012 09:06:08 +0300
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <1341641168.13711.25.camel@c4> |
--Qws1zIkSmUuw4hCCrReuy5j1QuK8l8vH17gi6qt
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
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.
>
>
>
> You don't have to keep a list of questions, just a list of numbers
> where each number represent a question.
> A question you want to appear twice as much as any other, put it twice
> in the list.
> For a question you want to appear 100 times less then any other, use
> the algorithm you suggested.
Thanks for your interest.
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
--
Bottom posters are filthy heretics and infidels and ought to be burned
on the stake after having been tarred, feathered and having rotten eggs
thrown at their faces!
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
--Qws1zIkSmUuw4hCCrReuy5j1QuK8l8vH17gi6qt
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>On Sat, 2012-07-07 at 08:20 +0300, Ori Idan wrote:<br>
[... description of the problem was snipped ...]<br>
> My wish is to have an algorithm which requires only bounded<br>
> number of<br>
> computations of random numbers (i.e. no loop) to accomplish<br>
> the above.<br>
> Assume that N is large, so keeping lists of questions in<br>
> memory is ruled<br>
> out.<br>
> <br>
> <br>
> <br>
> You don't have to keep a list of questions, just a list of numbers<br>
> where each number represent a question.<br>
> A question you want to appear twice as much as any other, put it twice<br>
> in the list.<br>
> For a question you want to appear 100 times less then any other, use<br>
> the algorithm you suggested.<br>
<br>
Thanks for your interest.<br>
<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<br>
<br>
-- <br>
Bottom posters are filthy heretics and infidels and ought to be burned<br>
on the stake after having been tarred, feathered and having rotten eggs<br>
thrown at their faces!<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=X3oDMTJwcmJ1NTU0BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODcEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzQxNjQxMTM0?act=reply&messageNum=5187">Reply <span style="font-weight: 700;">via web post</span></a> |
<a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlbTI5MGpkBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM0MTY0MTEzNA--" style="font-weight: 700;">Start a New Topic</a>
</div>
<a href="http://groups.yahoo.com/group/hackers-il/message/5185;_ylc=X3oDMTM0b3RhNDNlBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxODcEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzQxNjQxMTM0BHRwY0lkAzUxODU-">Messages in this topic</a>
(<span style="font-weight: 700;">3</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=X3oDMTJmbnRpaHUyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzNDE2NDExMzQ-?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=X3oDMTJlbWpmMWZwBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM0MTY0MTEzNA--" 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=X3oDMTJkZmdqMjgyBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzQxNjQxMTM0" 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=5187/stime=1341641134/nc1=4507179/nc2=5758222/nc3=3848640" 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 -->
--Qws1zIkSmUuw4hCCrReuy5j1QuK8l8vH17gi6qt--