Efficient swapping of elements of an array in Java

Question

I am wondering if there is a more efficient way of swapping two elements in an Array, than doing something like this:

String temp = arr[1];
arr[1] = arr[2];
arr[2] = temp;

Well, this is obviously not bad or even wrong, but I need to swap very often so I am interested if there are any Libs or something that provide a more efficient way to do this?

Solution 1

Nope. You could have a function to make it more concise each place you use it, but in the end, the work done would be the same (plus the overhead of the function call, until/unless HotSpot moved it inline — to help it with that, make the function static final).

Solution 2

This should make it seamless:

public static final <T> void swap (T[] a, int i, int j) {
  T t = a[i];
  a[i] = a[j];
  a[j] = t;
}

public static final <T> void swap (List<T> l, int i, int j) {
  Collections.<T>swap(l, i, j);
}

private void test() {
  String [] a = {"Hello", "Goodbye"};
  swap(a, 0, 1);
  System.out.println("a:"+Arrays.toString(a));
  List<String> l = new ArrayList<String>(Arrays.asList(a));
  swap(l, 0, 1);
  System.out.println("l:"+l);
}

Solution 3

If you're swapping numbers and want a concise way to write the code without creating a separate function or using a confusing XOR hack, I find this is much easier to understand and it's also a one liner.

public static void swap(int[] arr, int i, int j) {
    arr[i] = (arr[i] + arr[j]) - (arr[j] = arr[i]);
}

What I've seen from some primitive benchmarks is that the performance difference is basically negligible as well.

This is one of the standard ways for swapping array elements without using a temporary variable, at least for integers.

Solution 4

If you want to swap string. it's already the efficient way to do that.

However, if you want to swap integer, you can use XOR to swap two integers more efficiently like this:

int a = 1; int b = 2; a ^= b; b ^= a; a ^= b;

Solution 5

Use Collections.swap and Arrays.asList:

Collections.swap(Arrays.asList(arr), i, j);

View more solutions

Comments

[djechlin]

What tests did you use to benchmark this and what were the speed improvements?

[bhuang3]

@djechlin at least, you don't need to create a temporary variable

[Robin]

XOR sounds very interesting to me, do you have any source or examples on this, however this won't help me in this case ;)

[djechlin]

@bhuang3 - please amend your post explaining why the Java compiler does not perform this optimization. I of course suspect it does hence the DV.

[bhuang3]

@djechlin I don't consider compiler optimization.. I'm just talking about programming.

[bhuang3]

@Robin int a = 1; int b = 2; a ^= b; b ^= a; a ^= b;

[djechlin]

That's far longer, more confusing, harder to read and takes more lines of code. I suppose it's more efficient solely with regard to the resource of number of variables declared on the stack but there is no reason to believe the OP was asking for optimization along this resource so DV stands...

[bhuang3]

@djechlin yes, you're right, it's hard to understand and read, it's just a programming tricky. In the real programming development, I prefer to use the obvious way.

[Robin]

@bhuang3 Thanks for the example

[Robin]

Just for the record, what is the benefit in using static final instead of just static or even none?

[bhuang3]

@Robin you're welcome, however, just as djechlin says, this way is hard to understand an read, it's just a programming tricky, by the way, if the two integers point to the same address, it may have some problems, but in java, the memory allocation is handled by JVM, so it hard to say if this way is practical or not.

[T.J. Crowder]

@Robin: static tells the compiler and VM (remember, HotSpot is the VM, which does a lot of runtime optimization) that it doesn't have worry about setting up this, which makes it easier to inline the function. final says that it won't be overridden in a subclass. I could easily be wrong about the degree to which HotSpot cares about either of them, really, I'm not au courant with HotSpot's latest wizardry. :-)

[Sergio Nakanishi]

I think you can't override a static method.

[Robin]

@T.J.Crowder: Thank you, I was aware of that, but didn't know/thought it would speed it up. I always thought, having a method static, would lead to a decrease performance, because the VW will load the method on startup?

[T.J. Crowder]

@Robin: All methods in a class are loaded when the class is loaded, whether instance or static, more in Section 12.4 of the JLS.

[Robin]

@T.J.Crowder: Thank you for the Lesson, this was new to me.

[T.J. Crowder]

@Sergio: "I think you can't override a static method." You can, unless it's final, but it's very different from overriding an instance method. Note this error overriding a static final (ideone.com/NuMyv4): "error: foo() in Derived cannot override foo() in Base...overridden method is static,final". That error goes away if it's not final (ideone.com/vnuAk6). It only comes into play if you call the static method via an instance reference, which is an odd thing to do. The method called is determined at compile-time, from the type of the ref: ideone.com/yXDgpa.

[Radim Vansa]

In modern JVMs it does not matter whether the method is final or not; using Class Hierarchy Analysis the compiler determines how many overrides there are and inlines it right away as long as the bytecode-length of the method is shorter than 35 bytes (-XX:MaxInlineSize). If it loads class with override, it invalidates its assumptions and recompiles the method again. Use final when you want to prevent overriding (here it makes sense), not just to hint the assembly compiler.

[LostNomad311]

this works well , thanks . note that this requires an array of objects so if you get on of those weird compile time errors make sure your using Integer[] array instead of int[] array .

[lin]

but arr[i] + arr[j] may overflow

[kmecpp]

@ChaojunZhong that should not be an issue. The new [i] will be calculated fine when the other number is subtracted. Try it in an IDE

[jeffery.yuan]

This will not work if the type in the array is primitive.Arrays.asList(int[]) will convert it to a list of int[].

[Locke]

This doesn't answer the question. The question was to swap elements of an array. Flipping the references to two arrays does nothing to modify their contents. Not to mention you used the exact same method to switch the arrays as the question was trying to find an alternative to.

[Denis Nikolaenko]

Technically, static methods in sub classes are not overridden. They are hidden.

[T.J. Crowder]

@DenisNikolaenko - Ah, yes, thanks! Lurkers, more here.

[greybeard]

What's the distinguishing detail over Neel Alex' answer?

[greybeard]

What question does this try to answer?

[greybeard]

What question does this try to answer? Why would this be preferable?

[Akhil kumar Amarneni]

Can I know why it will not work for primitive types. Actually its not working for me need to know the reason for this.