# Swap elements in list without copy [duplicate]

I have a lists with 100,000 elements and would like two swap to entries without dublicating the list

Example:

a = {11,2,7,31};
swap[2,4]; (* how to implement this? *)
a (* should print {11,31,7,2} *)


I can do

swap[i_,j_]:=(a=ReplacePart[a,{i->a[[j]],j->a[[i]]}])


but this copies the list and if there are many swaps this takes way too much time...

Edit: The important point of my question is how to do it without having Mathematica creating a copy of the list. This is in no way answered by the alleged duplicate.

-

## marked as duplicate by Öskå, acl, bobthechemist, Sjoerd C. de Vries, Mr.Wizard♦Jul 12 '14 at 23:51

You can use swap = Function[{list,i,j},list[[{j,i}}]] = list[[i,j]],HoldFirst]. Example: lst = Range[10]; swap[lst, 3, 7];lst –  Leonid Shifrin Jul 12 '14 at 12:55
@LeonidShifrin. What you have posted has syntax errors. You probably meant to write swap = Function[{list, i, j}, list[[{j, i}]] = list[[{i, j}]], HoldFirst] –  m_goldberg Jul 12 '14 at 14:03
@m_goldberg Thanks for spotting this. Actually, I first posted the comment, then tested and found those error, but got distracted and forgot to paste the correct version. –  Leonid Shifrin Jul 12 '14 at 14:45
if you just want to do numbers, you can use the bitwise XOR swap trick ... a^=b;b^=a;a^=b; reference.wolfram.com/language/ref/BitXor.html –  technosaurus Jul 13 '14 at 0:12
Dear duplicate markers, I do not see where this question has been answered before. The linked question and its answers do in no way tackle the issues of not creating a copy of the list. –  Danvil Jul 14 '14 at 12:13

Edit 2: Thanks to @Rojo for pointing out something I forgot about, which leads me to revise my answer as well as to the following conclusion:

Mathematica can swap elements in an array without copying the array.

What I neglected was $HistoryLength. Mine is set at $HistoryLength = 5; the standard default is Infinity. The issue it causes is that the result of a = Range[100000000]; is stored. When the swap is computed, the value a has to be copied so that the value in the history remains unchanged (compare with the example from the original answer, b = a; b[[1]] = -1; down below). If you set $HistoryLength = 0 then the swap occurs in place without copying a. See, for instance, Old values are not freed/garbage collected when you re-evaluate an assignment. Blank lines indicate separate input cells. Quit[]$HistoryLength = 0;

a = Range[100000000];

MaxMemoryUsed[]
(* 823174480 *)

a[[{4, 2}]] = a[[{2, 4}]]; // AbsoluteTiming
(* {0.000011, Null} *)

MaxMemoryUsed[]
(* 823175512 *)


Compare with the evidence I gave in my original answer, during which $HistoryLength was 5: Quit[]$HistoryLength = 5;         (* added *)

a = Range[10^8];

MaxMemoryUsed[]
(* 823176384 *)

a[[{4, 2}]] = a[[{2, 4}]];  (* If $HistoryLength >= 2, then the result of Range[10^8], two commands ago, has to be preserved in the history *) MaxMemoryUsed[] (* So the memory usage doubles *) (* 1623180112 *)  In the other part of my original answer, the problem was to explain why the timing seemed fast on iterated swaps inside a Do loop. The explanation is the same as above. The intermediate results of each iteration are not stored in the history, so no copying is done. If $HistoryLength = 0, then all swaps will be fast.

Quit[]

$HistoryLength = 0 SeedRandom[1]; a = Range[10^8]; With[{indices = Range[10^8]}, sw = Table[RandomSample[indices, 2], {1000}] ]; Do[a[[s]] = a[[Reverse@s]], {s, sw}]; // AbsoluteTiming (* {0.002138, Null} *)  If HistoryLength is changed to 5 or so, a copy of the initial value of a will be made on the first swap, but subsequent swaps will be fast. This may be inferred by comparing the Do with one that does one swap: Do[a[[s]] = a[[Reverse@s]], {s, sw}]; // AbsoluteTiming (* {0.430604, Null} *)  For further confirmation, we can see that the bulk of the time corresponds to how long it takes to write 10^8 integers to RAM: a = Range[10^8]; // AbsoluteTiming (* {0.371801, Null} *)  A similar comparison to an operation that requires reading and writing: Evaluating b = a creates a reference but does not copy memory; the subsequent command b[[1]] = -1 forces Mathematica to copy the list (as well as change b[[1]]). b = a; b[[1]] = -1; // AbsoluteTiming (* {0.437203, Null} *)  Side issue: The code for the iterated swaps in the original answer was somewhat different. It used a instead of With for the indices to generate the list of swaps sw. Using a this way causes a to get copied on the first swap even if $HistoryLength = 0.

Quit[]

$HistoryLength = 0 SeedRandom[1]; a = Range[10^8]; sw = Table[RandomSample[a, 2], {1000}]; Do[a[[s]] = a[[Reverse@s]], {s, sw}]; // AbsoluteTiming (* first time *) (* {0.405094, Null} *) Do[a[[s]] = a[[Reverse@s]], {s, sw}]; // AbsoluteTiming (* second time *) (* {0.002062, Null} *)  I do not fully understand this. A possible hypothesis is that a reference to the original value of a is maintained via the RandomSample code; however, it is not a thoroughly satisfying hypothesis. Edit 1: Illustration of the multiple swap code. SeedRandom[1]; a = Range[20] sw = Table[RandomSample[a, 2], {5}] (* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} {{6, 1}, {8, 1}, {3, 4}, {1, 17}, {15, 4}} *) Do[a[[s]] = a[[Reverse@s]], {s, sw}]; a (* {17, 2, 4, 15, 5, 1, 7, 6, 9, 10, 11, 12, 13, 14, 3, 16, 8, 18, 19, 20} *)  - So this means Mathematica code runs faster if $HistoryLength=0? That's good to know! –  Danvil Jul 22 '14 at 8:44
ClearAll@swap
SetAttributes[swap, HoldFirst];

swap[list_, a_, b_] :=
With[{temp = list[[a]]},
list[[a]] = list[[b]];
list[[b]] = temp]

a = {11, 2, 7, 31};

swap[a, 2, 4]; a


{11, 31, 7, 2}

b = Range[100000];

Do[swap[b, 2, 4], {1000}] // Timing


{0.015600, Null}

-
Thank you! That HoldFirst was a very important hint. –  Danvil Jul 12 '14 at 13:22
You could even get rid of the temp write: swap[list_, a_, b_] := {list[[a]], list[[b]]} = {list[[b]], list[[a]]} –  nikie Jul 12 '14 at 14:12
@nikie thanks I just learnt this from m_goldberg's answer :) –  eldo Jul 12 '14 at 14:16

If you are asking if you can do the swap in-place, that is, by destructively modifying the list containing the elements you want to swap, I believe what you ask is impossible. As far as can I tell, Mathematica never modifies a list in place, although it sometimes creates the illusion that it does.

Consider

a = {11, 2, 7, 31}; b = a; a === b

True

a[[{4, 2}]] = a[[{2, 4}]]; {a, b}

{{11, 31, 7, 2}, {11, 2, 7, 31}}


If the swap had really been made in-place, both a and b would have been modified. But since b remains unmodified, a must have been rebound to a newly created list containing the result of the swap. Therefore, there are now two lists in memory where there had only been one before.

-
But would it also copy the list if no other symbol referenced it? Otherwise, how do you explain @eldo's timing results? –  nikie Jul 12 '14 at 14:15
@nikie. Yes, it would. As for edo's timing, what's to explain? His timing only tells us Mathematica can copy lists very fast. –  m_goldberg Jul 12 '14 at 14:36
Did you try playing with the numbers? I find it hard to believe that Mathematica can copy a 8 GB list 100.000 times in less than 2 seconds. With a GHz CPU, it should take about a second (order of magnitude) to copy it once. –  nikie Jul 12 '14 at 14:51
So there is no way to do a simple swap without copying a huge list of data? –  Danvil Jul 12 '14 at 16:38
@Danvil. Not that I know of. I once spent two days trying to find a way make Mathematica modify a list in-place, but failed. –  m_goldberg Jul 12 '14 at 17:14

Use a tmp variable x, if you want to swap a & b, first let x = a, then a = b, then b = tmp.

-
{a, b} = {b, a} preforms a swap in Mathematica, no temporary variable required. –  m_goldberg Jul 12 '14 at 14:38