Mantenimento della velocità di array ordinato

Question

Mantenimento della velocità di array ordinato

#1 da (3 voti)

0

Ho un ciclo for in esecuzione su un elenco di oggetti come:

[{a: 2001, b: "hello"}, {a: 54, b: "hi"}....]

In questo ciclo, estrai gli oggetti in base a determinati valori di campo (come, b == hello?) e creo un nuovo elenco di oggetti filtrati. Una volta completato il ciclo for, seleziono gli oggetti rimanenti in base al valore di a. Questo è un esempio semplicistico, quindi la presortazione per campo a non è possibile.

La mia domanda è, è più veloce fare l'ordinamento dopo che il ciclo è completo, facendo qualcosa come una ricerca binaria alla fine di ogni iterazione e poi inserire l'oggetto? Ciò eviterebbe l'ordinamento alla fine, ma non so davvero se questo finisca per costare di più.

sorting

posta tonyl7126 28.04.2014 - 02:39

fonte

1 risposta

Leggi altre domande sui tag sorting

È buono controllare esplicitamente per null nei test unitari? Strategia per mantenere in sicurezza il repository offline usando git [closed]

score 3 · Accepted Answer

In generale, è più veloce costruire prima un insieme di valori, quindi ordinare. Se inserisci un contenitore ordinato, pagherai il prezzo per il mantenimento di una raccolta ordinata (che, a seconda dell'implementazione sottostante potrebbe richiedere ~2 lg n confronti, o, come sembra implicare dicendo "ricerca binaria", ~lg n confronta e poi ~n/2 swap).

Se, al contrario, memorizzi semplicemente i tuoi articoli in modo non ordinato e poi ordina, consenti agli algoritmi più veloci di ordinare tutti gli elementi alla fine per ~n lg n confronti, che, se ammortizziamo su n di elementi che hai inserito, questo metodo richiederebbe un costo di ~lg n per ogni elemento (e meno swap), più economico di entrambe le opzioni per il mantenimento della raccolta ordinata.

Ovviamente, la profilazione ti dirà sempre cosa funziona meglio sulla tua macchina. Tuttavia, per set di dati sufficientemente grandi, sarebbe meglio filtrare, quindi ordinare.

Nota minore : tecnicamente, quando si inserisce in un contenitore ordinato, le operazioni non dipenderanno dal numero totale di elementi n ma piuttosto il numero corrente di elementi k , aumentando da 1 a n . Tuttavia, il costo medio per queste operazioni risulta essere ~lg n all'interno di un fattore costante - vedi Approssimazione di Stirling .