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

2011/6/24 Robert Klemme <[e-mail]>:
>> 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. =C2=A0You probably
> accidentally added another issue.

Yes, and still I'm looking for the introduced bug :)



>> Results:
>> -------------------------------------------------------------------
>> server-1: =C2=A0 =C2=A0 50000 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0
>> server-2-A: =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A028488 =C2=A016302 =C2=A0=
5210 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0
>> server-2-B: =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A0 =C2=A07226 =C2=A012245 =
30529 =C2=A0 =C2=A0 =C2=A0 =C2=A00
>> server-2-C: =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A014286 =C2=A021453 14261 =
=C2=A0 =C2=A0 =C2=A0 =C2=A00
>> server-3: =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A00 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 =C2=A0 =C2=A0 =C2=A0 =C2=A00 500=
00
>> ---------------------------------------------------------------------
>
> Would that be sufficient statistical enough for you?
> https://gist.github.com/1040631

Yes :)

However, I've compared efficience (with 100.000 iterations):

Mine:
--------
INFO: Time elapsed     : 0.9837 seconds
INFO: Resolution speed : 101656.6751 resolutions/second

Yours:
---------
INFO: Time elapsed     : 2.5718 seconds
INFO: Resolution speed : 38883.8211 resolutions/second

:)

Of course my code is much more ugly.



>> 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.

Yes, but it's just an Array allocation (using [] rather than
Array.new, which is much faster).





> My remark has nothing to do whatsoever with avoiding double access to
> a Hash. =C2=A0I was specifically talking about these:
>
> 11: =C2=A0 =C2=A0 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.

Right.




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

DNS SRV are explained in RFC 2782, and entries with weight 0 don't
mean "do not use", but "rarely select it at the first choice":

http://tools.ietf.org/html/rfc2782:


   Priority
        The priority of this target host.  A client MUST attempt to
        contact the target host with the lowest-numbered priority it can
        reach; target hosts with the same priority SHOULD be tried in an
        order defined by the weight field.  The range is 0-65535.  This
        is a 16 bit unsigned integer in network byte order.

   Weight
        A server selection mechanism.  The weight field specifies a
        relative weight for entries with the same priority. Larger
        weights SHOULD be given a proportionately higher probability of
        being selected. The range of this number is 0-65535.  This is a
        16 bit unsigned integer in network byte order.  Domain
        administrators SHOULD use Weight 0 when there isn't any server
        selection to do, to make the RR easier to read for humans (less
        noisy).  In the presence of records containing weights greater
        than 0, records with weight 0 should have a very small chance of
        being selected.

        In the absence of a protocol whose specification calls for the
        use of other weighting information, a client arranges the SRV
        RRs of the same Priority in the order in which target hosts,
        specified by the SRV RRs, will be contacted. The following
        algorithm SHOULD be used to order the SRV RRs of the same
        priority:

        To select a target to be contacted next, arrange all SRV RRs
        (that have not been ordered yet) in any order, except that all
        those with weight 0 are placed at the beginning of the list.

        Compute the sum of the weights of those RRs, and with each RR
        associate the running sum in the selected order. Then choose a
        uniform random number between 0 and the sum computed
        (inclusive), and select the RR whose running sum value is the
        first in the selected order which is greater than or equal to
        the random number selected. The target host specified in the
        selected SRV RR is the next one to be contacted by the client.
        Remove this SRV RR from the set of the unordered SRV RRs and
        apply the described algorithm to the unordered SRV RRs to select
        the next target host.  Continue the ordering process until there
        are no unordered SRV RRs.  This process is repeated for each
        Priority.


Note also that the selection mechanism is detalied in the last paragraph.



>> Really thanks a lot for your interest. It's very helpful.
>
> Good! =C2=A0These kinds of discussions are the ones I like being around.
> Everybody learns something along the way.

Sure ;)

Thanks a lot again.

--=20
I=C3=B1aki Baz Castillo
<[e-mail]>