question on reverse array

Question

we know algorithm how reverse array of n integers

 for (int i=0;i<n/2;i++){
  swap(a[i],a[n-1-i]):
}

is this method better according the speed of algorithm or not because swap using xor is more fast then in other method here is code

public class swap {

    public static  void main(String[]args){
        int a[]=new int[]{2,4,5,7,8,11,13,12,14,24};
        System.out.println(" array at the begining:");
        for (int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }

        for (int j=0;j<a.length/2;j++){
            a[j]^=a[a.length-1-j];
            a[a.length-1-j]^=a[j];
            a[j]^=a[a.length-1-j];
        }
        System.out.println("reversed array:");
        for (int j=0;j<a.length;j++){
            System.out.println(a[j]);
        }
    }
}

Result:

array at the begining:
2
4
5
7
8
11
13
12
14
24
reversed array:
24
14
12
13
11
8
7
5
4
2

Answer 1

The xor swap method is fine for integers, but calculating a.length-1-j 3 times each iteration is what's killing you.

Answer 2

It's exactly the same algorithm, but you're using the XOR swap method instead of an explicit swap using a temporary variable. The XOR swap method is just a novelty and its use is rarely, if ever justified. Stick with simple, obvious implementations and then you can concentrate on more important things.

Answer 3

swap using xor is more fast

On Java client JVM, which is less aggressive at eliminating bounds checks, then XORing without temporaries takes nearly twice as long to reverse the array than using a single temporary. If you move the values into temporaries to avoid repeating the bounds check, you get something close to the speed with a temporary, but then you haven't avoided a temporary variable.

This uses System.nanoTime, and gives 16 or 17 ms for the version with temporaries, 30ms for the version with XOR on my machine. All the rest of the loops are the same. Using temporaries for the XOR is around 19ms, so it is reasonable to deduce that the difference is due to the extra array accesses in the XOR version.

public class XorTest {
    static final int[] array = new int[10000000];

    static void runTest (String name, Runnable test) {
        final long start = System.nanoTime();

        test.run();

        final long finish = System.nanoTime();

        System.out.println (name + ": " + ( finish - start ) / 1000000 + "ms");
    }

    public static void main ( String...args ) {
        if (args.length == 0 || "xor".equals(args[0]))
            runTest(
                "xor",
                new Runnable () {
                    @Override
                    public void run () {
                        for (int i = 0, max = array.length / 2, j = array.length - 1; i < max; ++i,--j) {
                            array[i] ^= array[j];
                            array[j] ^= array[i];
                            array[i] ^= array[j];
                        }
                    }
                });
        else if ("tmp".equals(args[0]))
            runTest(
                "tmp",
                new Runnable () {
                    @Override
                    public void run () {
                        for (int i = 0, max = array.length / 2, j = array.length - 1; i < max; ++i, --j) {
                            int tmp = array[i];
                            array[i] = array[j];
                            array[j] = tmp;
                        }
                    }
                });
        else if ("xor+tmp".equals(args[0]))
            runTest(
                "xor+tmp",
                new Runnable () {
                    @Override
                    public void run () {
                        for (int i = 0, max = array.length / 2, j = array.length - 1; i < max; ++i, --j) {
                            int a = array[i];
                            int b = array[j];
                            a^=b;
                            b^=a;
                            a^=b;
                            array[i] = a;
                            array[j] = b;
                        }
                    }
                });
    }
}

Answer 4

I did some tests using XOR and temporary: XOR is about two times slower.
Here the code:

public class Swap {

    private static void swap1(int[] a) {
        int half = a.length / 2;
        Timer timer = new Timer();
        for (int repeat = 201; repeat > 0; repeat--) {
            for (int i = 0, j = a.length-1; i < half; i++,j--) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }
        Times times = timer.times();
        System.out.println("swap1: " + times);
    }

    private static void swap2(int[] a) {
        int half = a.length / 2;
        Timer timer = new Timer();
        for (int repeat = 201; repeat > 0; repeat--) {
            for (int i = 0, j = a.length-1; i < half; i++,j--) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        Times times = timer.times();
        System.out.println("swap2: " + times);
    }

    public static  void main(String[]args){
        int a[] = new int[102400];
        for (int i = 0; i < a.length; i++) {
            a[i] = i;
        }
        System.out.println(Arrays.toString(Arrays.copyOf(a, 10)) + "..." + Arrays.toString(Arrays.copyOfRange(a, a.length-10, a.length)));
        swap1(a);
        System.out.println(Arrays.toString(Arrays.copyOf(a, 10)) + "..." + Arrays.toString(Arrays.copyOfRange(a, a.length-10, a.length)));
        swap2(a);
        System.out.println(Arrays.toString(Arrays.copyOf(a, 10)) + "..." + Arrays.toString(Arrays.copyOfRange(a, a.length-10, a.length)));
        swap1(a);
        swap2(a);
    }
}

And some typical results:

java version "1.6.0_20"
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) Server VM (build 16.3-b01, mixed mode)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]...[102390, 102391, 102392, 102393, 102394, 102395, 102396, 102397, 102398, 102399]
swap1: elapsed=0,068    cpu=0,063    user=0,063    [seconds]
[102399, 102398, 102397, 102396, 102395, 102394, 102393, 102392, 102391, 102390]...[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
swap2: elapsed=0,035    cpu=0,031    user=0,031    [seconds]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]...[102390, 102391, 102392, 102393, 102394, 102395, 102396, 102397, 102398, 102399]
swap1: elapsed=0,063    cpu=0,063    user=0,063    [seconds]
swap2: elapsed=0,023    cpu=0,031    user=0,031    [seconds]

(each called two times to eliminate some start-up problems)