Améliorer l'efficacité de Alog (faire pivoter le tableau vers la gauche de n itérations)

Et à propos de ceci:

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

Réf: https://www.geeksforgeeks.org/print-left-rotation-array/

Vous n'avez pas besoin de le faire à chaque itération. Au lieu de cela, vous pouvez créer une formule pour déterminer où chaque élément irait.

Par exemple, disons que la taille de votre tableau est n.

Ensuite, si vous devez déplacer votre tableau vers le gauche par 1 itération, alors un élément à la position p serait à (p + 1)% n position.

Pour i itérations, chaque élément serait à (p + i)% n emplacement. Ainsi, une boucle pour chaque itération n'est pas nécessaire.

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

Il y a quelques failles dans le code.

• Tout d'abord, vous effectuez un travail redondant - si itérations> a.length - puis après a.length itérations, le tableau revient simplement à lui-même.
• Deuxièmement, chaque itération crée une toute nouvelle copie du tableau!
• Troisièmement, le nouvel emplacement de chaque élément du tableau peut être prédéterminé en ne regardant que la longueur du tableau, le nombre d'itérations requises et l'index de cet élément, pas besoin de répéter les itérations.

En prenant cela en considération, cela peut se résumer à quelque chose sous la forme de:

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

Cela se résume à O (n) solution - où n est le nombre d'éléments dans le tableau, avec des constantes décentes également.

Voici une rotation sur place (n'utilise pas de deuxième tableau), avec une complexité temporelle O (a.length). Sur mon système (Intel 3770K 3,5 GHz), il peut faire pivoter un tableau d'éléments 2 ^ 28 = 268 435 456 en 0,17 (rotation 76) à 0,85 seconde (rotation 1). Les échanges sont effectués dans des séquences d'accès séquentielles, ce qui est compatible avec le cache.

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

Rotation simple à l'aide d'un deuxième tableau. Sur mon système (Intel 3770K 3,5 GHz), il peut faire pivoter un tableau de 2 ^ 28 = 268 435 456 éléments en 0,11 à 0,50 seconde.

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