From: "Iñaki Baz Castillo" Date: 2011-06-26T02:31:36+09:00 Subject: Re: How to order a hash based on its keys? 2011/6/24 Robert Klemme : >> 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. Yes, and still I'm looking for the introduced bug :) >> Results: >> ------------------------------------------------------------------- >> server-1:     50000         0         0       0         0 >> server-2-A:         0  28488  16302  5210         0 >> server-2-B:         0    7226  12245 30529        0 >> server-2-C:         0  14286  21453 14261        0 >> server-3:            0         0         0        0 50000 >> --------------------------------------------------------------------- > > 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.  I was specifically talking about these: > > 11:     if rnd < prio = entry[0] > 106: printf "INFO: Time elapsed : %.4f seconds\n", time_elapsed = > time_end - time_start > > which are better written as > > prio = entry[0] > if rnd < prio > > time_elapsed = 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".  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. 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!  These kinds of discussions are the ones I like being around. > Everybody learns something along the way. Sure ;) Thanks a lot again. -- Iñaki Baz Castillo