From: brabuhr@... Date: 2009-11-26T04:34:04+09:00 Subject: Re: Distinct Sets (#225) On Wed, Nov 25, 2009 at 11:59 AM, lith wrote: > Here is a graph-based approach: > http://pastie.org/714759 Running the small approximative benchmark: > fgrep name /proc/cpuinfo model name : Intel(R) Pentium(R) M processor 1.60GHz > uname -a Linux eXist 2.6.31-14-generic #48-Ubuntu SMP Fri Oct 16 14:04:26 UTC 2009 i686 GNU/Linux > ruby1.8 -v 711915.rb 714759.rb ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux] user system total real elements * sets: 1 * 5 => 1 * 1 0.000000 0.000000 0.000000 ( 0.003731) elements * sets: 1 * 5 => 2 * 1 0.000000 0.000000 0.000000 ( 0.002467) elements * sets: 2 * 5 => 3 * 1 0.000000 0.000000 0.000000 ( 0.003154) elements * sets: 2 * 5 => 4 * 1 0.010000 0.000000 0.010000 ( 0.004540) elements * sets: 2 * 5 => 5 * 1 0.000000 0.000000 0.000000 ( 0.005251) elements * sets: 3 * 5 => 6 * 1 0.010000 0.000000 0.010000 ( 0.004601) elements * sets: 3 * 5 => 7 * 1 0.000000 0.000000 0.000000 ( 0.006505) elements * sets: 3 * 5 => 8 * 1 0.000000 0.010000 0.010000 ( 0.008302) elements * sets: 4 * 5 => 9 * 1 0.000000 0.000000 0.000000 ( 0.008121) elements * sets: 4 * 5 => 10 * 1 0.010000 0.010000 0.020000 ( 0.008174) elements * sets: 18 * 255 => 1 * 51 0.070000 0.000000 0.070000 ( 0.068440) elements * sets: 35 * 255 => 2 * 51 0.120000 0.020000 0.140000 ( 0.145098) elements * sets: 52 * 255 => 3 * 51 0.220000 0.030000 0.250000 ( 0.253006) elements * sets: 69 * 255 => 4 * 51 0.310000 0.060000 0.370000 ( 0.375845) elements * sets: 86 * 255 => 5 * 51 0.450000 0.070000 0.520000 ( 0.516071) elements * sets: 103 * 255 => 6 * 51 0.580000 0.090000 0.670000 ( 0.680203) elements * sets: 120 * 255 => 7 * 51 0.740000 0.130000 0.870000 ( 0.864627) elements * sets: 137 * 255 => 8 * 51 0.920000 0.160000 1.080000 ( 1.082008) elements * sets: 154 * 255 => 9 * 51 1.190000 0.130000 1.320000 ( 1.319013) elements * sets: 171 * 255 => 10 * 51 1.380000 0.190000 1.570000 ( 1.569024) elements * sets: 34 * 505 => 1 * 101 0.140000 0.010000 0.150000 ( 0.151603) elements * sets: 68 * 505 => 2 * 101 0.260000 0.060000 0.320000 ( 0.336318) elements * sets: 102 * 505 => 3 * 101 0.490000 0.060000 0.550000 ( 0.537813) elements * sets: 135 * 505 => 4 * 101 0.700000 0.090000 0.790000 ( 0.802585) elements * sets: 169 * 505 => 5 * 101 0.950000 0.160000 1.110000 ( 1.106535) elements * sets: 203 * 505 => 6 * 101 1.240000 0.220000 1.460000 ( 1.456670) elements * sets: 236 * 505 => 7 * 101 1.590000 0.260000 1.850000 ( 1.850735) elements * sets: 270 * 505 => 8 * 101 2.030000 0.260000 2.290000 ( 2.294973) elements * sets: 304 * 505 => 9 * 101 2.350000 0.430000 2.780000 ( 2.784864) elements * sets: 337 * 505 => 10 * 101 2.860000 0.470000 3.330000 ( 3.335518) And a little one-off benchmark (sets of random integers): per sets set user system total real 10, 1 0.000000 0.000000 0.000000 ( 0.000776) 10, 10 0.000000 0.000000 0.000000 ( 0.005667) 10, 100 0.350000 0.030000 0.380000 ( 0.384304) 10, 1000 Timeout::Error - execution expired (> 3 minutes) user system total real 1, 10 0.000000 0.000000 0.000000 ( 0.000743) 10, 10 0.000000 0.000000 0.000000 ( 0.009329) 100, 10 0.040000 0.010000 0.050000 ( 0.056932) 1000, 10 5.180000 0.070000 5.250000 ( 7.455180) 10000, 10 8.460000 0.510000 8.970000 ( 12.744708) 100000, 10 Timeout::Error - execution expired (> 3 minutes) user system total real 1, 1 0.010000 0.000000 0.010000 ( 0.003573) 10, 10 0.010000 0.000000 0.010000 ( 0.008709) 100, 100 28.750000 0.350000 29.100000 ( 42.588412) 1000, 1000 Timeout::Error - execution expired (> 3 minutes)