Qual è il modo più efficiente per inserire una stringa in un elenco di stringhe già ordinato?

Question

Ho una lista array contenente 17.000 parole. Ho bisogno di aggiungere una parola alla lista solo se non è già in e ho bisogno di preservare l'ordinamento della lista. vale a dire, ho bisogno di metterlo nella sua posizione alfabeticamente corretta.

Non so come trovare il posto giusto per inserirlo. Sto usando una ricerca binaria per scoprire se la parola è già nella lista e che restituisce l'indice se è lì o -1 se non lo è. Stavo pensando di usare ArrayList.add (int index, E element) per metterlo in.

Answer 1

binary search viene in mente, la lista api potrebbe contenere meglio però

In una ricerca binaria si arriva a un punto in cui sono rimasti 2 elementi, uno sopra e uno sotto, con uno di essi probabilmente == sul tuo oggetto. Per il tuo caso non avrai il caso ==, quindi restituisci l'indice di quello superiore e inseriscilo nella sua posizione. Non so se java ha una classe di tuple, o puoi costruire un container. In entrambi i casi, restituire qualcosa di simile:

(bool, int) binSearch(IList list) 
    returns true, -1 if found 
    returns false, higher of 2 bounds otherwise 

, ovviamente, questo non è Java, ma non è un tratto di convertire

Answer 2

Se hai scritto la ricerca binaria si potrebbe modificarlo per restituire l'ultimo valore cercato. Questo valore può essere la posizione della stringa corrispondente o il percorso in cui deve essere inserito.

In una ricerca binaria, si suddivide l'elenco finché non si trova la stringa o non è possibile suddividerla ulteriormente. Quella posizione in cui non è più possibile suddividere l'elenco è la posizione in cui deve essere inserita la stringa.

Answer 3

Per fissare un processo, l'idea generale viene in mente è quella di utilizzare più memoria, come tutti sappiamo. Qui, può essere l'indice delle prime stringhe per ogni lettera. Per esempio un ArrayList ulteriore, scrivendo in pseudo:

ArrayList indexes; 
indexes[0] = {"a", 0}; 
indexes[1] = {"b", 123}; 
... 

Per una stringa che inizia con "a", si può fare una ricerca binaria tra gli indici 0-123.

Answer 4

Utilizzare il metodo integrato binarySearch. Se la chiave non viene trovata, il numero restituito è
-(insertionIndex) - 1

Answer 5

Se non ci sono parole ripetute, come dici tu, potresti prendere in considerazione l'implementazione di trie. Le operazioni di inserimento su un trie sono un po 'più veloci che in una tabella hash, perché non ci sono collisioni. Lo stesso vale anche per la ricerca.

Inoltre, in un ArrayList per inserire un elemento nel mezzo dell'elenco, questo significa riposizionare la metà degli elementi o aumentare la dimensione dell'array, che potrebbe essere un po 'dispendiosa.

Se siete curiosi, potete vedere un'implementazione nella seguente pagina: https://forums.oracle.com/forums/thread.jspa?messageID=8787521

Answer 6

Convertire il ArrayList in un TreeSethttp://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

Il TreeSet si prenderà cura di duplicati per voi, e tenere le parole in ordine alfabetico.

Esempio: (WordList è la ArrayList di parole)

TreeSet<String> WordSet = new TreeSet<String>(WordList);