whats wrong with this code ?!
in [Mathematica]
|
From: becko on 19 Jun 2010 07:47 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 ]
From: Themis Matsoukas on 20 Jun 2010 03:47 Get a good night's sleep. Then, fix the line { qksort[z,left,i-1][[left;;i-1]], z[[i]], qksort[z,i+1,right][[i+1;;right]] } If qksort[z,left,i-1] contains fewer elements that i-1, or qksort[z,i+1,right] contains fewer than right, you will get the error message. You may try to debug your qksort using a couple print statements, as in the example below: qksort[x_List, left_Integer, right_Integer] := If[right - left >= 1, Module[{i, z}, {i, z} = split[x, left, right]; Print["1--", {qksort[z, left, i - 1], {left, i - 1}}]; Print["2--", {qksort[z, i + 1, right], {i + 1, right}}]; {qksort[z, left, i - 1][[left ;; i - 1]], z[[i]], qksort[z, i + 1, right][[i + 1 ;; right]]} // Flatten], x] This will print your lists before picking out their parts, and will also show you which parts are to be picked. Themis On Jun 19, 2010, at 7:47 AM, becko 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 > ] >
From: Leonid Shifrin on 21 Jun 2010 02:14 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(a)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 > ] > >
From: becko on 23 Jun 2010 01:55 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(a)smc.vnet.net Subject: Re: 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(a)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(a)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(a)hotmail.com CTRL + Click to follow link" href="">becko</A> ; <A title="mailto:mathgroup(a)smc.vnet.net CTRL + Click to follow link" href="">mathgroup(a)smc.vnet.net</A> </DIV> <DIV><B>Subject:</B> Re: 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(a)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--
|
Pages: 1 Prev: NotebookDirectory for package (.m) files? Next: Using Mathematica for Electrophysiology Data |