MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: whats wrong with this code ?!

  • To: mathgroup at smc.vnet.net
  • Subject: [mg110531] Re: whats wrong with this code ?!
  • From: "becko" <becko565 at hotmail.com>
  • Date: Wed, 23 Jun 2010 01:54:06 -0400 (EDT)

I see the error of my ways now. I did try x[[{i, j}]] = x[[{j, i}]] at first, but I couldn't get past the "Set::setps: ... in the part assignment is not a symbol" message. The HoldFirst is the key! And thanks for the PbS explanation!



From: Leonid Shifrin
Sent: Sunday, June 20, 2010 5:29 AM
To: becko ; mathgroup at smc.vnet.net
Subject: [mg110531] Re: [mg110456] whats wrong with this code ?!


Hi,

Here is the correct code for your method:

ClearAll[qksort];
qksort[x_List, left_Integer, right_Integer] :=
 If[right - left >= 1, Module[{i, z}, {i, z} = split[x, left, right];
   {qksort[z[[left ;; i - 1]], 1, i - left], z[[i]],
     qksort[z[[i + 1 ;; right]], 1, right - i]} // Flatten], x]

I ommitted previous functions since no changes are needed for them.

Your code contains one non-obvious inefficiency though, and that is in the way you deal with lists, particularly swapping function. Using ReplacePart and idiom z = swap[z,...] means that you copy the entire list (actually twice - once internally via ReplacePart and once explicitly) to swap only two elements. Therefore, a single swap operation has a linear rather than the constant time complexity in the size of the list whose elements are being swapped.

This is hidden for small lists by the fact that other operations such as list indexing and breaking list into pieces are costly and shadow this effect. Also, most operations in qsort are with small lists, for which this effect is not visible. You will start seeing it for lists of ~50000 elements or so, where OTOH the use of home-made sort is only of academic interest anyway, given the highly efficient built-in sorting function.

Anyway, below is a similar implementation based on pass-by-reference semantics:

ClearAll[swapPbR];
SetAttributes[swapPbR, HoldFirst];
swapPbR[x_, i_Integer, j_Integer] :=
  x[[{i, j}]] = x[[{j, i}]];

ClearAll[splitPbR];
SetAttributes[splitPbR, HoldFirst];
splitPbR[x_, left_Integer, right_Integer] :=
  Module[{l = RandomInteger[{left, right}], T, i = left},
   T = x[[l]]; swapPbR[x, left, l];
   Do[If[x[[j]] < T, swapPbR[x, ++i, j]], {j, left + 1, right}];
   swapPbR[x, left, i];
   i];

ClearAll[qksortPbR];
qksortPbR[x_List, left_Integer, right_Integer] :=
  Module[{i, qsort, xl = x},
   qsort[l_Integer, r_Integer] :=
    If[r - l >= 1,
     i = splitPbR[xl, l, r];
     qsort[l, i - 1];
     qsort[i + 1, r]];
   qsort[left, right];
   xl];


This implementation is based on pass-by-reference semantics and in-place 
list modification for all main functions. I use a local copy of the 
original list <xl>, and recursive local <qsort> function defined in the 
Module scope, which allows me to embed <xl> into it directly without 
passing it as a parameter. The < swapPbR> function works on the original 
list passed to it, rather than creating a copy, and is constant-time. 
The function <splitPbR> also modifies the original list. Note that I 
omitted the head-testing patterns _List, since they will slow the 
function down and are not strictly  necessary for dependent functions, 
and OTOH x_List pattern may not match if this argument is held.

I find that this is a good example of a (rare) case where 
pass-by-reference can indeed have some benefits in Mathematica. You can 
do some benchamarks and see that PbR version is about twice faster for 
smalller lists and starts to win big for larger ones. Of course, it is 
still much slower than the built-in Sort.

Hope this helps.

Regards,
Leonid


On Sat, Jun 19, 2010 at 4:47 AM, becko <becko565 at hotmail.com> wrote:

  ok. I give up. I've been struggling with this the entire night. I have
  three functions: swap[..], split[..] and qksort[..]. The objective is to
  implement a recursive sort algorithm. I have tried to execute it on
  list={2,5,4,7,9,1};. But I keep getting the "Cannot take positions ..
  through .. in .." message. You may need to execute it a few times to see
  the error (because of it depends on the RandomInteger). Here are the
  three functions. Thanks in advance.

  
swap[x_List,i_Integer,j_Integer]:=ReplacePart[x,{i->x[[j]],j->x[[i]]}]

  slowsort[x_List]:=
  Module[{z=x},
  Do[
  If[z[[j]]<z[[r]],z=swap[z,j,r]],
  {r,1,Length[z]-1},{j,r+1,Length[z]}
  ];
  z
  ]

  split[x_List,left_Integer,right_Integer]:=
  Module[{L=RandomInteger[{left,right}],z,T,i=left},
   T=x[[L]];z=swap[x,left,L];
  Do[
  If [ z[[j]]<T,z=swap[z,++i,j] ],
  {j,left+1,right}
  ];
  z=swap[z,left,i];
  {i,z}
  ]

  qksort[x_List,left_Integer,right_Integer]:=
  If[right-left>=1,
  Module[{i,z},
  {i,z}=split[x,left,right];
  =
{qksort[z,left,i-1][[left;;i-1]],z[[i]],qksort[z,i+1,right][[i+1;;right]]=
}//Flatten
  ],
  x
  ]





------=_NextPart_000_003D_01CB11FC.B35F0210
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
X-Sun-Content-Length: 6786

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content=text/html;charset=iso-8859-1 =
http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 8.00.7600.16385"></HEAD>
<BODY style="PADDING-LEFT: 10px; PADDING-RIGHT: 10px; PADDING-TOP: =
15px"
id=MailContainerBody leftMargin=0 topMargin=0 =
CanvasTabStop="true"
name="Compose message area">
<DIV><FONT face=Calibri>I see the error of my ways now. I did try =
x[[{i, j}]] =
x[[{j, i}]] at first, but I couldn't get past the "Set::setps: ... in =
the part
assignment is not a symbol" message. The HoldFirst is the key! And =
thanks for
the&nbsp;PbS explanation!</FONT></DIV>
<DIV><FONT face=Calibri></FONT>&nbsp;</DIV>
<DIV><FONT face=Calibri></FONT><BR></DIV>
<DIV style="FONT: 10pt Tahoma">
<DIV style="BACKGROUND: #f5f5f5">
<DIV style="font-color: black"><B>From:</B> <A
title="mailto:lshifr at gmail.com&#10;CTRL + Click to follow link" =
href="">Leonid
Shifrin</A> </DIV>
<DIV><B>Sent:</B> Sunday, June 20, 2010 5:29 AM</DIV>
<DIV><B>To:</B> <A
title="mailto:becko565 at hotmail.com&#10;CTRL + Click to follow link"
href="">becko</A> ; <A
title="mailto:mathgroup at smc.vnet.net&#10;CTRL + Click to follow link"
href="">mathgroup at smc.vnet.net</A> </DIV>
<DIV><B>Subject:</B> Re: [mg110456] whats wrong with this code
?!</DIV></DIV></DIV>
<DIV><BR></DIV>Hi,<BR><BR>Here is the correct code for your
method:<BR><BR>ClearAll[qksort];<BR>qksort[x_List, left_Integer, =
right_Integer]
:= <BR>&nbsp;If[right - left &gt;= 1, Module[{i, z}, {i, z} = =
split[x, left,
right];<BR>&nbsp;&nbsp; {qksort[z[[left ;; i - 1]], 1, i - left], =
z[[i]],
<BR>&nbsp;&nbsp;&nbsp;&nbsp; qksort[z[[i + 1 ;; right]], 1, right - i]} =
//
Flatten], x]<BR><BR>I ommitted previous functions since no changes are =
needed
for them. <BR><BR>Your code contains one non-obvious inefficiency =
though, and
that is in the way you deal with lists, particularly swapping function. =
Using
ReplacePart and idiom z = swap[z,...] means that you copy the entire =
list
(actually twice - once internally via ReplacePart and once explicitly) =
to swap
only two elements. Therefore, a single swap operation has a linear =
rather than
the constant time complexity in the size of the list whose elements are =
being
swapped. <BR><BR>This is hidden for small lists by the fact that other
operations such as list indexing and breaking list into pieces are =
costly and
shadow this effect. Also, most operations in qsort are with small lists, =
for
which this effect is not visible. You will start seeing it for lists of =
~50000
elements or so, where OTOH the use of home-made sort is only of academic =

interest anyway, given the highly efficient built-in sorting
function.<BR><BR>Anyway, below is a similar implementation based on
pass-by-reference =
semantics:<BR><BR>ClearAll[swapPbR];<BR>SetAttributes[swapPbR,
HoldFirst];<BR>swapPbR[x_, i_Integer, j_Integer] :=<BR>&nbsp; x[[{i, =
j}]] =
x[[{j, i}]];<BR><BR>ClearAll[splitPbR];<BR>SetAttributes[splitPbR,
HoldFirst];<BR>splitPbR[x_, left_Integer, right_Integer] :=<BR>&nbsp; =
Module[{l
= RandomInteger[{left, right}], T, i = left},<BR>&nbsp;&nbsp; T = =
x[[l]];
swapPbR[x, left, l];<BR>&nbsp;&nbsp; Do[If[x[[j]] &lt; T, swapPbR[x, =
++i, j]],
{j, left + 1, right}];<BR>&nbsp;&nbsp; swapPbR[x, left, =
i];<BR>&nbsp;&nbsp;
i];<BR><BR>ClearAll[qksortPbR];<BR>qksortPbR[x_List, left_Integer,
right_Integer] :=<BR>&nbsp; Module[{i, qsort, xl = =
x},<BR>&nbsp;&nbsp;
qsort[l_Integer, r_Integer] :=<BR>&nbsp;&nbsp;&nbsp; If[r - l &gt;=
1,<BR>&nbsp;&nbsp;&nbsp;&nbsp; i = splitPbR[xl, l,
r];<BR>&nbsp;&nbsp;&nbsp;&nbsp; qsort[l, i - =
1];<BR>&nbsp;&nbsp;&nbsp;&nbsp;
qsort[i + 1, r]];<BR>&nbsp;&nbsp; qsort[left, right];<BR>&nbsp;&nbsp;
xl];<BR><BR><BR>This implementation is based on pass-by-reference =
semantics and
in-place list modification for all main functions. I use a local copy of =
the
original list &lt;xl&gt;, and recursive local &lt;qsort&gt; function =
defined in
the Module scope, which allows me to embed &lt;xl&gt; into it directly =
without
passing it as a parameter. The &lt; swapPbR&gt; function works on the =
original
list passed to it, rather than creating a copy, and is constant-time. =
The
function &lt;splitPbR&gt; also modifies the original list. Note that I =
omitted
the head-testing patterns _List, since they will slow the function down =
and are
not strictly&nbsp; necessary for dependent functions, and OTOH x_List =
pattern
may not match if this argument is held.<BR><BR>I find that this is a =
good
example of a (rare) case where pass-by-reference can indeed have some =
benefits
in Mathematica. You can do some benchamarks and see that PbR version is =
about
twice faster for smalller lists and starts to win big for larger ones. =
Of
course, it is still much slower than the built-in Sort.<BR><BR>Hope this =

helps.<BR><BR>Regards,<BR>Leonid<BR><BR>
<DIV class=gmail_quote>On Sat, Jun 19, 2010 at 4:47 AM, becko <SPAN
dir=ltr>&lt;<A href="">becko565 at hotmail.com</A>&gt;</SPAN> =
wrote:<BR>
<BLOCKQUOTE
style="BORDER-LEFT: rgb(204,204,204) 1px solid; MARGIN: 0pt 0pt 0pt =
0.8ex; PADDING-LEFT: 1ex"
class=gmail_quote>ok. I give up. I've been struggling with this the =
entire
  night. I have<BR>three functions: swap[..], split[..] and qksort[..]. =
The
  objective is to<BR>implement a recursive sort algorithm. I have tried =
to
  execute it on<BR>list={2,5,4,7,9,1};. But I keep getting the "Cannot =
take
  positions ..<BR>through .. in .." message. You may need to execute it =
a few
  times to see<BR>the error (because of it depends on the =
RandomInteger). Here
  are the<BR>three functions. Thanks in
  =
advance.<BR><BR>swap[x_List,i_Integer,j_Integer]:=ReplacePart[x,{i-&gt;=
x[[j]],j-&gt;x[[i]]}]<BR><BR>slowsort[x_List]:=<BR>Module[{z=x},<BR>D=
o[<BR>If[z[[j]]&lt;z[[r]],z=swap[z,j,r]],<BR>{r,1,Length[z]-1},{j,r+1,L=
ength[z]}<BR>];<BR>z<BR>]<BR><BR>split[x_List,left_Integer,right_Integer]=
:=<BR>Module[{L=RandomInteger[{left,right}],z,T,i=left},<BR>&nbsp;T=
=x[[L]];z=swap[x,left,L];<BR>Do[<BR>If
  [ z[[j]]&lt;T,z=swap[z,++i,j]
  =
],<BR>{j,left+1,right}<BR>];<BR>z=swap[z,left,i];<BR>{i,z}<BR>]<BR><BR>=
qksort[x_List,left_Integer,right_Integer]:=<BR>If[right-left&gt;=1,<B=
R>Module[{i,z},<BR>{i,z}=split[x,left,right];<BR>{qksort[z,left,i-1][[l=
eft;;i-1]],z[[i]],qksort[z,i+1,right][[i+1;;right]]}//Flatten<BR>],<BR>x<=
BR>]<BR><BR></BLOCKQUOTE></DIV><BR>
<DIV><FONT face=Calibri></FONT>&nbsp;</DIV></BODY></HTML>

------=_NextPart_000_003D_01CB11FC.B35F0210--


  • Prev by Date: Re: Workbench fails to build documentation
  • Next by Date: Re: Newby Q: How to specify reals
  • Previous by thread: Re: whats wrong with this code ?!
  • Next by thread: An optimization problem