Sortowanie patologiczne

Twój szef zażądał opracowania algorytmu sortowania w celu poprawy wydajności aplikacji twojej firmy. Jednak po napisaniu aplikacji wiesz, że prawdopodobnie nie będziesz w stanie znacznie przyspieszyć jej działania. Nie chcąc zawieść swojego szefa, postanowiłeś opracować nowy algorytm, który działa nawet lepiej niż * sortowanie na niektórych zestawach danych. Oczywiście, nie możesz dać do zrozumienia, że ​​algorytm działa tylko w niektórych przypadkach, więc chcesz, aby był jak najbardziej niejasny.

Celem tego konkursu jest napisanie procedury sortowania w wybranym języku, który będzie działał lepiej na określonych zestawach danych niż inne, z powtarzalnymi wynikami. Im bardziej szczegółowa klasyfikacja określa prędkość, tym lepiej. Algorytm musi dokonywać pewnego rodzaju sortowania, więc algorytm, który zależy od danych, które są już całkowicie posortowane (jak w algorytmie, który nic nie robi), lub algorytm, który zależy od danych, które są całkowicie posortowane w odwrotnej kolejności, są nieprawidłowe. Algorytm sortowania musi poprawnie sortować dowolny zestaw danych.

Po przedstawieniu procedury prosimy o wyjaśnienie, dlaczego działa ona tylko na niektórych zestawach danych, oraz na włączenie testów na co najmniej jednym zestawie dobrych (szybkich) danych i jednym zestawie złych (wolnych) danych. Chodzi o to, aby móc udowodnić swojemu szefowi, że natknąłeś się na lepszy sposób sortowania, więc więcej danych testowych jest lepszych. Oczywiście pokażesz swojemu szefowi tylko wyniki testu z dobrych danych, więc wada wymaganych danych testowych nie może być zbyt oczywista. Jeśli dotyczy twojego języka, pokaż, że Twój algorytm jest szybszy niż wbudowany algorytm sortowania w Twoim języku.

Na przykład, można przesłać algorytm sortowania wstawiania, przy czym dobre dane to dane, które są już prawie posortowane, a złe dane to dane całkowicie losowe, ponieważ sortowanie wstawiania zbliża się do O (n) na prawie posortowanych danych. Nie jest to jednak zbyt dobre, ponieważ mój szef prawdopodobnie zauważyłby, że wszystkie dane testowe są już prawie posortowane.

To konkurs popularności , więc wygrywa odpowiedź z największą liczbą głosów po 7 dniach (21 maja).

Jeśli nikt mnie nie pobije, chciałbym przesłać odpowiedź wiki społeczności, która korzysta z równomiernie rozmieszczonych zestawów danych.

Minęło sporo czasu, ale pamiętam, że w Algorytmach 101 nauczono nas algorytmu sortowania wykorzystującego losowość. Nie byłem zbyt dobrym uczniem, więc tak naprawdę nie pamiętam, jak poszło i dlaczego zadziałało to średnio.

Mimo to zdecydowałem, że ten problem wymaga rozwiązania wykorzystującego randomizację, które, mam nadzieję, zadziała średnio na moją korzyść.

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

Ponieważ prawdziwa randomizacja jest ważna, zapewniam RNG odpowiedź na Życie, Wszechświat i Wszystko. Po kilku testach okazuje się, że był to sprytny ruch! Sprawdź, jak szybko posortowane są te 2 całkowicie dowolne listy:

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

Oba są sortowane tylko w 1 iteracji - nie można chyba poprosić o szybszą funkcję!

Trzeba przyznać, że niektóre inne listy przynoszą nieco gorsze wyniki ...

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

Są one sortowane odpowiednio w 4176 i 94 523 iteracjach, co w rzeczywistości zajmuje więcej niż sekundę ... ale zatrzymajmy ten fakt dla siebie, aby nikogo nie odwracać uwagi od tego, jak niesamowity jest ten algorytm!

Edytować:

Poproszono mnie o udowodnienie skuteczności mojego algorytmu na liście 100 pozycji, więc proszę:

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

Nawet ta długa i całkowicie dowolna lista jest natychmiast sortowana! Naprawdę musiałem natknąć się na najlepszy algorytm sortowania na świecie!

Jeśli możesz tworzyć własne dane, jest to dość proste - uzyskaj dane, które wyglądają losowo, ale zawierają klucz do szybszego sortowania. Wszystkie inne dane używają oryginalnej metody sortowania, więc średni czas jest lepszy.

Jednym prostym sposobem jest upewnienie się, że każdy element danych ma unikalny klucz, a następnie po prostu skróty kluczy. Weźmy na przykład listę z liczbami od 1 do 10 000, wszystkie pomnożone przez 16 i dodaną do niej losową liczbę od 0-15 (patrz fillArray () poniżej). Będą wyglądać losowo, ale każdy z nich ma unikalny klucz sekwencyjny. Aby posortować, podziel przez 16 (w C >> 4 jest bardzo szybki), a następnie po prostu umieść liczbę w tablicy, używając uzyskanego klucza jako indeksu. Jedno przejście i gotowe. Podczas testów odkryłem, że Quicksort był 30 razy wolniejszy przy dziesięciu milionach liczb.

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

Wszystko, co ma unikalny klucz, można posortować w ten sposób - oczywiście jeśli masz pamięć do przechowywania. Na przykład wiele baz danych używa unikalnego numerycznego identyfikatora klienta - jeśli lista jest wystarczająco mała / sekwencyjna, może być przechowywana w pamięci. Lub inny sposób na przetłumaczenie rekordu na unikalny numer. Aby uzyskać więcej informacji, sprawdź Hash Sorts, ponieważ to właśnie to ...