mergeSort with ReplaceRepeated
Luca Bedogni
I'm writing an implementation of mergesort using replacerepeated.
This is actually the code:
merge[{a1, arest___}, b : {b1, ___}] /; a1 >= b1 //. {merge[a1, arest, b1]
:> merge[b1, a1, arest] };
but it doesn't work, and I don't know why, because I'm really new to
Mathematica.
Any clue?
Regards
--
Luca Bedogni
Sjoerd C. de Vries
I guess that given the code below you haven't learned enough of the
Mathematica language to come even close to solving it.
Since it is not the goal of this group to make your homework, I can
only advise you to learn the basics using the documentation included
with Mathematica before you endeavour in the more complicated stuff.
The code below doesn't work for one thing because it doesn't contain
an actual function definition. This is usually done using Set (=) or
SetDelayed (:=). Look them up in the documentation.
Cheers -- Sjoerd
On Jun 13, 12:04 pm, Luca Bedogni <bedogni.l...@gmail.com> wrote:
> Hi
> I'm writing an implementation of mergesort using replacerepeated.
> This is actually the code:
> merge[{a1, arest___}, b : {b1, ___}] /; a1 >= b1 //. {merge[a1, arest, =
Luca Bedogni
and now I want to learn the replacerepeated mechanism. Googling around, I
found some exercises, and one is to make a mergesort function using
replacerepeated, and that was my question.
Thank you
--
Luca Bedogni
2009/6/15 Sjoerd C. de Vries <sjoerd.c...@gmail.com>
> Judging from your June 6 post, this is a homework assignment of yours.
> I guess that given the code below you haven't learned enough of the
> Mathematica language to come even close to solving it.
>
> Since it is not the goal of this group to make your homework, I can
> only advise you to learn the basics using the documentation included
> with Mathematica before you endeavour in the more complicated stuff.
>
> The code below doesn't work for one thing because it doesn't contain
> an actual function definition. This is usually done using Set (=) or
> SetDelayed (:=). Look them up in the documentation.
>
> Cheers -- Sjoerd
>
> On Jun 13, 12:04 pm, Luca Bedogni <bedogni.l...@gmail.com> wrote:
> > Hi
> > I'm writing an implementation of mergesort using replacerepeated.
> > This is actually the code:
> > merge[{a1, arest___}, b : {b1, ___}] /; a1 >= b1 //. {merge[a1, arest, =
Leonid Shifrin
I already replied to your post some days ago with a complete implementation.
In case you did not see it, I repeat it here:
Clear[toLinkedList];
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]];
Module[{h, lrev},
mergeLinked[x_h, y_h] :=
Last[{x, y,
h[]} //. {{fst : h[hA_, tA_h], sec : h[hB_, tB_h], e_h} :>
If[hA > hB, {tA, sec, h[hA, e]}, {fst, tB, h[hB, e]}], {fst :
h[hA_, tA_h], h[], e_h} :> {tA, h[], h[hA, e]}, {h[],
sec : h[hB_, tB_h], e_h} :> {h[], tB, h[hB, e]}}];
lrev[set_] :=
Last[h[set, h[]] //. h[h[hd_, tl_h], acc_h] :> h[tl, h[hd, acc]]];
sort[lst_List] :=
Flatten[Map[h[#, h[]] &, lst] //.
x_List :>
Flatten[{toLinkedList@x, {}} //. {{hd1_, {hd2_, tail_List}},
accum_List} :> {tail, {accum, lrev@mergeLinked[hd1, hd2]}}],
Infinity, h]];
It uses linked list structure {a,{b,{c,{...}}}} to achieve expected N log N
complexity, that you won't achieve by naive pattern matching like you did in
your attempts, since lists are implemented as arrays in Mathematica and the
whole array is copied at each pattern match for patterns like
{first_,rest___}. Here is, for example, a naive implementation of merge,
which will work if your lists' elements are not lists themselves (this
limitation can be easily removed if needed):
Clear[merge];
merge[x_List, y_List] :=
Block[{merge},
Flatten[merge[x, y] //. {merge[{a_, b___}, {c_, d___}] :>
If[a < c, {a, merge[{b}, {c, d}]}, {c, merge[{a, b}, {d}]}],
merge[{}, {a__}] :> {a}, merge[{a__}, {}] :> {a}}]]
which uses more or less the pattern - matching you tried ( I used Block
trick to avoid using separate names for a function and rule pattern). You
can do simple benchmarks with sorted random lists to see that it has awful
performance (assuming N = Length[x] and M = Length[y], I expect something
like O(N^2+M^2)).
For details on the linked list - based implementation, look at the previous
post of mine, or another recent one on a related topic of recursive Select
implementation. To get familiar with linked lists in Mathematica, look at
the book of David Wagner (our of print alas), online notes on efficient data
structures in Mathematica by Daniel Lichtblau, and at my book (
http://mathprogramming-intro.org/book/node525.html), or you can ask more
specific questions and I or other people here will try to answer.
Generally one must be careful with ReplaceRepeated not to produce
inefficient solutions. You can look for instance at
http://mathprogramming-intro.org/book/node153.html,
http://mathprogramming-intro.org/book/node245.html
in my book, where efficiency issues related to ReplaceRepeated are
discussed. At the same time, I think it is a good exercise to make several
RR - based implementations of some standard problems like mergesort - this
may enable you to better understand the rule-based layer of Mathematica,
which is IMO its most important and fundamental layer (as compared to
functional and imperative ones).
Regards,
Leonid
On Mon, Jun 15, 2009 at 2:36 AM, Luca Bedogni <bedogn...@gmail.com>wrote:
> Well, it is not really an homework. I'm trying to understand Mathematica,
> and now I want to learn the replacerepeated mechanism. Googling around, I
> found some exercises, and one is to make a mergesort function using
> replacerepeated, and that was my question.
>
> Thank you
> --
> Luca Bedogni
>
>
> 2009/6/15 Sjoerd C. de Vries <sjoerd.c...@gmail.com>
>
> > Judging from your June 6 post, this is a homework assignment of yours.
> > I guess that given the code below you haven't learned enough of the
> > Mathematica language to come even close to solving it.
> >
> > Since it is not the goal of this group to make your homework, I can
> > only advise you to learn the basics using the documentation included
> > with Mathematica before you endeavour in the more complicated stuff.
> >
> > The code below doesn't work for one thing because it doesn't contain
> > an actual function definition. This is usually done using Set (=) or
> > SetDelayed (:=). Look them up in the documentation.
> >
> > Cheers -- Sjoerd
> >
> > On Jun 13, 12:04 pm, Luca Bedogni <bedogni.l...@gmail.com> wrote:
> > > Hi
> > > I'm writing an implementation of mergesort using replacerepeated.
> > > This is actually the code:
> > > merge[{a1, arest___}, b : {b1, ___}] /; a1 >= b1 //. {merge[a1, arest,
> =
Sjoerd C. de Vries
My appologies if I have misjudged you. Indeed, the group regularly
gets asked questions by students that are copied straight from their
assignments, and the wording from your first post seemed to indicate
this was the case here as well.
Anyway, I still think you should become familiar with the basic stuff
before you try to go any deeper.
If you have Mathematica 6 or 7 you'll have a documentation centre
which is full of examples, each of which can be readily modified and
executed. If you are going to use functions like your merge, I'd
suggest at least reading the parts about function definitions.
Cheers -- Sjoerd
On Jun 15, 11:36 am, Luca Bedogni <bedogni.l...@gmail.com> wrote:
> Well, it is not really an homework. I'm trying to understand Mathematica,
> and now I want to learn the replacerepeated mechanism. Googling around, I
> found some exercises, and one is to make a mergesort function using
> replacerepeated, and that was my question.
>
> Thank you
> --
> Luca Bedogni
>
> 2009/6/15 Sjoerd C. de Vries <sjoerd.c.devr...@gmail.com>
>
> > Judging from your June 6 post, this is a homework assignment of yours.
> > I guess that given the code below you haven't learned enough of the
> > Mathematica language to come even close to solving it.
>
> > Since it is not the goal of this group to make your homework, I can
> > only advise you to learn the basics using the documentation included
> > with Mathematica before you endeavour in the more complicated stuff.
>
> > The code below doesn't work for one thing because it doesn't contain
> > an actual function definition. This is usually done using Set (=) or
> > SetDelayed (:=). Look them up in the documentation.
>
> > Cheers -- Sjoerd
>
> > On Jun 13, 12:04 pm, Luca Bedogni <bedogni.l...@gmail.com> wrote:
> > > Hi
> > > I'm writing an implementation of mergesort using replacerepeat=
ed.
> > > This is actually the code:
> > > merge[{a1, arest___}, b : {b1, ___}] /; a1 >= b1 //. {merge[a1, are=
st, =