Question Pourquoi la fonction de tri rapide C est-elle beaucoup plus lente (comparaisons de bandes, permutation de bandes) que la fonction de tri par bulles?


Je vais implémenter un "mainframe" de bande de jouet pour un étudiant, montrant la rapidité des fonctions de classe "quicksort" (récursive ou non, n'a pas vraiment d'importance, en raison du matériel lent et des techniques d'inversion de pile bien connues). la classe de fonction "bubblesort". Donc, bien que je sois clair sur l’implémentation matérielle et les contrôleurs, je suppose que la fonction de tri rapide est beaucoup plus rapide que les autres en termes de séquence, ordre et distance de comparaison (il est fin, à cause de la vitesse de rembobinage différente.

Malheureusement, ce n'est pas vrai; Ce simple code "à bulles" montre de grandes améliorations par rapport aux fonctions de "tri rapide" en termes de distances de comparaison, de direction et de nombre de comparaisons et d'écritures.

J'ai donc 3 questions:

  1. Est-ce que j'ai une erreur dans la mise en œuvre de la fonction de tri rapide?
  2. Est-ce que j'ai une erreur dans ma mise en œuvre de la fonction de bubbleoft?
  3. Sinon, pourquoi la fonction "bubblesort" est-elle tellement plus rapide dans les opérations de comparaison et d’écriture que dans la fonction "quicksort"?

J'ai déjà une fonction "quicksort":

void quicksort(float *a, long l, long r, const compare_function& compare)
{
    long i=l, j=r, temp, m=(l+r)/2;
    if (l == r) return;
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while (1)
        {
            i = l;
            j = r;
            while (i < m && !compare(a, i, m)) i++;
            while (m < j && !compare(a, m, j)) j--;
            if (i >= j)
            {
                break;
            }
            swap(a, i, j);
        }
        if (l < m) quicksort(a, l, m, compare);
        if (m < r) quicksort(a, m, r, compare);
        return;
    }
}

et j'ai ma propre implémentation de la fonction "bubblesort":

void bubblesort(float *a, long l, long r, const compare_function& compare)
{
    long i, j, k;
    if (l == r)
    {
        return;
    }
    if (l == r-1)
    {
        if (compare(a, l, r))
        {
            swap(a, l, r);
        }
        return;
    }
    if (l < r-1)
    {
        while(l < r)
        {
            i = l;
            j = l;
            while (i < r)
            {
                i++;
                if (!compare(a, j, i))
                {
                    continue;
                }
                j = i;
            }
            if (l < j)
            {
                swap(a, l, j);
            }
            l++;
            i = r;
            k = r;
            while(l < i)
            {
                i--;
                if (!compare(a, i, k))
                {
                    continue;
                }
                k = i;
            }
            if (k < r)
            {
                swap(a, k, r);
            }
            r--;
        }
        return;
    }
}

J'ai utilisé ces fonctions de tri dans un exemple de code de test, comme ceci:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>

long swap_count;
long compare_count;

typedef long (*compare_function)(float *, long, long );
typedef void (*sort_function)(float *, long , long , const compare_function& );

void init(float *, long );
void print(float *, long );

void sort(float *, long, const sort_function& );
void swap(float *a, long l, long r);

long less(float *a, long l, long r);
long greater(float *a, long l, long r);

void bubblesort(float *, long , long , const compare_function& );
void quicksort(float *, long , long , const compare_function& );

void main()
{
    int n;
    printf("n=");

    scanf("%d",&n);
    printf("\r\n");

    long i;
    float *a = (float *)malloc(n*n*sizeof(float));

    sort(a, n, &bubblesort);
    print(a, n);

    sort(a, n, &quicksort);
    print(a, n);

    free(a);
}

long less(float *a, long l, long r)
{
    compare_count++;
    return *(a+l) < *(a+r) ? 1 : 0;
}

long greater(float *a, long l, long r)
{
    compare_count++;
    return *(a+l) > *(a+r) ? 1 : 0;
}

void swap(float *a, long l, long r)
{
    swap_count++;

    float temp;

    temp = *(a+l);
    *(a+l) = *(a+r);
    *(a+r) = temp;
}

float tg(float x)
{
    return tan(x);
}

float ctg(float x)
{
    return 1.0/tan(x);
}

void init(float *m,long n)
{
    long i,j;
    for (i = 0; i < n; i++)
    {
        for (j=0; j< n; j++)
        {
            m[i + j*n] = tg(0.2*(i+1)) + ctg(0.3*(j+1));
        }
    }
}

void print(float *m, long n)
{
    long i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("  %5.1f", m[i + j*n]);
        }
        printf("\r\n");
    }
    printf("\r\n");
}

void sort(float *a, long n, const sort_function& sort)
{
    long i, sort_compare = 0, sort_swap = 0;

    init(a,n);

    for(i = 0; i < n*n; i+=n)
    {
        if (fmod (i / n, 2) == 0)
        {
            compare_count = 0;

            swap_count = 0;
            sort(a, i, i+n-1, &less);

            if (swap_count == 0)
            {
                compare_count = 0;
                sort(a, i, i+n-1, &greater);
            }

            sort_compare += compare_count;
            sort_swap += swap_count;
        }
    }

    printf("compare=%ld\r\n", sort_compare);
    printf("swap=%ld\r\n", sort_swap);

    printf("\r\n");
}

12
2018-02-07 07:10


origine


Réponses:


Je pense que le problème est que la plupart des implémentations de tri rapide reposent sur une étape de partition qui alterne des lectures et des écritures aux extrémités opposées de la région à trier. Dans un modèle à accès aléatoire, ceci est parfaitement correct (toutes les lectures sont essentiellement O (1)), mais sur une bande, cela peut être extrêmement coûteux, car basculer entre les différentes extrémités de la plage à trier peut prendre O ( n) le temps que la bande roule en avant et en arrière. Cela transforme ce qui est normalement une étape de partitionnement O (n) en quelque chose qui est potentiellement O (n2), dominant le temps d'exécution de la fonction. De plus, comme le temps nécessaire pour effectuer une recherche sur bande est probablement plusieurs milliers de fois inférieur à la fréquence du processeur, cet O (n2) le travail a un facteur constant énorme.

Le tri par bulles, en revanche, ne présente pas ce problème car il compare toujours les cellules adjacentes du tableau. Il fait au plus O (n) passer sur le tableau, et nécessite donc que la bande soit rembobinée seulement n fois. La logique de traitement est nettement plus chère dans le tri à bulles - plus que dans presque tous les autres O (n2) trier - mais ce n’est rien comparé au temps gagné en ne cherchant pas la bande dans les deux sens.

En bref, le tri rapide devrait probablement être beaucoup plus lent sur une bande que le tri par bulles, simplement parce que la bande doit se déplacer beaucoup plus pendant l'exécution. Étant donné que la recherche sur bande est coûteuse, l'avantage du délai d'exécution naturel à l'exécution sera réduit à ce stade et le taux de bulles devrait être beaucoup plus rapide.


32
2018-02-07 07:20



La réponse de templatetypedef est juste sur l'argent. Non seulement les accès de bubbleort sont-ils minimisés, mais ils fonctionnent en place. Je pense que c'est en fait le meilleur algorithme de tri pour une machine ayant une seule bande arbitrairement lente et seulement O (1) RAM. [EDIT: En fait sorte de cocktail (une version bidirectionnelle de bubbleort) devrait être meilleure car elle évite les rembobinages inutiles - merci Steve Jessop.]

Si vous avez 4 lecteurs de bande disponibles alors tri par fusion règle le dortoir. Avec seulement 3 bandes, une version plus sophistiquée de mergesort peut être utilisé.


11
2018-02-07 11:51



L'une des raisons pour lesquelles QuickSort est plus rapide que le tri par bulles est qu'il déplace instantanément les éléments sur de grandes distances. Si QuickSort déplace un élément de 50 éléments vers le haut, puis 20, 10, 5 et 2 avant qu'il ne se retrouve à sa place, l'élément se retrouvera dans 43 cases à partir desquelles il a démarré, tout en n'ayant bougé que 5 fois. Le tri des bulles aurait déplacé l'élément 43 fois. Si le déplacement de l'élément un emplacement coûte le même prix que son déplacement de 50, c'est une victoire majeure. Si, cependant, le coût de déplacement d'un élément est proportionnel à la distance, QuickSort aura déplacé l'élément sur une distance totale de 87 emplacements, soit deux fois plus que le tri par bulles.

Si l’on se trouve confronté à des lecteurs de bande, l’algorithme optimal dépendra beaucoup du fonctionnement physique des lecteurs. Par exemple, sur certains disques, les seules opérations sont le rembobinage et l’écriture (effacement efficace de la bande dans le processus), le retour rapide et la lecture, et le traitement de l’octet suivant (lecture ou écriture, en fonction du mode de rembobinage). D'autres lecteurs permettent d'accéder à des blocs individuels et de les remplacer n'importe où sur la bande. Certains lecteurs sont limités à la lecture dans une direction. D'autres (par exemple, les bandes QIC) ont des pistes qui lisent dans une direction et d'autres dans l'autre. Je ne sais pas si des lecteurs permettraient de lire ou d'écrire le même bloc de données dans les deux sens, mais cela serait au moins théoriquement possible.


1
2017-08-25 23:20