Alcune domande di smistamento

Question

Ho trovato un modo che migliora (per quanto ho testato) al momento l'algoritmo quicksort al di là di ciò che è già stato fatto. Sto lavorando su testarlo e poi voglio ottenere la parola su di esso. Tuttavia, apprezzerei un certo aiuto con alcune cose. Così qui sono le mie domande. Tutto il mio codice è in C ++ per la via.

1. Una delle specie che ho a confronto alla mia Quicksort è la std :: sort dalla libreria standard C ++. Tuttavia, sembra essere estremamente lento. Sto solo l'ordinamento array di int e long, ma sembra essere di circa 8-10 volte più lento rispetto sia il mio Quicksort ed un Quicksort standard con Bentley e McIlroy (e forse Sedgewick). Qualcuno ha qualche idea sul perché essa è così lento? Il codice che uso per il genere è solo std :: sort (a, a + numelem); dove a è la matrice di lunghi o int e numelem è il numero di elementi nella matrice. I numeri sono molto casuale, e ho provato dimensioni differenti così come diverse quantità di elementi ripetuti. Ho anche provato qsort, ma è ancora peggio come mi aspettavo. Edit: ignorare questa prima domanda - che è stato risolto

.

2. Mi piacerebbe trovare più buone implementazioni Quicksort da confrontare con la mia quicksort. Finora ho uno Bentley-McIlroy e ho anche confrontato con la prima versione pubblicata di quicksort dual-perno di Vladimir Yaroslavskiy. Inoltre, ho intenzione porting timsort (che è una sorta di unione Credo) e ottimizzato quicksort doppio perno dalla sorgente JDK 7. Quali altri quicksorts buona implementazioni ne sai? Se non sono in C o C ++ che potrebbe essere a posto perché io sono abbastanza bravo a porting, ma io preferirei C o C ++ quelli se si sa di loro.

3. Come mi consiglia di uscire la parola circa le mie aggiunte al Quicksort? Finora il mio quicksort sembra essere significativamente più veloce di tutti gli altri quicksorts che ho provato contro. La principale fonte di sua velocità è che gestisce elementi ripetuti in modo più efficiente rispetto ad altri metodi che ho trovato. Si elimina quasi completamente il comportamento peggiore dei casi senza aggiungere molto tempo a controllare per gli elementi ripetuti. Ho pubblicato a questo proposito sul forum di Java, ma ho ottenuto alcuna risposta. Ho anche provato a scrivere a Jon Bentley perché stava lavorando con Vladimir sul suo quicksort dual-pivot e non ho ricevuto risposta (anche se non era terribilmente sorpreso da questo). Dovrei scrivere un documento su di esso e metterlo su arxiv.org? Devo inviare in alcuni forum? ci sono alcune mailing list a cui devo inviare? Ho lavorato su questo per qualche tempo e il mio metodo è legittimo. Io ho una certa esperienza con la pubblicazione della ricerca, perché io sono un dottorando in fisica computazionale. Dovrei provare avvicina qualcuno nel reparto informatica della mia università? A proposito, ho anche sviluppato un diverso Quicksort dual-pivot, ma non è meglio del mio singolo perno quicksort (anche se è meglio di quicksort dual-perno di Vladimir con alcuni set di dati).

Apprezzo molto il vostro aiuto. Voglio solo aggiungere quello che posso per il mondo informatico. Io non sono interessato a brevettare questo o qualsiasi cosa assurda come quella.

Answer 1

Se si ha fiducia nel vostro lavoro, provare a discutere con qualcuno esperto nella vostra università al più presto possibile. Non è sufficiente a dimostrare che il codice corre più veloce di un altro procedimento sulla vostra macchina. Devi dimostrare matematicamente ciò che guadagno di prestazioni si pretende di aver raggiunto attraverso l'analisi del vostro algoritmo. Direi che la prima cosa da fare è assicurarsi che entrambi gli algoritmi si confrontano sono implementate e compilati in modo ottimale - si può solo essere ingannare se stessi qui. La probabilità di un individuo ottenere tale un netto miglioramento su simile metodo di ordinamento importante senza avere già conoscenza delle sue varianti accettate sembra proprio minuscola. Tuttavia, non lasciate che vi scoraggi. Dovrebbe essere comunque interessante. Sareste disposti a pubblicare il codice qui? ... Inoltre, dal momento che quicksort è particolarmente vulnerabile a scenari peggiori, i test si sceglie di eseguire possono avere un effetto enorme, così come la scelta di perni. In generale, direi che tutti i set di dati con un numero elevato di elementi equivalenti o uno che è già altamente ordinati non è mai una buona scelta per il Quicksort - e ci sono già modi ben noti di lotta contro questa situazione, e migliori metodi di ordinamento alternativi .

Answer 2

Se si è veramente fatto un passo avanti e hanno la matematica per dimostrarlo, si dovrebbe cercare di ottenere la pubblicazione nella Journal of the ACM . E 'sicuramente una delle riviste più prestigiose per l'informatica.

Il secondo migliore sarebbe una delle IEEE riviste come < a href = "http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=32" rel = "nofollow"> noreferrer Operazioni su Software Engineering .