qsort() vs std :: sort, funzione di confronto differenza filosofica

Question

Mi chiedevo perché ci sono due approcci completamente diversi per specificare la funzione di confronto in qsort() {versione C} rispetto allo std::sort().

qsort richiede la funzione di confronto come di seguito: non conosco il motivo per cui ha bisogno di tre tipi di valori di ritorno -1, 0, +1.

int comp(int *x, int *y){ 
    return *x - *y; 
} 

mentre la funzione di confronto per std::sort(), che sembra più coerente a me, come è scritto in termini di funzione segue un invariante. cioè se x è minore di ritorno funzione y vero, x è nella giusta posizione rispetto alla y

bool comp(int x, int y){ 
     return x < y; 
} 

Perché una tre valori -1,0, + 1 quando restituisce un bool (int o con due valori 0, 1) è molto più semplice e pulito?

Answer 1

Altri hanno sottolineato l'equivalenza dei due modi di fare paragoni; ecco perché i due approcci sono seguiti.

In C, il confronto deve essere un puntatore a funzione. Ciò significa che si ottengono sempre overhead della funzione call e pointer indirection. Quando qsort è stato progettato negli anni '70 su un computer PDP-11, la quantità di spese generali doveva essere ridotta, pertanto le funzioni di confronto come strcmp eseguivano un confronto a tre in una singola chiamata di funzione. (Si noti che qsort è generalmente un ordinamento instabile, per cui il caso uguaglianza può sembrare inutile, ma può essere reso stabile con le opportune comparazioni puntatore.)

In C++, il confronto può essere inlined al momento istanziazione di template, tanto l'overhead è sparito (non c'è bisogno nemmeno di una chiamata di funzione) e può essere utilizzata la convenzione più semplice. Ciò significa anche che std::sort può funzionare con sovraccarichi operator< per impostazione predefinita.

Answer 2

Mi chiedevo la stessa cosa e mi è venuta in mente una teoria basata su strcmp e std::string::compare. Vale a dire, fare un confronto può richiedere un tempo relativamente lungo. Per determinare se un oggetto A è minore, uguale o maggiore di un altro oggetto B, è possibile utilizzare:

if (A < B) { 
    //do stuff where A is less 
} else if (B < A) { 
    //do stuff where A is greater 
} else { 
    //do stuff where A is equal 
} 

che richiede normalmente l'iterazione di A e B deve essere fatto due volte, una volta per A<B e una volta per B<A . Se controlli tutte e tre le possibilità allo stesso tempo, devi solo scorrere le stringhe una volta sola. Pertanto è stata utilizzata la convenzione -1, 0, 1.

Tuttavia, C++ sembra aver abbandonato questa convenzione. Un argomento che ho sentito è che i computer sono cambiati e, a causa della complessità del codice per fare il confronto a tre, fare un confronto a tre è più lento e più soggetto a errori, e il più delle volte non ci importava il caso di uguaglianza. In effetti, tutti gli algoritmi di ordinamento standard sono progettati per funzionare in questo modo, anche se un'implementazione individuale potrebbe fare qualcosa di più interessante.

if (A < B) { 
    //do stuff where A is less 
} else { 
    //do stuff where A is greater or equal 
} 

Secondo timing di MSVC su this test, string::operator< è quasi due volte più veloce strcmp, e chiamando string::operator< due volte è stato solo leggermente più lento di farlo una volta. (Caching e codice più semplice, immagino?). I risultati di GCC sono simili.

Answer 3

Se per qualsiasi due xe y, x < yo x == yo x> y è valido, quindi due modi di dare la funzione di confronto sono equivalenti. Si può definire ==> e operatori in termini di < come segue:

• x == y è equivalente (x < y) & & (y < x)
• x> y è equivalente! ay < x

Come si può capire, è generalmente più efficiente (e più semplice) per implementare <, < =, ==,> = e> in termini di tre vie confrontare operazione, quindi imple menting == in termini di < come mostrato sopra.Penso che dovrebbe essere la ragione per cui C (e molti altri linguaggi in realtà) hanno scelto la funzione di confronto a tre, anche se quicksort potrebbe non sfruttare tali informazioni extra.

C++ ha overload degli operatori, ma non a tre vie confrontare operatore (non ha né C), in modo da passare da tre vie confrontare all'operatore 'meno' (nonostante i suddetti potenziali inconvenienti sopra) permette di sfruttare operatore sovraccarico.

Answer 4

La funzione di confronto qsort è modellato strcmp e memcmp, che restituiscono < 0, 0, o> 0 ... che è più informazioni che appena restituire un < o> = indicatore ... ci vogliono due di chiamate a determinare se due elementi sono uguali. La nozione di "invariante" non si applica qui: ovviamente l'invariante che un [i] < a [i + 1] non si applica all'array originale ... in effetti non si applica all'array finale perché [i] == a [i + 1] è possibile. Né si applica il termine "coerente" ... i risultati sono e devono essere coerenti per entrambi i tipi di funzioni di confronto. "più pulito" è negli occhi di chi guarda, e "molto più semplice" è un'esagerazione.

Answer 5

C'è una discussione interessante su questo: https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/bgGrHG_Y_Pw