ocaml-lib-devel

Re: [Ocaml-lib-devel] ExtArray?

[Jonathan R. <jon...@gm...>]

How about this for Array.filter?

# let filter pred array =3D
    let j =3D ref 0 in
    for i =3D 0 to Array.length array - 1 do
      if pred array.(i) then (
        array.(!j) <- array.(i); incr j;
      )
    done;
    Array.sub array 0 !j;;
val filter : ('a -> bool) -> 'a array -> 'a array =3D <fun>

Although, it's a destructive update, which is probably not desired...
in which case, add "let array =3D Array.copy array in" before the loop.

I haven't done a benchmark, but I think could be more efficient.

Jonathan

Re: [Ocaml-lib-devel] ExtArray?

[Jonathan R. <jon...@gm...>]

IMO, Array.filter should return an array of the same size. Reason:
whilst arrays are mutable, they are not resizable.

Then it's just a specialised Array.map.

let filter pred =3D map (fun elt -> if pred elt then Some elt else None);;

find_all then builds a list by unwrapping all values Some 'a from filter.

My 2c,

Jonathan

Re: [Ocaml-lib-devel] ExtArray?

[Brian H. <bh...@sp...>]

On Fri, 25 Nov 2005, Jonathan Roewen wrote:

> IMO, Array.filter should return an array of the same size. Reason:
> whilst arrays are mutable, they are not resizable.

Which makes the usefullness of this function deeply questionable, I agree.

>
> Then it's just a specialised Array.map.
>
> let filter pred = map (fun elt -> if pred elt then Some elt else None);;

This is simple enough, I don't see why a new library function is needed. 
The changing size version is complicated enough I don't want to be 
constantly recoding it.

Brian

Re: [Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

I've changed the implementation of Array.filter to use BitSets at your
suggestion.  The version using the actual BitSet type is quite a bit
shorter than your version.

I've also implemented Array.partition along the same lines.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

Hi,

Did you do any benchmarks?  I did a quick, creating 10000 arrays of random
size between 0-1000 (a couple preliminary tests of size 0-10000 elements
gave a similar trend).  On average,  I get results like:

byte code:
jones 6.9 (from CVS)
hurt 7.2 (from email)
skaller  5.8 (list with remembered size - see below)

native code:
jones  0.82
hurt  0.80
skaller 0.72

So, it would seem that the version which uses lists + length as an
intermediate representation is the fastest.  Caveat: I probably didn't run
it long enough/with large enough arrays to test the effects of garbage
collection. Brian's version might be better in these cases, but that may
require more in-depth testing.  But Max's version is much simpler! :)

I think these results suggest that it may make a lot of sense to have
find_all return a list.  (As Max suggested, perhaps a common function calle=
d
by both find_all and filter, which returns list * length).

-Amit

(Code for skaller below)

let filter f a =3D
    let result =3D ref [] in
    let n =3D ref 0 in
        Array.iter
            (fun x ->
                if f x then begin
                    result :=3D x :: !result;
                    incr n
                end)
            a;
    match !result with
    | []    ->    [| |]
    | x::xs    ->
        let filtered =3D Array.create !n x in
        let rec fill i =3D function
        | []    -> filtered
        | x::xs -> filtered.(i) <- x; fill (i+1) xs
        in
            fill 1 xs;;

On 11/25/05, Richard Jones <ri...@an...> wrote:
>
>
> I've changed the implementation of Array.filter to use BitSets at your
> suggestion.  The version using the actual BitSet type is quite a bit
> shorter than your version.
>
> I've also implemented Array.partition along the same lines.
>
> Rich.
>
> --
> Richard Jones, CTO Merjis Ltd.
> Merjis - web marketing and technology - http://merjis.com
> Team Notepad - intranets and extranets for business -
> http://team-notepad.com
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

Re: [Ocaml-lib-devel] ExtArray?

[Brian H. <bh...@sp...>]

On Fri, 25 Nov 2005, Amit Dubey wrote:

> Hi,
>
> Did you do any benchmarks?

Nope.

Brian

Re: [Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

Here are a couple more functions which I propose for addition to
ExtArray:

  (* Swap two elements in an array. *)
  let swap xs i j =
    if i <> j then (
      let c = xs.(i) in
      xs.(i) <- xs.(j);
      xs.(j) <- c
    )
  
  (* Randomize an array (in place). *)
  let unsort xs =
    let n = Array.length xs in
    for i = 0 to n-2 do
      let j = Random.int (n - i) in
      swap xs i j
    done

If you like those, then one for ExtList:

  (* Randomize a list. *)
  let unsort xs =
    let xs = Array.of_list xs in
    Array.unsort xs;
    Array.to_list xs

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtArray?

[Nicolas P. <nic...@gm...>]

SGksCgpPbiAxMi83LzA1LCBSaWNoYXJkIEpvbmVzIDxyaWNoQGFubmV4aWEub3JnPiB3cm90ZToK
Pgo+IEhlcmUgYXJlIGEgY291cGxlIG1vcmUgZnVuY3Rpb25zIHdoaWNoIEkgcHJvcG9zZSBmb3Ig
YWRkaXRpb24gdG8KPiBFeHRBcnJheToKPgpbLi4uXQoKPgo+ICAgKCogUmFuZG9taXplIGFuIGFy
cmF5IChpbiBwbGFjZSkuICopCj4gICBsZXQgdW5zb3J0IHhzID0KWy4uLl0KCklNSE8gSSB0aGlu
ayB0aGF0IHNodWZmbGUgaXMgYSBtb3JlIHN1aXRhYmxlIG5hbWUgZm9yIHRoZXNlIGZ1bmN0aW9u
cy4KCi0tCk5pY29sYXMgUG91aWxsYXJkIGFrYSBFcnRhaSAgPGVydGFpQGZleWRha2lucy5vcmc+
Cmh0dHA6Ly91dHRrLm9yZyAgICAgIFV0dGsgLS0gVW5pZmllZCBUZXN0IFRvb2wgS2l0Cg==