View mode: basic / threaded / horizontal-split · Log in · Help
February 14, 2009
Re: random cover of a range
Christopher Wright wrote:
> bearophile wrote:
>> Andrei Alexandrescu:
>>> Your handwaving ain't much better than my memory. Hey, either 
>>> somebody goes through the math over here or we can give up on the 
>>> whole thing and use O(n) storage for the blessed thing.<
>>
>> We can implement both, and we can look what's better in practical 
>> situations.
> 
> Agreed. Worst-case quadratic can perform much better in many 
> circumstances, and the proposed algorithm is tunable.

I think if we want to look like professionals we're not going to do 
that. History of computing is full of embarrassing quadratic algorithms 
failing miserably when advances in storage capacity or simply data set 
growth within the original program showed their pernicious tendencies. I 
have authored such a program when I was a student :o).


Andrei
February 14, 2009
Re: random cover of a range
bearophile wrote:
> Christopher Wright:
>> Agreed. Worst-case quadratic can perform much better in many 
>> circumstances, and the proposed algorithm is tunable.
> 
> I think it's not quadratic :-) (See the answer by Bill B.)

I don't think that answer answers the question.

Andrei
February 14, 2009
Re: random cover of a range
Bill Baxter wrote:
> I found a pdf[1] that has a summary of the probabilities associated
> with finding empty slots in the context of hashing.
> If I'm reading it right, if you have a load factor (fraction full) of
> f, then it's expected it will take you 1/(1-f) trials to get an empty
> if you just continue picking randomly one after the other.
> 
> --bb
> [1] http://www.cse.unsw.edu.au/~cs2011/lect/2711_HashProbe-4.pdf

Thank you, that's exactly the explanation I was looking for.

Andrei
February 14, 2009
Re: random cover of a range
Bill Baxter wrote:
> On Sat, Feb 14, 2009 at 2:20 PM, Andrei Alexandrescu
> The probability of *not* getting the number after t tries is
> (1-1/n)^t, so it's just a pure decaying exponential, the chance of
> getting it after t tries should be 1 minus that.  The average number
> of tries is going to be some kind of integral of that curve, and an
> integral of an exponential is still an exponential, so it seems
> unlikely to me that your memory was correct on this one.

Thanks for finding the pdf with the calculation. It looks like this old 
brain can still remember something :o).

>> Now, assuming the above is true, say we decide to do the linear search for a
>> fraction f of the n elements in the array.
> 
> Maybe you were switching subjects (to your algorithm?) here, but just
> to be clear, Bearophile didn't say anything about doing a linear
> search.  His first phase is just to do repeated dart-throwing trials
> till an empty is found.

I meant random trials. What I was saying was that it takes linear time 
to hit an element.

>> . The average number of steps will
>> be:
>>
>> S = n * (1/n + 1/(n - 1) + 1/(n - 2) + ... + 1/(n - fn))
>>
>> So we're looking for the harmonic series that does not start from 1, but
>> instead starts from its fn'th term (you drop the first (1-f)n terms). Does
>> it converge? (I don't know.)
> 
> In the limit of what?  You seem to be asking if a finite series converges.

S is the average number of steps taken to finishing the task. I'm 
looking for a bound on that number of steps. With the clear Saturday 
morning outlook, it seems that it's in any case better than O(n log n), 
which means that bearophile was right - it's not quadratic. But I've 
been wrong a number of times on this because I keep on trying to 
convince someone else to do the math, so someone please confirm :o).

Andrei
February 14, 2009
Re: random cover of a range
bearophile wrote:
> Jason House:
>> Believe it or not, that's an unreasonable requirement. IIRC, most RNG's have periods such as 2^32. You can't get more permutations than that. Somewhere in the ballpark of 17 elements, your requurement becones impossible to meet without a highly specialized RNG. I hope someone can prove me wrong about that!<
> 
> Mersenne Twister has a period much longer, if you want.
> For even longer permutations you have to generate them in a different way.
> 
> Bye,
> bearophile

I don't think the period of the generator is particularly important.
The problem is, it'd be pretty hard to get the required number of random 
seed bits.
February 14, 2009
OT -- Re: random cover of a range
Hello bearophile,

> (And my name is bearophile, thank you).
> 
> Bye,
> bearophile


I'm curious to know what "bearophile" means?


At first, I thought this alias was innocent enough, but after visiting your 
much promoted site (promoted in the D community), I'm not so sure what to 
think.  I almost blanched at some of the content and greatly regretted having 
visited it.


If you don't know what I'm talking about, then I ask you consider carefully 
the implications of some of your the creature fantasies that you blog about. 
I'm surprised nobody else has complained.  Or maybe I should not be so surprised 
considering how politically incorrect it is to challenge any ideology (or 
fantasy, for that matter) even if it be so morally bankrupt so as to be considered 
extreme indeceny and deviance by any number of different cultural standards. 
The implications there as graphically displayed, while not quite clear, 
are in the direction of bestiality... and if not, are confused enough as 
to be presumptiously indifferent to any ethical question about the horrible 
nature of it.


You are not doubt quite bright, as your other interests and participation 
in D design have made clearly evident.  But I just can't believe such content 
is so closely linked to this group and the D design process.  I should think 
you would be embarrassed.  I know I am to have been subjected to it.


If you're shocked that I'm confronting you openly on this, the reason lies 
squarely in the fact that you are boldly and unashamedly displaying the material 
in a site that is linked here multiple times; and I believe such boldness 
warrants the same measure of confrontation in return.  I hope you will change 
your mind about the material.  I'd wish both your mind on the matter and 
the material would completely change, but I don't have the right to request 
much more than that you disassociate it completely with your dealings with 
D, so that those it concerns  don't have to be involved in the particulars 
of your fantasies whenever you link your site here.


Of course, it is equally people's right here to support you in your freedom 
to display such things (while providing the links here).  If they do, however, 
it speaks volumes about peoples general apathy to the downward spiral of 
society where increasingly indecent content is seen as normal and harmless. 
This is a great shame, and I'd be sorry to see that people don't care anymore.


For those that see this as flamebait, I request that you do not respond. 
I just felt somebody had to say something about this.  If this is perceived 
to be libelous, I ask that you consider carefully how damaging your content 
is to others, and the feelings it might engender in its viewers.  Thus, you 
should recognize that this post merely elucidates on what's already evident.


-JJR
February 14, 2009
Re: OT -- Re: random cover of a range
I had to think some seconds about your post, but now I think it's irony. 
I'm not quite sure, though. Could you tell me the answer?
February 14, 2009
Re: OT -- Re: random cover of a range
On Sat, Feb 14, 2009 at 2:10 PM, John Reimer <terminal.node@gmail.com> wrote:
> Hello bearophile,
>
>> (And my name is bearophile, thank you).
>>
>> Bye,
>> bearophile
>
>
> I'm curious to know what "bearophile" means?
>
>
> At first, I thought this alias was innocent enough, but after visiting your
> much promoted site (promoted in the D community), I'm not so sure what to
> think.  I almost blanched at some of the content and greatly regretted
> having visited it.
>
>
> If you don't know what I'm talking about, then I ask you consider carefully
> the implications of some of your the creature fantasies that you blog about.
> I'm surprised nobody else has complained.  Or maybe I should not be so
> surprised considering how politically incorrect it is to challenge any
> ideology (or fantasy, for that matter) even if it be so morally bankrupt so
> as to be considered extreme indeceny and deviance by any number of different
> cultural standards. The implications there as graphically displayed, while
> not quite clear, are in the direction of bestiality... and if not, are
> confused enough as to be presumptiously indifferent to any ethical question
> about the horrible nature of it.
>
>
> You are not doubt quite bright, as your other interests and participation in
> D design have made clearly evident.  But I just can't believe such content
> is so closely linked to this group and the D design process.  I should think
> you would be embarrassed.  I know I am to have been subjected to it.
>
>
> If you're shocked that I'm confronting you openly on this, the reason lies
> squarely in the fact that you are boldly and unashamedly displaying the
> material in a site that is linked here multiple times; and I believe such
> boldness warrants the same measure of confrontation in return.  I hope you
> will change your mind about the material.  I'd wish both your mind on the
> matter and the material would completely change, but I don't have the right
> to request much more than that you disassociate it completely with your
> dealings with D, so that those it concerns  don't have to be involved in the
> particulars of your fantasies whenever you link your site here.
>
>
> Of course, it is equally people's right here to support you in your freedom
> to display such things (while providing the links here).  If they do,
> however, it speaks volumes about peoples general apathy to the downward
> spiral of society where increasingly indecent content is seen as normal and
> harmless. This is a great shame, and I'd be sorry to see that people don't
> care anymore.
>
>
> For those that see this as flamebait, I request that you do not respond. I
> just felt somebody had to say something about this.  If this is perceived to
> be libelous, I ask that you consider carefully how damaging your content is
> to others, and the feelings it might engender in its viewers.  Thus, you
> should recognize that this post merely elucidates on what's already evident.

He's what's called a furry.  Welcome to the internet, I suppose you've
been living under a rock.
February 14, 2009
Re: OT -- Re: random cover of a range
On Sat, Feb 14, 2009 at 2:54 PM, Jarrett Billingsley
<jarrett.billingsley@gmail.com> wrote:
>
> He's what's called a furry.  Welcome to the internet, I suppose you've
> been living under a rock.
>

This isn't meant to be an attack, but a snarky observation :P
February 14, 2009
Re: OT -- Re: random cover of a range
John Reimer wrote:
> Hello bearophile,
>
>> (And my name is bearophile, thank you).
>>
>> Bye,
>> bearophile
>
>
> I'm curious to know what "bearophile" means?
>
>
> At first, I thought this alias was innocent enough, but after visiting
> your much promoted site (promoted in the D community), I'm not so sure
> what to think. I almost blanched at some of the content and greatly
> regretted having visited it.
>
>
> If you don't know what I'm talking about, then I ask you consider
> carefully the implications of some of your the creature fantasies that
> you blog about. I'm surprised nobody else has complained. Or maybe I
> should not be so surprised considering how politically incorrect it is
> to challenge any ideology (or fantasy, for that matter) even if it be so
> morally bankrupt so as to be considered extreme indeceny and deviance by
> any number of different cultural standards. The implications there as
> graphically displayed, while not quite clear, are in the direction of
> bestiality... and if not, are confused enough as to be presumptiously
> indifferent to any ethical question about the horrible nature of it.
>
>
> You are not doubt quite bright, as your other interests and
> participation in D design have made clearly evident. But I just can't
> believe such content is so closely linked to this group and the D design
> process. I should think you would be embarrassed. I know I am to have
> been subjected to it.
>
>
> If you're shocked that I'm confronting you openly on this, the reason
> lies squarely in the fact that you are boldly and unashamedly displaying
> the material in a site that is linked here multiple times; and I believe
> such boldness warrants the same measure of confrontation in return. I
> hope you will change your mind about the material. I'd wish both your
> mind on the matter and the material would completely change, but I don't
> have the right to request much more than that you disassociate it
> completely with your dealings with D, so that those it concerns don't
> have to be involved in the particulars of your fantasies whenever you
> link your site here.
>
>
> Of course, it is equally people's right here to support you in your
> freedom to display such things (while providing the links here). If they
> do, however, it speaks volumes about peoples general apathy to the
> downward spiral of society where increasingly indecent content is seen
> as normal and harmless. This is a great shame, and I'd be sorry to see
> that people don't care anymore.
>
>
> For those that see this as flamebait, I request that you do not respond.
> I just felt somebody had to say something about this. If this is
> perceived to be libelous, I ask that you consider carefully how damaging
> your content is to others, and the feelings it might engender in its
> viewers. Thus, you should recognize that this post merely elucidates on
> what's already evident.
>
>
> -JJR
>
>

What content are you refering to? I don't know Italian, but I didn't see 
anything like what you imply in English.
1 2 3 4 5 6 7 8 9
Top | Discussion index | About this forum | D home