On Wed, 19 Oct 2005, Ryan Leavengood wrote: > On 10/18/05, Ara.T.Howard <Ara.T.Howard / noaa.gov> wrote: >> >> a couple of observations: zach's method destroys the array at each >> iteration and is unique in this respect. to be fair a 'dup' must be added >> to his approach. you arrays are composed in a quite regular fashion which >> give the algoritm's that favour linear search a huge advantage - a random >> distribution of dups makes the task much harder. i implemented changes for >> the above and now: > > Thanks a lot for this Ara, you make some excellent points. I did think about > how the linear nature of the test array might skew the results, but I never > got around to randomizing them. I also assumed that all the algorithms > worked correctly and non-destructively. I considered adding some tests to > ensure they all returned the same result, but didn't bother. > >> also, your concept of 'big' doesn't seem that, er, big - running with >> larger numbers is also revealing - i started a process with > > I know it wasn't very big, but I figured it would be big enough to show how > the algorithms scaled. Plus I'm using my work laptop and have to get some > work done, so I can't wait all day while Ruby eats up all my CPU :) don't worry -- your tax dollars funding my testing ;-) > Like Paul, I've found this thread very enlightening, and it will make me > think twice before using a "cute" solution (though you don't always need the > highest performer all the time.) Though James' solution is pretty cute and > fast, so good job. > > Either way this thread was a very good indication of Ruby's TIMTOWTDI > nature. agreed all the way around. the final (for me) results: small: harp:~ > ruby a.rb user system total real david 5.330000 0.000000 5.330000 ( 5.350960) jeff 0.370000 0.000000 0.370000 ( 0.373027) jegII 0.320000 0.010000 0.330000 ( 0.324357) markvh 0.610000 0.000000 0.610000 ( 0.606635) martin 0.300000 0.000000 0.300000 ( 0.308640) paolo 0.540000 0.000000 0.540000 ( 0.537689) park 0.400000 0.000000 0.400000 ( 0.403531) paul 0.660000 0.000000 0.660000 ( 0.662007) robert 0.640000 0.000000 0.640000 ( 0.642736) samk1 0.410000 0.000000 0.410000 ( 0.418733) samk2 4.730000 0.000000 4.730000 ( 5.043174) simonk 1.060000 0.000000 1.060000 ( 1.052031) simons 1.150000 0.000000 1.150000 ( 1.160381) zach 0.640000 0.000000 0.640000 ( 0.641282) user system total real david 12.600000 0.000000 12.600000 ( 12.637510) jeff 0.200000 0.000000 0.200000 ( 0.203639) jegII 0.010000 0.000000 0.010000 ( 0.007662) markvh 0.880000 0.000000 0.880000 ( 0.872928) martin 0.010000 0.000000 0.010000 ( 0.007404) paolo 0.030000 0.000000 0.030000 ( 0.028461) park 0.010000 0.000000 0.010000 ( 0.009939) paul 0.020000 0.000000 0.020000 ( 0.019959) robert 0.010000 0.010000 0.020000 ( 0.015718) samk1 0.010000 0.000000 0.010000 ( 0.009769) samk2 10.050000 0.000000 10.050000 ( 10.088609) simonk 1.950000 0.000000 1.950000 ( 1.949996) simons 1.420000 0.000000 1.420000 ( 1.415801) zach 0.890000 0.000000 0.890000 ( 0.890465) big: harp:~ > ruby a.rb 424 42424 user system total real david 616.620000 0.000000 616.620000 (626.621697) jeff 10.610000 0.000000 10.610000 ( 10.635370) jegII 3.380000 0.000000 3.380000 ( 3.371940) markvh 43.970000 0.000000 43.970000 ( 44.051656) martin 3.120000 0.000000 3.120000 ( 3.122285) paolo 7.210000 0.000000 7.210000 ( 7.238185) park 4.270000 0.000000 4.270000 ( 4.291279) paul 6.700000 0.000000 6.700000 ( 6.729307) robert 7.780000 0.000000 7.780000 ( 7.779309) samk1 4.510000 0.010000 4.520000 ( 4.520682) samk2 432.290000 0.000000 432.290000 (433.597829) simonk 76.810000 0.040000 76.850000 ( 77.561346) simons 56.480000 0.000000 56.480000 ( 61.661304) zach 42.590000 0.010000 42.600000 ( 42.661407) user system total real david 1525.140000 0.010000 1525.150000 (1540.030511) jeff 19.840000 0.000000 19.840000 ( 19.871017) jegII 0.100000 0.000000 0.100000 ( 0.096985) markvh 101.610000 0.000000 101.610000 (102.777395) martin 0.090000 0.000000 0.090000 ( 0.091271) paolo 20.650000 0.610000 21.260000 ( 22.851724) park 0.130000 0.000000 0.130000 ( 0.140809) paul 0.330000 0.000000 0.330000 ( 0.333704) robert 0.210000 0.000000 0.210000 ( 0.211370) samk1 0.130000 0.000000 0.130000 ( 0.125668) samk2 1010.770000 0.000000 1010.770000 (1037.171224) simonk 178.140000 0.010000 178.150000 (178.632616) simons 123.920000 0.000000 123.920000 (124.054895) zach 97.430000 0.000000 97.430000 ( 97.559515) so __martin__ and __jegII__ effectively tie -- the diff is not significant considering my cpu did some other, but not many, things during that time it's interesting to note their solutions are an order of magnitude better that the next fastest and __5__ orders of magnitude better than the worst. defintitely a strong argument to always consider re-working algoritms before using the c compiler and extconf.rb in anger. regards. -a -- =============================================================================== | email :: ara [dot] t [dot] howard [at] noaa [dot] gov | phone :: 303.497.6469 | anything that contradicts experience and logic should be abandoned. | -- h.h. the 14th dalai lama ===============================================================================