Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5  
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 at 12:55
2  
@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 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 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 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 at 12:13

4 Answers 4

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}
*)
share|improve this answer
    
So this means Mathematica code runs faster if $HistoryLength=0? That's good to know! –  Danvil Jul 22 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}

share|improve this answer
    
Thank you! That HoldFirst was a very important hint. –  Danvil Jul 12 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 at 14:12
    
@nikie thanks I just learnt this from m_goldberg's answer :) –  eldo Jul 12 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.

share|improve this answer
    
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 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 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 at 14:51
    
So there is no way to do a simple swap without copying a huge list of data? –  Danvil Jul 12 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 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.

share|improve this answer
    
{a, b} = {b, a} preforms a swap in Mathematica, no temporary variable required. –  m_goldberg Jul 12 at 14:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.