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

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

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

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

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.

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

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?

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.

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

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.