From: Robert Klemme <bob.news@...>
Date: 2005-08-07T00:21:08+09:00
Subject: Re: algorithm help

------=_NextPart_000_0037_01C59AAA.DBA63D70
Content-Type: text/plain;
	format=flowed;
	charset="iso-8859-1";
	reply-type=response
Content-Transfer-Encoding: 7bit

Ara.T.Howard <Ara.T.Howard@noaa.gov> wrote:
> On Fri, 5 Aug 2005, Kroeger Simon (ext) wrote:
>
>> true, this is optimized for the given case (m <= 2).
>
> which was exactly the tast at hand - this is 'always' true for my
> data.
>> this creates a BigInt 1250 Bytes width, alocates 10 kByte of memory,
>> fills it, reverses it, and scans it with a regular expression. All
>> to look at 17 fixnums, it may be O(C * n) but with a realy huge C.
>
> and i'm scanning rows with about 7324 pixels so this matters...
>
>> ok, I don't want to invest that much time either, but your code
>> doesn't cope with negativ numbers :)
>
> indeed.  and the code (my code) needs to do exactly that - i
> searching for pixels indicating that the sun is below the horizon
> using narray like
>   below_horizon = (narray < -3).where
>
> and then applying some data munging to only those areas of the
> scanline.  the area will always be zero, one, or two sections for
> pure daytime, crossing the solar terminator away from the poles, and
> crossing the terminator at the poles respectively.  it seems like
> that couldn't be so - but latitutes follow curves in the data to you
> can get two, but not three, ranges in a single scanline.
> in addition, the dark area, when there are two, will always be on
> opposite ends of the scanline to the 'divide and conquer' approach is
> particularly suitable.
>
> cheers.
>
> -a
>> email :: ara [dot] t [dot] howard [at] noaa [dot] gov
>> phone :: 303.497.6469
>> My religion is very simple.  My religion is kindness.
>> --Tenzin Gyatso
> ===============================================================================

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

------=_NextPart_000_0037_01C59AAA.DBA63D70
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 1000=0A=
=0A=
NUMBERS =3D [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, =
9999]=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=
    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=
end=0A=

------=_NextPart_000_0037_01C59AAA.DBA63D70--