вопрос по обратному массиву

Question

мы знаем алгоритм, как обратный массив из n целых чисел

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

этот метод лучше по скорости алгоритма или нет, потому что своп с использованием xor быстрее, чем в другом методе, здесь код

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]);
        }
    }
}

Результат:

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

Это точно такой же алгоритм, но вы используете метод обмена XOR вместо явного обмена с использованием временной переменной. Метод обмена XOR - это просто новинка, и его использование редко, если вообще оправдано. Придерживайтесь простых, очевидных реализаций, и тогда вы сможете сосредоточиться на более важных вещах.

Answer 2

Я провел несколько тестов, используя XOR и временный: XOR примерно в два раза медленнее.
Здесь код:

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

И некоторые типичные результаты:

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]

(каждый вызывался два раза, чтобы устранить некоторые проблемы при запуске)

Answer 3

Вот, пожалуйста, просто лучше !!

import java.util.Arrays;
import java.util.Scanner;

class Demo
{  
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter total number of elemets: ");
        int total = sc.nextInt();
        int[]arr1 = new int[total];
        int[]arr2 = new int[total];

        System.out.print("Enter elemets: ");

        for(int i = 0; i<total; i++)
        {
            arr1[i]= sc.nextInt();
        }

        System.out.print("Original Array: " +Arrays.toString(arr1));
        System.out.println();

        for(int a = 0 ; a< total; a++)
        {
            for(int j =total-a-1; j>=0; j--)
            {               
                    arr2[a]= arr1[j];
                    break;              
            }

        }
        System.out.print("Reversed Array: " +Arrays.toString(arr2));
    }    
}  

Answer 4

своп с использованием xor быстрее

В Java-клиенте JVM, который менее агрессивен в устранении проверок границ, тогда XORing без временных значений занимает почти вдвое больше времени для обращения массива, чем при использовании одного временного. Если вы перемещаете значения во временные значения, чтобы избежать повторения проверки границ, вы получаете временную переменную, близкую к скорости, но тогда вам не удалось избежать временной переменной.

Это использует System.nanoTime и дает 16 или 17 мс для версии с временными данными, 30 мс для версии с XOR на моей машине. Все остальные петли одинаковы. Использование временных значений для XOR составляет около 19 мс, поэтому разумно сделать вывод, что разница связана с дополнительным доступом к массиву в версии XOR.

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 5

Метод xor swap подходит для целых чисел, но вычисление a.length-1-j 3 раза за каждую итерацию убивает вас.