Tri pathologique

Votre patron vous a demandé de développer un algorithme de tri pour améliorer les performances de l'application de votre entreprise. Cependant, après avoir écrit la demande, vous savez qu'il est peu probable que vous puissiez la rendre beaucoup plus rapide. Ne voulant pas décevoir votre patron, vous avez décidé de développer un nouvel algorithme qui fonctionne encore mieux que * trier sur certains ensembles de données. Bien sûr, vous ne pouvez pas rendre évident que l'algorithme ne fonctionne que dans certains cas, vous voulez donc le rendre aussi obscur que possible.

L'objectif de ce concours est d'écrire une routine de tri dans la langue de votre choix qui fonctionne mieux sur certains ensembles de données que sur d'autres, avec des résultats reproductibles. Plus la classification qui détermine la vitesse est précise, mieux c'est. L'algorithme doit effectuer un tri quelconque, donc un algorithme qui dépend des données déjà triées complètement (comme dans, un algorithme qui ne fait rien), ou un algorithme qui dépend des données triées complètement en sens inverse, sont tous deux invalides. L'algorithme de tri doit trier correctement tout ensemble de données.

Après avoir présenté votre routine, veuillez expliquer pourquoi elle ne fonctionne que sur certains ensembles de données et inclure des tests sur au moins un ensemble de bonnes (rapides) données et un ensemble de mauvaises (lentes) données. Le but ici est de pouvoir prouver à votre patron que vous êtes tombé sur une meilleure façon de trier, donc plus de données de test sont meilleures. Bien sûr, vous allez seulement montrer à votre patron les résultats des tests à partir des bonnes données, donc la faille dans les données de test requises ne peut pas être trop évidente. Si cela s'applique à votre langue, veuillez montrer que votre algorithme est plus rapide que l'algorithme de tri intégré de votre langue.

Par exemple, on peut soumettre un algorithme de tri par insertion, les bonnes données étant des données déjà presque triées et les mauvaises données étant des données complètement aléatoires, car le tri par insertion approche O (n) sur des données presque triées. Cependant, ce n'est pas très bon, car mon patron remarquerait probablement que toutes les données de test sont presque triées pour commencer.

C'est un concours de popularité , donc la réponse avec le plus de votes après 7 jours (21 mai) l'emporte.

Si personne ne me bat, j'aimerais soumettre une réponse wiki communautaire qui tire parti d'ensembles de données uniformément distribués.

Cela fait assez longtemps, mais je me souviens que dans Algorithms 101, nous avons appris un algorithme de tri qui utilisait la randomisation. Je n'étais pas un très bon élève, donc je ne me souviens pas vraiment comment cela s'est passé ni pourquoi cela a fonctionné rapidement en moyenne.

Néanmoins, j'ai décidé que ce problème appelle une solution qui utilise la randomisation, qui, espérons-le, fonctionnera en ma faveur en moyenne.

import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

Étant donné que la véritable randomisation est importante, je m'assure de semer le RNG avec la réponse à la vie, l'univers et tout. Après un peu de test, il s'avère que c'était une décision intelligente! Découvrez à quelle vitesse ces 2 listes complètement arbitraires sont triées:

rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

Ces deux éléments sont triés en une seule itération - vous ne pourriez pas demander une fonction plus rapide que cela!

Maintenant, certes, certaines autres listes produisent des résultats légèrement pires ...

rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

Celles-ci sont triées en 4.176 et 94.523 itérations respectivement, ce qui prend en fait plus d'une seconde ... mais gardons ce fait pour nous afin de ne distraire personne de l'étonnant de cet algorithme!

Éditer:

On m'a demandé de prouver l'efficacité de mon algorithme sur une liste de 100 éléments, alors voici:

rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

Même cette longue liste complètement arbitraire est triée instantanément! Vraiment, je dois être tombé sur le meilleur algorithme de tri au monde!

Si vous pouvez créer vos propres données, c'est assez simple - obtenez des données qui semblent aléatoires, mais qui incluent une clé pour un tri plus rapide. Toutes les autres données utilisent la méthode de tri d'origine, donc les délais moyens sont meilleurs.

Une façon simple consiste à vous assurer que chaque élément de données possède une clé unique, puis à hacher simplement les clés. Prenons par exemple une liste avec les nombres de 1 à 10 000, tous multipliés par 16, et avec un nombre aléatoire de 0 à 15 ajouté (voir fillArray () ci-dessous). Ils auront l'air aléatoires, mais chacun a une clé séquentielle unique. Pour le tri, divisez par 16 (en C, le >> 4 est très rapide), puis placez simplement le nombre dans un tableau en utilisant la clé résultante comme index. Une passe et vous avez terminé. Lors des tests, j'ai trouvé que le tri rapide était 30 fois plus lent sur dix millions de numéros.

void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

Tout ce qui a une clé unique peut être trié de cette façon - si vous avez la mémoire pour la stocker, bien sûr. Par exemple, de nombreuses bases de données utilisent un identifiant client numérique unique - si la liste est suffisamment petite / séquentielle, elle peut être conservée en mémoire. Ou une autre façon de traduire un enregistrement en un numéro unique. Pour plus d'informations, recherchez Hash Sorts, car c'est ce que c'est ...