14
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 6
    $\begingroup$ You can use swap = Function[{list,i,j},list[[{j,i}}]] = list[[i,j]],HoldFirst]. Example: lst = Range[10]; swap[lst, 3, 7];lst $\endgroup$ Commented Jul 12, 2014 at 12:55
  • 3
    $\begingroup$ @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] $\endgroup$ Commented Jul 12, 2014 at 14:03
  • $\begingroup$ @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. $\endgroup$ Commented Jul 12, 2014 at 14:45
  • $\begingroup$ 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 $\endgroup$ Commented Jul 13, 2014 at 0:12
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 14, 2014 at 12:13

4 Answers 4

Reset to default
12
$\begingroup$

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} *)
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ So this means Mathematica code runs faster if $HistoryLength=0? That's good to know! $\endgroup$ Commented Jul 22, 2014 at 8:44
5
$\begingroup$ 
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}

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you! That HoldFirst was a very important hint. $\endgroup$ Commented Jul 12, 2014 at 13:22
  • 1
    $\begingroup$ You could even get rid of the temp write: swap[list_, a_, b_] := {list[[a]], list[[b]]} = {list[[b]], list[[a]]} $\endgroup$ Commented Jul 12, 2014 at 14:12
  • $\begingroup$ @nikie thanks I just learnt this from m_goldberg's answer :) $\endgroup$ Commented Jul 12, 2014 at 14:16
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ But would it also copy the list if no other symbol referenced it? Otherwise, how do you explain @eldo's timing results? $\endgroup$ Commented Jul 12, 2014 at 14:15
  • $\begingroup$ @nikie. Yes, it would. As for edo's timing, what's to explain? His timing only tells us Mathematica can copy lists very fast. $\endgroup$ Commented Jul 12, 2014 at 14:36
  • $\begingroup$ 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. $\endgroup$ Commented Jul 12, 2014 at 14:51
  • $\begingroup$ So there is no way to do a simple swap without copying a huge list of data? $\endgroup$ Commented Jul 12, 2014 at 16:38
  • $\begingroup$ @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. $\endgroup$ Commented Jul 12, 2014 at 17:14
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ {a, b} = {b, a} preforms a swap in Mathematica, no temporary variable required. $\endgroup$ Commented Jul 12, 2014 at 14:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.