Re: How to order a hash based on its keys?

On Thu, Jun 23, 2011 at 6:42 PM, I=F1aki Baz Castillo <[e-mail]> wrote=
:
> 2011/6/23 Robert Klemme <[e-mail]>:
>> I'd also not use recursion in srv_entries_randomize() - a loop is
>> usually more efficient.
>
> I was not able to do it with a loop, neither writing the algorithm in
> a paper, I always got bad statistical results.

That was certainly not an effect of the recursion.  You probably
accidentally added another issue.

> Are you sure sure that
> your code generates statistical results? for example, with my example
> data:
>
> priorities =3D {
> =A01 =3D> [[0, :"server-1"]],
> =A02 =3D> [[16, :"server-2-A"], [4, :"server-2-B"], [8, :"server-2-C"]],
> =A04 =3D> [[50, :"server-3"]]
> }
>
> I get there correct results (columns mean position from 1 to 5):
>
> Iterating 50000 times...
>
> Results:
> -------------------------------------------------------------------
> server-1: =A0 =A0 50000 =A0 =A0 =A0 =A0 0 =A0 =A0 =A0 =A0 0 =A0 =A0 =A0 0=
 =A0 =A0 =A0 =A0 0
> server-2-A: =A0 =A0 =A0 =A0 0 =A028488 =A016302 =A05210 =A0 =A0 =A0 =A0 0
> server-2-B: =A0 =A0 =A0 =A0 0 =A0 =A07226 =A012245 30529 =A0 =A0 =A0 =A00
> server-2-C: =A0 =A0 =A0 =A0 0 =A014286 =A021453 14261 =A0 =A0 =A0 =A00
> server-3: =A0 =A0 =A0 =A0 =A0 =A00 =A0 =A0 =A0 =A0 0 =A0 =A0 =A0 =A0 0 =
=A0 =A0 =A0 =A00 50000
> ---------------------------------------------------------------------

Would that be sufficient statistical enough for you?
https://gist.github.com/1040631

>> =A0And btw. you calculate the total weight every
>> time the method is invoked as sum of all entries while I maintain the
>> @total and adjust it only for every insertion and removal.
>
> Right. I'm trying to improve that. However take into account that my
> code does not need to create an instance. Instead it will be a class
> method (or a module method like DNS::srv_randomize), so I cannot use
> attributes (or I should not).

Well, that's not exactly true: your code creates an Array (stored in
ordered_targets) so you could as well create another object.

> But you are right, I must get removing the recursion. If you can prove
> me that your code gets same results for 10000 iterations with same
> input data I will adapt my code :)

see above

>>=A0You also seem to have the habit of placing
>> assignments in method argument lists or control flow statements. =A0This
>> makes code harder to read and is really only needed in case of loops,
>> e.g.
>>
>> while (str =3D io.gets)
>> =A0printf "We have read: %p\n", str
>> end
>
> Right, in fact I did it due to performance reasons, to avoid double
> access to the same element of a hash, but I've realized that depending
> on the case, it's just more efficient to perform double access rather
> than generating a new variable.

My remark has nothing to do whatsoever with avoiding double access to
a Hash.  I was specifically talking about these:

11:     if rnd < prio =3D entry[0]
106: printf "INFO: Time elapsed : %.4f seconds\n", time_elapsed =3D
time_end - time_start

which are better written as

prio =3D entry[0]
if rnd < prio

time_elapsed =3D time_end - time_start
printf "INFO: Time elapsed : %.4f seconds\n", time_elapsed

Much more readable and no performance difference other than maybe one
more access to a local variable which is negligible IMHO.

>> There is one thing I don't understand in your code: you have two
>> randomizations in there: in line 8 there is rand() similar to what I
>> have done and in line 34 there is shuffle. =A0Why do you do that? =A0Is
>> there a requirement that hasn't been mentioned yet?
>
> You are right, sorry. If a SRV record has weight 0, there should be no
> chance it to be the chosen first (before other records with same
> priority and weight greater than 0). So what I do is remove SRV
> records with same priority and weight 0 and then make a simple shuffle
> with them, adding the results in the last position. For example:
>
> =A0- priority 1, weight 10, domain "server1", port 5060
> =A0- priority 1, weight 0, domain "server2", port 5060
> =A0- priority 1, weight 0, domain "server3", port 5060
>
> In this case, records 2 and 3 should always be chosen after record 1
> (which has weight > 0). The order of records with weight 0 must be
> random.

Weight 0 generally means "do not use".  Basically you change the
algorithm to also include items whose weight is 0.  I am not sure I
would add that complexity.  If someone uses weight 0 then he may
actually do that on purpose.  If not then it's a bug and should be
flagged accordingly (e.g. by raising an exception).  Also: this will
also change weight of all other elements, because the probabilities
are skewed.  I'd rather provide proper weights as inputs and avoid
illegal weights.

> Really thanks a lot for your interest. It's very helpful.

Good!  These kinds of discussions are the ones I like being around.
Everybody learns something along the way.

Kind regards

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/