Devo utilizzare qualsiasi algoritmo per ordinare / trovare elementi o utilizzare i metodi incorporati di una lingua?

In generale, se la lingua o la libreria standard fornisce una funzione per fare ciò che vuoi, usalo fino a quando, a meno che tu non abbia una ragione specifica, hai bisogno di usare qualcos'altro. Quest'ultimo può accadere, ma è piuttosto inusuale come regola generale.

Ovviamente, in alcuni casi può avere senso considerare alcune vie di mezzo, come scrivere un wrapper che di solito usa la routine standard, ma gestisce alcuni casi d'angolo che non gestisce bene, ma che è importante per il tuo scopo particolare (per un esempio, una volta ho scritto un wrapper per qsort in una libreria standard C perché ha fatto veramente in modo scadente quando è stato richiesto di ordinare una raccolta che conteneva molti elementi duplicati, e ci aspettavamo molti duplicati per la maggior parte del tempo).

Se la libreria standard della tua lingua fornisce una funzione di cui hai bisogno e non hai motivo di credere che ci sia qualcosa di sbagliato nella sua implementazione o API, quindi usa lo standard .

Riuscire a implementare la funzione da soli sarà nel migliore dei casi una perdita di tempo, dal momento che duplicherete il lavoro che altre persone hanno già fatto per voi. Nel peggiore dei casi, la tua versione sarà lenta e buggata perché non avresti quasi tanto tempo nei punti migliori delle implementazioni degli algoritmi di ordinamento come hanno gli implementatori linguistici, e le inevitabili sottili differenze tra la tua versione e quella standard causeranno confusione infinita per altri sviluppatori.

È importante avere un indizio su come questi algoritmi sono implementati, almeno concettualmente, perché è fondamentale capire perché alcuni metodi (come i metodi di ordinamento) hanno i comportamenti, le prestazioni e le API specifici che fanno. Ad esempio, se non si seguono mai un algoritmo e una struttura di strutture dati, non si ha idea del motivo per cui una tabella hash non può essere ordinata (senza copiare tutte le voci in un'altra struttura o utilizzando una terribile funzione hash).

Naturalmente, se c'è davvero qualcosa di sbagliato nella funzione di libreria standard, non hai molta scelta. Ma non è molto comune, e se leggi abbastanza buoni libri / blog / ecc sulla tua lingua di scelta, imparerai presto dove sono i difetti reali e come evitarli.

Mentre il consiglio che viene dato qui di non implementare il proprio algoritmo di ordinamento nel mondo reale è, penso, suona, devi ancora scegliere tra le strutture di dati iniziali, e una lista non è sempre il miglior punto di partenza per l'ordinamento / la ricerca.

Cercare la lista una volta è una cosa, ma la ricerca molte volte è un'altra.

Nell'ultimo caso, l'elenco potrebbe essere meglio trasformato in una struttura di dati orientata alla ricerca (una matrice, una matrice ordinata, un albero, una tabella hash, un albero specializzato, un albero B +, ecc ...) , con molto a seconda dei fattori attorno alla mutevolezza.

In alcuni casi può essere ragionevole caricare i dati in un database e scaricare la ricerca / ordinamento su di esso.

Per me, quando si tratta delle prestazioni delle strutture dati standard e degli algoritmi e degli allocatori di memoria (e l'unico motivo per utilizzare l'uno o l'altro in genere è per le prestazioni), sono piuttosto facili da battere se la soluzione è meno generalizzata rispetto alla libreria standard, ed è quasi impossibile da battere quando si tenta di soddisfare esattamente gli stessi requisiti.

Ad esempio, è molto difficile battere std::sort in C ++ se si desidera un ordinamento di confronto generalizzato (almeno a meno che non si utilizzi una versione parallelizzata). Tuttavia, puoi facilmente battere std::sort se usi anche un ordinamento naïve di tipo radix che funziona solo su numeri interi o puntatori.

Allo stesso modo, in genere si è in difficoltà a superare l'efficienza del malloc di C se si desidera un allocatore thread-safe generico in grado di gestire allocazioni di dimensioni variabili e blocchi di memoria singoli. Ma puoi facilmente batterlo se usi una lista libera che può solo raggruppare blocchi di una dimensione specifica ed è progettata per essere usata da un thread alla volta, o un allocatore sequenziale che si raggruppa in modo sequenziale e non t offrire la possibilità di liberare i pezzi singolarmente.

Sarà estremamente difficile, se non impossibile, battere std::vector in C ++ in tutti i casi pur soddisfacendo requisiti identici. Ma è abbastanza facile batterlo per una sequenza che è specificatamente ottimizzata per memorizzare solo, per esempio, da 0 a 8 elementi.

Allo stesso modo è improbabile che il HandRolledArrayList<Float> superi la ArrayList<Float> in Java. Ma puoi facilmente sovraperformare se usi semplicemente una matrice di float invece.

E se lavori in un'area veramente critica in termini di prestazioni in cui esegui il ciclo di milioni di cose e / o hotspot scoperti attraverso la misurazione, a volte può pagare per implementare una struttura di dati o un allocatore o un algoritmo in concorrenza con fornito nella libreria standard, ma in genere solo se l'implementazione è di gran lunga meno generale dei requisiti che gli implementatori di libreria standard dovevano soddisfare.