(no subject)

[Jocelyn Serot]

Just to know - before i start the work : is there any plans or work 
undergoing for integrating the support for Ocaml3.0 "custom blocks" in 
the Camlidl stub code generator ?

J. Serot

-- 
E-mail: Jocelyn.Serot@l_a_s_m_e_a.u_n_i_v-bpclermont.fr .....................
S-mail: LASMEA - UMR 6602 CNRS, Universite Blaise Pascal, 63177 Aubiere cedex
Tel: (33) 04 73.40.73.30 - Fax: (33) 04 73.40.72.62 .........................
.... http://wwwlasmea.univ-bpclermont.fr/Personnel/Jocelyn.Serot/Welcome.html
Valid e-mail: remove underscores (sorry, this is prevention against junk mail

sorting of list of vectors (array with one dimension)

[Mattias Waldau]

I have a list of vectors, I would like to sort according to the first
vector, and move the corresponding data in the other vectors.

Is there a function for this (for example, a sort function, where I add a
function that is called each time data is swapped) or do I have to write a
quicksort in ocaml.

/mattias

Re: sorting of list of vectors (array with one dimension)

[John Max Skaller]

Mattias Waldau wrote:
> 
> I have a list of vectors, I would like to sort according to the first
> vector, and move the corresponding data in the other vectors.
> 
> Is there a function for this (for example, a sort function, where I add a
> function that is called each time data is swapped) or do I have to write a
> quicksort in ocaml.

Indirection is the solution to everything :-)

Make a vector of indexes, initially 0,1,2,3 ... n-1,
and sort them with a 'compare' routine which looks at your first vector.

When finished, reorganise all the vectors in the new order indicated
by the indices. You can now move the element that should be in slot 0
there,
saving the old contents of slot 0, 
and rippling through the first cycle until the location for the saved
data is freed. The problem is to find the next cycle. The easiest way I
can think
of is to flag which slots have been fixed, and find any one that has
not,
if any, and start the ripple again from there. I don't see, immediately,
how to do this in less than linear time. Anyone?

Example: sorting "helowrd"
                  0123456

leads to "dehlorw"
          6102354

so we have to move: 6->0, 1->1, 0->2, 2->3, 3->4, 5->5, 4->6.
The cyclic decomposition is:

	(60234)(1)(5)



-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: sorting of list of vectors (array with one dimension)

[Sven LUTHER]

On Thu, Nov 30, 2000 at 06:37:51PM +1100, John Max Skaller wrote:
> Mattias Waldau wrote:
> > 
> > I have a list of vectors, I would like to sort according to the first
> > vector, and move the corresponding data in the other vectors.
> > 
> > Is there a function for this (for example, a sort function, where I add a
> > function that is called each time data is swapped) or do I have to write a
> > quicksort in ocaml.

why not use a associative map or something such instead of a list of vectors ?
you would use the content of the first vector as key, and the other vectors as
data. This way you get a datatype which is ordered as stored, and which give
you faster random access & modify time than a list. It still is a fully
functional datatype.

Friendly,

Sven Luther

Re: sorting of list of vectors (array with one dimension)

[John Max Skaller]

Sven LUTHER wrote:

> why not use a associative map or something such instead of a list of vectors ?

	Performance.
 
-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

RE: sorting of list of vectors (array with one dimension)

[Mattias Waldau]

Nice suggestions changing the data structure, but I can't change it.

Instead, I implemented the indirection trick by Max Skaller. However instead
of finding how to reorder the data, I just use a temporary data structure
instead.

The algoritm is first to find how to reorder (sort_columns_step_1), and then
l the reordering on each array (sort_columns_step_2).

In this example I like to sort the arrays t1,t2 and t3 according to t1

let t1 = [|2;1;4;3|] in
let t2 = [|true;false;false;true|] in
let t3 = [|"mattias";"magnus";"george";"hugo"|] in
let reorder = sort_columns_step_1 t1 in
   sort_columns_step_2 ~reorder t1;
   sort_columns_step_2 ~reorder t2;
   sort_columns_step_2 ~reorder t3;
   (t1,t2,t3);;
              - : int array * bool array * string array =
[|1; 2; 3; 4|], [|false; true; true; false|],
[|"magnus"; "mattias"; "hugo"; "george"|]

and the code is

let sort_columns_step_1 (a:'a array) : int array =
  let a_i = Array.init (Array.length a) (fun ii -> ii) in
  let compare_a = (fun e1 e2 -> compare a.(e1) a.(e2)) in
  Array.sort compare_a a_i;
  a_i

let sort_columns_step_2 ~(reorder:int array) (a:'a array) =
  let a_temp = Array.init (Array.length a) (fun ii -> a.(reorder.(ii))) in
  Array.iteri (fun ii el -> a.(ii) <- el) a_temp

----
Mattias Waldau, CTO
Tacton AB, Saltmatargatan 7, 11359 Stockholm
Mobile +46 70 549 11 12
http://www.tacton.com mailto:mattias.waldau@tacton.com

Re: sorting of list of vectors (array with one dimension)

[John Max Skaller]

Mattias Waldau wrote:
> 
> Nice suggestions changing the data structure, but I can't change it.
> 
> Instead, I implemented the indirection trick by Max Skaller. However instead
> of finding how to reorder the data, I just use a temporary data structure
> instead.

That's easiest, but it would be nice to find a fast way to reorder
the array in place, in case you get very large arrays, where
constructing a new one would exhaust memory, or slow down
the process due to the VM thrashing the disk.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: sorting of list of vectors (array with one dimension)

[Judicael Courant]

Mattias Waldau a écrit :
> 
> I have a list of vectors, I would like to sort according to the first
> vector, and move the corresponding data in the other vectors.
> 
> Is there a function for this (for example, a sort function, where I add a
> function that is called each time data is swapped) or do I have to write a
> quicksort in ocaml.
> 
> /mattias

Maybe you are not using the right data representation ? Things would be
much simpler if you used a vector of lists instead of a list of vectors
; just a matter of

Array.sort (fun l1 l2 -> compare (List.hd l1) (List.hd l2)) lv

Now, you can easily convert your initial representation to this one as
follows (untested code):

(* get : int -> 'a array list -> 'a list *)
let get i vl = List.map (fun t -> t.(i)) vl

(* lv_of_vl : 'a array list -> 'a list array *)
let lv_of_vl vl =
  Array.init (Array.length (List.hd vl))
             (fun i -> get i vl)

(* set : int -> 'a list -> 'a array list -> unit *)
let set i l vl =
  List.iter2 (fun x t -> t.(i) <- x) l vl

(* vl_of_lv : 'a list array -> 'a array list -> unit *)
let vl_of_lv lv vl =
   Array.iteri (fun i l -> set i l vl) lv


Sincerly yours,

Judicaël.
-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
"Montre moi des morceaux de ton monde, et je te montrerai le mien"
Tim, matricule #929, condamné à mort.
http://rozenn.picard.free.fr/tim.html