Повышение эффективности Alog (поворот массива влево на n итераций)

Question

Я решаю задачу, чтобы повернуть массив влево на n количество итераций. Код в значительной степени работает, но отстает от очень-очень большого ввода. Как еще повысить эффективность

// Complete the rotLeft function below.
static int[] rotLeft(int[] a, int iterations) {

      for(int i=0;i<iterations;i++)
      {
         int[] temp=Arrays.copyOfRange(a, 1, a.length);  
         temp=Arrays.copyOf(temp,a.length);
         temp[a.length-1]=a[0];
         a=temp;
      }


      return a;
}

Предложения приветствуются. Спасибо

Answer 1

Вот поворот на месте (не использует второй массив), с O (a.length) сложностью по времени. В моей системе (Intel 3770K 3,5 ГГц) он может вращать массив элементов размером 2 ^ 28 = 268 435 456 в .17 (поворот 76) до 0,85 секунд (поворот 1). Перестановки выполняются в последовательных последовательностях доступа, что облегчает кеширование.

    // rotate in place
    public static void rolip(int[] a, int r){
        r = r % a.length;
        if(r == 0)
            return;
        int t;
        int n = a.length - r;
        int i = 0;
        int j;
        while(true){
            if(r <= n){                     // shift left r places
                for(j = i+r; i < j; i++){
                    t = a[i];               //  swap(a[i], a[i+r])
                    a[i] = a[i+r];
                    a[i+r] = t;
                }
                n -= r;
                if(n == 0)
                    break;
            } else {                        // shift right n places
                i += r;
                for(j = i+n; i < j; i++){
                    t = a[i];               //  swap(a[i], a[i-n])
                    a[i] = a[i-n];
                    a[i-n] = t;
                }
                i -= n+r;
                r -= n;
                if(r == 0)
                    break;
            }
        }
    }

---

Простое вращение с использованием второго массива. В моей системе (Intel 3770K 3,5 ГГц) он может повернуть массив элементов размером 2 ^ 28 = 268 435 456 за 0,11–0,5 секунды.

    public static void rol(int[] a, int r){
        r = r % a.length;
        if(r == 0)
            return;
        int n = a.length - r;
        int i;
        int j;
        if(r <= n){                         // if left rotate
            int[] b = new int[r];           //  save elements
            for(j = 0; j < r; j++)
                b[j] = a[j];
            for(i = 0; i < n; i++)          //  shift elements
                a[i] = a[j++];
            for(j = 0; j < r; j++)          //  copy saved elements
                a[i++] = b[j];
        } else {                            // else right rotate
            int[] b = new int[n];           //  save elements
            i = 0;
            for(j = r; j < a.length; j++)
                b[i++] = a[j];
            i = j-1;                        //  shift elements
            for(j = i-n; j >= 0; j--)
                a[i--] = a[j];
            for(j = 0; j < n; j++)          //  copy saved elements
                a[j] = b[j];
        }
    }

Answer 2

В коде есть несколько недостатков.

• Сначала вы выполняете избыточную работу - если iterations > a.length - то после итерации a.length массив просто возвращается к самому себе.
• Во-вторых, каждая итерация создает совершенно новую копию массива!
• В-третьих, новое местоположение каждого элемента в массиве может быть предопределено, если смотреть только на длину массива, количество требуемых итераций ииндекс этого элемента, нет необходимости повторять итерации.

Принимая это во внимание, это может сводиться к чему-то в виде:

 static int[] rotLeftEfficient(int[] a, int iterations) {
    iterations = iterations % a.length;
    int[] b = new int[a.length];
    for (int i = 0; i < a.length; i++) {
        int newIndex = (i - iterations + a.length) % a.length;
        b[newIndex] = a[i];
    }
    return b;
}

Thisсводится к решению O(n) - где n - количество элементов в массиве, с приличными константами.

Answer 3

Вместо смещения iterations вы можете непосредственно рассчитать конечную позицию.

finalIndex=(index-iterations+a.length)  % a.length

+ a.length добавлено, чтобы гарантировать, что finalIndex всегда является неотрицательным значением.

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

Это уменьшило временную сложность алгоритма с O (a. длина * итерации) до O (длина a) .

Answer 4

Вам не нужно делать это для каждой итерации. Вместо этого вы можете создать формулу, чтобы выяснить, куда будет направлен каждый элемент.

Например, предположим, что размер вашего массива равен n.

Затем, если вам нужно переместить массивналево на 1 итерацию, тогда элемент в позиции p будет в (p + 1)% n позиции.

Для i итераций каждый элемент будет в (p + i)% n местоположении. Таким образом, цикл для каждой итерации не требуется.

   static int[] rotLeft(int[] a, int iterations) {
        int[] answer = new int[a.length];
        for(int i=0;i<a.length;i++)
        {
            answer[i] = a[(i - iterations + a.length) % (a.length)];
        }
        return answer;
    }

Answer 5

А как же это:

    static int leftRotate(int arr[], int iterations, 
                                     int k) 
    { 
        /* To get the starting point of  
        rotated array */
        int mod = k % iterations; 

        // Prints the rotated array from  
        // start position 
        for(int i = 0; i < iterations; ++i) 
        System.out.print(arr[(i + mod) % iterations] 
                          + " ");  

        System.out.println(); 
    } 

leftRotate(arr, iterations, arr.length);

Ссылка: https://www.geeksforgeeks.org/print-left-rotation-array/