Welche Nachteile gibt es leistungsmäßig, wenn ich ein Array mit Hashing sortiere?

Question

Ich schrieb eine einfache Funktion, um ein Array int a[]; mit Hash zu sortieren. Dafür habe ich die Frequenz für jedes Element im neuen Array hash1[] gespeichert und dann in der linearen Zeit in das ursprüngliche Array zurückgelegt.

#include<bits/stdc++.h> 
using namespace std; 
int hash1[10000]; 
void sah(int a[],int n) 
{ 
    int maxo=-1; 
    for(int i=0;i<n;i++) 
    { 
     hash1[a[i]]++; 
     if(maxo<a[i]){maxo=a[i];} 
    } 
    int i=0,freq=0,idx=0; 
    while(i<maxo+1) 
    { 
     freq=hash1[i]; 
     if(freq>0) 
     { 
      while(freq>0) 
      { 
       a[idx++]=i;freq--; 
      } 
     } 
     i++; 
    } 
} 
int main() 
{ 
    int a[]={6,8,9,22,33,59,12,5,99,12,57,7}; 
    int n=sizeof(a)/sizeof(a[0]); 
    sah(a,n); 
    for(int i=0;i<n;i++) 
    { 
     printf("%d ",a[i]); 
    } 
} 

Dieser Algorithmus läuft in O (max_element). Welche Art von Nachteilen habe ich hier nur hinsichtlich der Leistung (Zeit und Raum)?

Answer 1

Der von Ihnen implementierte Algorithmus heißt counting sort. Seine Laufzeit ist O (n + U), wobei n die Gesamtzahl der Elemente und U der Maximalwert im Array ist (vorausgesetzt, die Zahlen gehen von 0 bis U) und die Speicherbelegung ist Θ (U). Ihre spezielle Implementierung setzt voraus, dass U = 10.000 ist. Obwohl Sie Ihren Ansatz als "Hashing" beschrieben haben, ist dies wirklich kein Hash (Berechnung einiger Funktion der Elemente und Verwendung, um sie in Eimer zu setzen) als Verteilung (Verbreitung Elemente nach ihren Werten herum).

Wenn U eine feste Konstante ist - wie es in Ihrem Fall ist - dann ist die Laufzeit O (n) und die Raumnutzung ist O (1), aber denken Sie daran, dass Big-O über langfristige Wachstumsraten und Wenn U groß ist, kann die Laufzeit ziemlich hoch sein. Dies macht es attraktiv, wenn Sie sehr große Arrays mit einem eingeschränkten Wertebereich sortieren. Wenn der Wertebereich jedoch groß sein kann, ist dies kein besonders guter Ansatz. Interessanterweise kann man sich radix sort als einen Algorithmus vorstellen, der wiederholt das Zählen der Sortierung mit U = 10 (bei Verwendung der 10er-Ziffern der Zahlen) oder U = 2 (bei binärem Durchlauf) und einer Laufzeit von O (n log U), was für große Werte von U sehr zu bevorzugen ist.

Sie können diesen Code auf verschiedene Arten bereinigen. Zum Beispiel haben Sie eine if Anweisung und eine while Schleife mit der gleichen Bedingung, die zu einer einzigen while Schleife kombiniert werden können. Sie können auch einige Assert-Prüfungen durchführen, um sicherzustellen, dass alle Werte im Bereich von 0 bis 9.999 liegen, da sonst ein Begrenzungsfehler auftritt. Darüber hinaus könnten Sie in Betracht ziehen, das globale Array entweder als lokale Variable (obwohl Sie Ihre Stack-Nutzung überwachen) oder als lokale Variable static zu verwenden (um den globalen Namespace nicht zu belasten). Sie können den Benutzer alternativ einen Parameter übergeben lassen, der die maximale Größe angibt, oder ihn selbst berechnen lassen.

Answer 2

Fragen können Sie prüfen:

• Input-Validierung. Was passiert, wenn der Benutzer -10 oder einen sehr großen Wert eingibt?
• Wenn das maximale Element groß ist, erhalten Sie irgendwann einen Leistungseinbruch, wenn der L1-Cache erschöpft ist. Das hash1 -array konkurriert um die Speicherbandbreite mit dem a -array. Wenn ich Radix-Sortierung in der Vergangenheit implementiert habe, fand ich heraus, dass 8 Bits pro Iteration am schnellsten waren.
• Die Zeit Komplexität ist eigentlich O (max_element + Anzahl_der_ Elemente). Z.B. Was, wenn Sie 2 Millionen Einsen oder Nullen sortiert haben. Es ist nicht so schnell wie das Sortieren von 2 Einsen oder Nullen.