Swap elements in list without copy [duplicate]

Question

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.

Answer 1

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}
*)

Answer 2

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}

Answer 3

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.

Answer 4

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