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 PbS explanation!</FONT></DIV> <DIV><FONT face=Calibri></FONT> </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 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 CTRL + Click to follow link" href="">becko</A> ; <A title="mailto:mathgroup at smc.vnet.net 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> If[right - left >= 1, Module[{i, z}, {i, z} = = split[x, left, right];<BR> {qksort[z[[left ;; i - 1]], 1, i - left], = z[[i]], <BR> 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> x[[{i, = j}]] = x[[{j, i}]];<BR><BR>ClearAll[splitPbR];<BR>SetAttributes[splitPbR, HoldFirst];<BR>splitPbR[x_, left_Integer, right_Integer] :=<BR> = Module[{l = RandomInteger[{left, right}], T, i = left},<BR> T = = x[[l]]; swapPbR[x, left, l];<BR> Do[If[x[[j]] < T, swapPbR[x, = ++i, j]], {j, left + 1, right}];<BR> swapPbR[x, left, = i];<BR> i];<BR><BR>ClearAll[qksortPbR];<BR>qksortPbR[x_List, left_Integer, right_Integer] :=<BR> Module[{i, qsort, xl = = x},<BR> qsort[l_Integer, r_Integer] :=<BR> If[r - l >= 1,<BR> i = splitPbR[xl, l, r];<BR> qsort[l, i - = 1];<BR> qsort[i + 1, r]];<BR> qsort[left, right];<BR> 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 <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.<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><<A href="">becko565 at hotmail.com</A>></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->= x[[j]],j->x[[i]]}]<BR><BR>slowsort[x_List]:=<BR>Module[{z=x},<BR>D= o[<BR>If[z[[j]]<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> T= =x[[L]];z=swap[x,left,L];<BR>Do[<BR>If [ z[[j]]<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>=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> </DIV></BODY></HTML> ------=_NextPart_000_003D_01CB11FC.B35F0210--