Lionel Bouton wrote:
> Bill Kelly wrote:
>>
>> From: "Lionel Bouton" <lionel-subscription / bouton.name>
>>>
>>> Here's a 157_benchmark_2.rb which benchs on several point 
>>> distributions (square, disk, circle and gaussian) and my code 
>>> adapted to the benchmark (the convex hull was done outside of 
>>> encircle so it wasn't active for the benchmark).
>>
>> Neat!  :)
>
> Oups : the 2D Gaussian was the same as the circle one (stupid me)... 
> The gradient walking couldn't possibly be so slow on such a 
> distribution :-)
>
> I updated my submission with :
> - a new heuristic for the initial step,
> - an optimized step ratio for the gradient algorithm,
> - a bug fix (it didn't run out of the benchmark).
>
> Lionel

Note that if you filter the points with the convex hull, Justin's 
algorithm becomes competitive with the gradient walking with roughly the 
same performance profile:

-- Random on disk --
             user     system      total        real
FRANK   36.730000   0.040000  36.770000 ( 37.330030)
DOUG     6.570000   0.010000   6.580000 (  6.680385)
PHILIPP  5.290000   0.000000   5.290000 (  5.377509)
JUSTIN   1.090000   0.010000   1.100000 (  1.107219)
LIONEL   0.900000   0.010000   0.910000 (  0.915325)
BILL     0.610000   0.000000   0.610000 (  0.622287)
-- Random on square --
             user     system      total        real
FRANK   35.420000   0.030000  35.450000 ( 36.056951)
DOUG     6.090000   0.010000   6.100000 (  6.147446)
PHILIPP  2.720000   0.000000   2.720000 (  2.766508)
JUSTIN   1.060000   0.000000   1.060000 (  1.081301)
LIONEL   1.810000   0.010000   1.820000 (  1.857297)
BILL     0.540000   0.000000   0.540000 (  0.536318)
-- 2D Gaussian --
             user     system      total        real
FRANK   36.370000   0.050000  36.420000 ( 37.079492)
DOUG     4.730000   0.000000   4.730000 (  4.816418)
PHILIPP  3.000000   0.010000   3.010000 (  3.036339)
JUSTIN   1.270000   0.000000   1.270000 (  1.279535)
LIONEL   0.810000   0.010000   0.820000 (  0.828373)
BILL     0.540000   0.000000   0.540000 (  0.544507)
-- Random on circle --
             user     system      total        real
FRANK   36.540000   0.030000  36.570000 ( 37.410887)
DOUG     0.260000   0.000000   0.260000 (  0.255157)
PHILIPP  0.390000   0.000000   0.390000 (  0.395307)
JUSTIN  11.350000   0.010000  11.360000 ( 11.568574)
LIONEL  12.730000   0.010000  12.740000 ( 13.040802)
BILL     0.170000   0.000000   0.170000 (  0.166975)


Lionel