From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-08-08T08:59:53+09:00
Subject: Re: algorithm help

--8323328-1424383796-1123459190=:14508
Content-Type: MULTIPART/MIXED; BOUNDARY="8323328-1424383796-1123459190=:14508"

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--8323328-1424383796-1123459190=:14508
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Mon, 8 Aug 2005, [ISO-8859-1] Simon Kr=F6ger wrote:

> ---------------------------------------------------------------
> VALUE seek_c(VALUE self, VALUE arr)
> {
>  RArray* a =3D RARRAY(arr);
> =09  int p1 =3D 0;
>  int p2 =3D 0;
>  int d1 =3D FIX2INT(a->ptr[0]);
>  int d2 =3D 0;
>  int last =3D a->len -1;
>
>  VALUE ranges =3D rb_ary_new();
>
>  while ((p2+=3D1) <=3D last)
>  {
>    if ((d2=3DFIX2INT(a->ptr[p2])) - d1 !=3D p2 - p1)
>    {
>      rb_ary_push(ranges, rb_range_new(INT2FIX(d1), a->ptr[p2-1], 1));
>      p1 =3D p2;
>      d1 =3D d2;
>    }
>  }
>  rb_ary_push(ranges, rb_range_new(INT2FIX(d1), a->ptr[last], 1));
>  return ranges;
> }
> ---------------------------------------------------------------


o.k. - got it to compile - but you need

>      rb_ary_push(ranges, rb_range_new(INT2FIX(d1), a->ptr[p2-1], 1));
                                                                    ^
                                                                    ^
                                                                    0


>  rb_ary_push(ranges, rb_range_new(INT2FIX(d1), a->ptr[last], 1));
                                                                ^
                                                                ^
                                                                0

else the ranges exclude the ends - which should be included.  however, if y=
ou
do that negative ranges break.  i'd like to test this on actual data sizes,
which would be about 10,000 elements per array.  i'm thinking anything
O(log(n)) will rise higher, even if pure ruby, for data this large... maybe
not though...

here's a set of arrays the code should work on:

   tests =3D [
     [],
     [0],
     [0,1],
     [0,1,2],
     [0,1,2,3],
     [0,3],
     [0,3,5],
     [0,3,5,7],
     [0,1,3,4],
     [0,1,3,4,6,7],
     [0,1,3,4,6,7,9,10],
     [0,1,3,4,6,7,10],
     [0,3,4,6,7,9,10],
     [0,1,3],
     [0,3,4],
     [0,-1],
     [0,-1,-2],
     [0,-1,-3,-4],
     [0,-1,-3,-4,-6],
     [0,-1,-3,-4,-6,-7],
     [-1,-3,-4,-6,-7],
     [-3,-4],
     [-3,-4,-6, *(-42 .. -8).to_a.reverse],
   ]

but, again, actual data will be about 10,000 element big.

cheers.

-a
--=20
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| Your life dwells amoung the causes of death=20
| Like a lamp standing in a strong breeze.  --Nagarjuna=20
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D

--8323328-1424383796-1123459190=:14508--
--8323328-1424383796-1123459190=:14508--