From: Robert Klemme Date: 2005-08-07T22:26:09+09:00 Subject: Re: algorithm help ------=_NextPart_000_0034_01C59B63.A8F6EEB0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=response Content-Transfer-Encoding: 8bit Simon Kr�ger wrote: >> To put some figures in here, I did a bit of benchmarking and indeed >> the bitset version is quite slooooouw: >> >> $ ruby ranges-2.rb >> user system total real >> bitset 37.734000 0.000000 37.734000 ( 38.354000) >> inject-range 0.313000 0.000000 0.313000 ( 0.318000) >> inject-array 0.156000 0.000000 0.156000 ( 0.153000) >> inject-array-2 0.140000 0.000000 0.140000 ( 0.140000) >> inject-array-map 0.204000 0.000000 0.204000 ( 0.210000) >> >> (Code attached) >> >> Anyway, it was fun playing around with this. :-) >> >> Kind regards >> >> robert > > Nice one, > > now we are getting some hard numbers to play with. > > i added a larger range 1000..5000 to the test set which should come > closer to ara's problem at hand. > > NUMBERS = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41] + > (1000..5000).to_a + [6789, 6790, 9998, 9999] > > I get the following numbers: > > user system total real > bitset 79.047000 0.094000 79.141000 ( 80.407000) > inject-range 41.609000 0.328000 41.937000 ( 43.000000) > inject-array 17.219000 0.047000 17.266000 ( 17.296000) > inject-array-2 17.687000 0.031000 17.718000 ( 18.688000) > inject-array-map 16.797000 0.078000 16.875000 ( 16.906000) > to_ranges 0.453000 0.000000 0.453000 ( 0.453000) > > Interestingly this brings the bitset approach back in play, but it > also clearly shows what can be done with the right algorithm: Especially if it's optimized for actual input data. > def to_ranges first, last > if (NUMBERS[last] - NUMBERS[first]).abs==last-first > return [[NUMBERS[first],NUMBERS[last]]] > end > r1 = to_ranges(first, (first+last)/2) > r2 = to_ranges((first+last)/2+1, last) > if (r1.last[1] - r2.first[0]).abs == 1 > r2[0] = [r1.last[0],r2.first[1]] > r1.pop > end > r1 + r2 > end I think there is a slightly more efficient version of to_ranges: you can save the range recreation in case of the connection of the last and first ranges of r1 and r2: def to_ranges_2 first, last if (NUMBERS[last] - NUMBERS[first]).abs==last-first return [[NUMBERS[first],NUMBERS[last]]] end r1 = to_ranges_2(first, (first+last)/2) r2 = to_ranges_2((first+last)/2+1, last) r2.first[0] = r1.pop[0] if (r1.last[1] - r2.first[0]).abs == 1 r1 + r2 end With the old set of data I get $ ruby ranges-2.rb user system total real bitset 37.890000 0.000000 37.890000 ( 38.520000) inject-range 0.313000 0.000000 0.313000 ( 0.323000) inject-array 0.125000 0.000000 0.125000 ( 0.130000) inject-array-2 0.140000 0.000000 0.140000 ( 0.155000) inject-array-map 0.203000 0.000000 0.203000 ( 0.198000) to_ranges 0.141000 0.000000 0.141000 ( 0.147000) to_ranges_2 0.141000 0.000000 0.141000 ( 0.138000) to_ranges-map 0.218000 0.000000 0.218000 ( 0.224000) to_ranges_2-map 0.219000 0.000000 0.219000 ( 0.218000) With your set of NUMBERS I get $ ruby ranges-2.rb user system total real bitset 103.984000 0.000000 103.984000 (105.677000) inject-range 77.735000 0.000000 77.735000 ( 78.927000) inject-array 29.312000 0.015000 29.327000 ( 29.803000) inject-array-2 28.625000 0.000000 28.625000 ( 29.301000) inject-array-map 29.047000 0.000000 29.047000 ( 29.543000) to_ranges 0.672000 0.000000 0.672000 ( 0.684000) to_ranges_2 0.594000 0.000000 0.594000 ( 0.596000) to_ranges-map 0.750000 0.000000 0.750000 ( 0.772000) to_ranges_2-map 0.609000 0.000000 0.609000 ( 0.640000) Your approach has a clear advantage if ranges are fairly large compared to the overall number of elements in the array. I wonder whether there is still room for optimization with regard to division of the array. > This would have been a nice quiz question, but i guess its worn > out by now. Yeah, I guess so. Cheers robert ------=_NextPart_000_0034_01C59B63.A8F6EEB0 Content-Type: application/octet-stream; name="ranges-2.rb" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="ranges-2.rb" =0A= require 'benchmark'=0A= =0A= REPEAT =3D 1=0A= =0A= # NUMBERS =3D [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, = 9998, 9999]=0A= NUMBERS =3D [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41] + = (1000..5000).to_a + [6789, 6790, 9998, 9999]=0A= p NUMBERS.length=0A= =0A= def to_ranges first, last=0A= if (NUMBERS[last] - NUMBERS[first]).abs=3D=3Dlast-first=0A= return [[NUMBERS[first],NUMBERS[last]]]=0A= end=0A= r1 =3D to_ranges(first, (first+last)/2)=0A= r2 =3D to_ranges((first+last)/2+1, last)=0A= if (r1.last[1] - r2.first[0]).abs =3D=3D 1=0A= r2[0] =3D [r1.last[0],r2.first[1]]=0A= r1.pop=0A= end=0A= r1 + r2=0A= end=0A= =0A= def to_ranges_2 first, last=0A= if (NUMBERS[last] - NUMBERS[first]).abs=3D=3Dlast-first=0A= return [[NUMBERS[first],NUMBERS[last]]]=0A= end=0A= r1 =3D to_ranges_2(first, (first+last)/2)=0A= r2 =3D to_ranges_2((first+last)/2+1, last)=0A= r2.first[0] =3D r1.pop[0] if (r1.last[1] - r2.first[0]).abs =3D=3D 1=0A= r1 + r2=0A= end=0A= =0A= Benchmark.bm 20 do |b|=0A= b.report "bitset" do=0A= REPEAT.times do=0A= ranges =3D []=0A= =0A= NUMBERS.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) = do |m|=0A= s =3D $`.length=0A= ranges << (s .. (s + m.length - 1))=0A= end=0A= =0A= p ranges=0A= end=0A= end=0A= =0A= b.report "inject-range" do=0A= REPEAT.times do=0A= = NUMBERS.inject([NUMBERS[0]..NUMBERS[0]]){|r,x|r<<(((r.last.end+1>=3Dx) ? = r.pop.first : x)..x)}=0A= end=0A= end=0A= =0A= b.report "inject-array" do=0A= REPEAT.times do=0A= NUMBERS.inject([[NUMBERS[0], NUMBERS[0]]]) do |r,x|=0A= if r.last[-1] + 1 >=3D x=0A= r.last[-1] =3D x=0A= r=0A= else=0A= r << [x,x]=0A= end=0A= end=0A= end=0A= end=0A= =0A= b.report "inject-array-2" do=0A= REPEAT.times do=0A= NUMBERS.inject([[NUMBERS[0], NUMBERS[0]]]) do |r,x|=0A= l =3D r.last=0A= if l[-1] + 1 =3D=3D x=0A= l[-1] =3D x=0A= r=0A= else=0A= r << [x,x]=0A= end=0A= end=0A= end=0A= end=0A= =0A= b.report "inject-array-map" do=0A= REPEAT.times do=0A= NUMBERS.inject([[NUMBERS[0], NUMBERS[0]]]) do |r,x|=0A= if r.last[-1] + 1 >=3D x=0A= r.last[-1] =3D x=0A= r=0A= else=0A= r << [x,x]=0A= end=0A= end.map! {|r| r.first .. r.last }=0A= end=0A= end=0A= =0A= b.report "to_ranges" do=0A= REPEAT.times do=0A= to_ranges( 0, NUMBERS.length - 1 )=0A= end=0A= end=0A= =0A= b.report "to_ranges_2" do=0A= REPEAT.times do=0A= to_ranges_2( 0, NUMBERS.length - 1 )=0A= end=0A= end=0A= =0A= b.report "to_ranges-map" do=0A= REPEAT.times do=0A= to_ranges( 0, NUMBERS.length - 1 ).map! {|r| r.first .. r.last }=0A= end=0A= end=0A= =0A= b.report "to_ranges_2-map" do=0A= REPEAT.times do=0A= to_ranges_2( 0, NUMBERS.length - 1 ).map! {|r| r.first .. r.last }=0A= end=0A= end=0A= =0A= b.report "seek" do=0A= REPEAT.times do=0A= p1, p2 =3D 0, NUMBERS.length - 1=0A= ranges =3D []=0A= =0A= until p1 =3D=3D NUMBERS.length=0A= p2 -=3D 1 while p2 !=3D p1 && (p2 - p1) !=3D (NUMBERS[p2] - = NUMBERS[p1]).abs=0A= ranges << (NUMBERS[p1] .. NUMBERS[p2])=0A= p1, p2 =3D p2 + 1, NUMBERS.length - 1=0A= end=0A= end=0A= end=0A= end=0A= ------=_NextPart_000_0034_01C59B63.A8F6EEB0--