Re: algorithm help

Simon Kröger <SimonKroeger@xxxxxx> 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

Attachment: ranges-2.rb
Description: Binary data

Relevant Pages

  • Re: algorithm help
    ... i added a larger range 1000..5000 to the test set which should come ... closer to ara's problem at hand. ... Interestingly this brings the bitset approach back in play, ...
    (comp.lang.ruby)
  • Re: Pascal-like set class
    ... > membership seem odd, because I pronounce the code "If element e is equal ... the reason I wrote it was because I wanted low-level control of the ... answer to your question is they wouldn't, except when the array is only one ... bitset, then the answer is pascal_set is more typesafe then bitset and I ...
    (comp.lang.cpp)
  • Re: Need someone very familiar with arrays
    ... I am not failiar with your scheme but will take a closer look at it when I get home. ... Note Robert M's correction on the length/origin of the array in the ReDim step. ...
    (microsoft.public.vb.general.discussion)
  • Re: Are there any databases that can store multidiimensional boolean arrays?
    ... This person wants to store a four dimensional boolean array, ... I'd never noticed the BitSet class before in several years of coding Java ...
    (comp.lang.java.databases)
  • Using <bitset>
    ... Is there a way to use <bitset> on an external array of bits (rather than ... bitset's built in _Array)? ...
    (microsoft.public.vc.stl)