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