Re: List difference using patterns and substitutions.
- To: mathgroup at smc.vnet.net
- Subject: [mg71345] Re: List difference using patterns and substitutions.
- From: Jon Harrop <jon at ffconsultancy.com>
- Date: Wed, 15 Nov 2006 06:44:25 -0500 (EST)
- Organization: Flying Frog Consultancy Ltd.
- References: <ejc53g$6qf$1@smc.vnet.net>
Nacho wrote:
> I'm trying to figure how can I build a difference list from another
> using only patterns and rule substitutions.
>
> The idea is to get from a list, another, one element shorter, where
> each value is the substraction of two consecutive elements in the
> original list, that is, from {1,2,3,5,5} get {1,1,2,0}.
In OCaml you just write:
let rec diff = function
| h1 :: (h2 :: _ as t) -> h1 - h2 :: diff t
| _ -> []
For example:
# diff [1;2;3;5;5];;
- : int list = [-1; -1; -2; 0]
In Mathematica you can do:
diff[{h1_, h2_, t___}] := Prepend[diff[{h2, t}], h1 - h2]
diff[_] := {}
For example:
In[3]:= diff[{1,2,3,5,5}]
Out[3]= {-1, -1, -2, 0}
But this is hugely inefficient.
> I've been thinking about it for a while, and I know several methods
> using a more traditional programming style (with For, for example), but
> I have no idea if it is possible to make it simple and fast with rule
> substitutions.
You must do two things to optimise Mathematica code:
1. Choose the best data structures and algorithms.
2. Exploit functions written in C inside the Mathematica interpreter as much
as possible.
The above Mathematica solution is very slow because the pattern matcher is
eagerly copying all of the remaining elements in the "list" when that isn't
necessary (lazy evaluation is asymptotically faster here). Secondly,
Prepend is O(n). So the overall algorithm is O(n^2) with the current
Mathematica implementation. A future implementation of Mathematica might
bring this down to O(n) but it will still be very slow compared to C code
because the Mathematica interpreter has to evaluate code for each element
in your list.
You can start optimising by using a different data structure. With linked
lists:
diff2[{h1_, t : {h2_, _}}] := {h1 - h2, diff2[t]}
diff2[_] := {}
The current Mathematica will evaluate this in O(n) time.
For example:
In[7]:= diff2[{1,{2,{3,{5,{5,{}}}}}}]
Out[7]= {-1, {-1, {-2, {0, {}}}}}
This is simple but slow. To make a fast implementation, you must use
Mathematica's built-in array operations to do the work for you, something
like:
diff3[a_] := ListConvolve[{-1, 1}, a]
For example:
In[13]:= diff3[{1,2,3,5,5}]
Out[13]= {-1, -1, -2, 0}
The performance of this implementation is now competitive with C code.
--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists