Sto tentando di creare una lista che dovrebbe essere ordinata per un particolare campo in una stringa separata da due punti. Ho una matrice di stringhe con i seguenti valori:
name1:535
name2:697
Dopo aver ordinato questo elenco, lo avrei ordinato in base al numero nel secondo campo:
name2:697
name1:535
Come dovrei andare a fare questo, ci sono dei problemi di cui dovrei essere a conoscenza quando ordina questo elenco di stringhe?
La risposta ingenua è di avere un tipo con un valore String in esso che lavori in compareTo() dall'interfaccia comparabile.
Il codice sarebbe simile a questo ...
Il problema con questo è che sta facendo molto più lavoro del necessario. Un semplice test:
public class Thingy implements Comparable<Thingy> {
double value;
public Thingy(double arg) {
value = arg;
}
@Override
public int compareTo(Thingy thingy) {
Global.count++;
return Double.valueOf(value).compareTo(thingy.value);
}
}
public class Global {
public static int count;
}
public class Main {
public static void main(String[] args) {
ArrayList<Thingy> things = new ArrayList<Thingy>();
for(int i = 0; i < 1000; i++) {
things.add(new Thingy(Math.random()));
}
Collections.sort(things);
System.out.println(Global.count);
}
}
mostra che compareTo() è stato chiamato 9015 volte. Se si esegue un calcolo ripetuto in compareTo() , viene chiamato molto più del necessario e il lavoro svolto non è necessario.
Provenendo da uno sfondo perl, una delle chiamate idiomatiche è la trasformazione di Schwartzian - l'ordinamento basato su un calcolo "è qualcosa che viene rapidamente riconosciuto. In questo codice, uno:
@sorted = map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, split($_)[0]] }
@unsorted;
Mentre il confronto viene chiamato più volte, viene eseguito su un valore memorizzato anziché su un valore (re) calcolato. Vedi anche Memoization .
In Java, è probabile che il costruttore della classe spezzi la stringa verso l'alto nelle parti del componente e ordina in base alle parti anziché all'intero.
Se hai a che fare con valori univoci da ordinare (il bilanciamento non è probabilmente unico ma lo spiegherò comunque), si potrebbe usare un SoldMaps - inserisci solo la chiave e il valore. Se la chiave ha già un ordinamento naturale (numeri interi, stringhe e simili), non è necessario più lavoro. Hai una struttura ordinata che ha un bel po 'di cose aggiuntive che potresti trovare utili quando ne hai bisogno (che in realtà provengono da NavigableMap , ma TreeMap e SkipListMap sono una NavigableMap oltre a essere una SortedMap).
Un potrebbe creare un TreeMap con il costruttore che passi un Comparator<String> in (javadoc per il costruttore
e javadoc per Comparator ) e fanno il lavoro sulla stringa da fare l'ordinamento, anche se questo potrebbe risentire dei problemi di fare calcoli ripetuti nel metodo compareTo() che ho menzionato sopra. (Un esempio in cui non è una TreeMap ordinata ZA come descritto in questa domanda - si ottiene comunque l'idea generale - la soluzione generale può essere vista qui ).
Se ciò che hai non è univoco, puoi ancora usarlo in una struttura SortedMap, solo che il valore invece di essere una stringa è un Set di stringhe.
Questo significa quindi aggiungere due passaggi (se la chiave non esiste, crearla e quindi creare il set, quindi aggiungere il valore al set) e ricerche (se la chiave esiste, controllare se il valore esiste nel set).
Sarebbe sensato avvolgere quel lavoro in una classe a sé stante in modo da non avere copiato il codice boilerplate per fare l'aggiunta multipla e la ricerca in più punti.
Se hai solo una matrice che dovrai ordinare una volta e poi usarla, e farla con essa e l'estensibilità di avere un oggetto (la name:balance rappresenta un oggetto che è più interessante di una semplice stringa), potresti usare il Comparatore menzionato sopra come parametro per Collections.sort(List, Comparator) ( javadoc ). Ricorda che per le liste di dimensioni considerevoli il numero di invocazioni per estrarre il campo da confrontare da un è molto più che calcolarlo una volta e memorizzarlo in un oggetto associato.