Binäre Suche über eine Liste von Paaren

Question

Ich muss elem finden, die element entsprechen würde.
Mein Programm funktioniert, aber es ist nicht effizient. Ich habe eine sehr große ArrayList<Obj> pairs (mehr als 4000 Elemente) und ich benutze eine binäre Suche, um passende Indizes zu finden.

public int search(String element) { 
    ArrayList<String> list = new ArrayList<String>(); 
    for (int i = 0; i < pairs.size(); i++) { 
     list.add(pairs.get(i).getElem()); 
    } 
    return index = Collections.binarySearch(list, element); 
} 

Ich frage mich, ob es eine effizientere Art und Weise ist eine Schleife als die Verwendung der Hälfte der Arraylist-Paare in eine neue Arraylist Liste zu kopieren. Constructor für Obj: Obj x = new Obj(String elem, String word);

Answer 1

Es sieht aus wie das Problem gelöst ist. Da mein Problem war, dass ArrayList-Paare Typ war Obj und element Typ String war, konnte ich nicht Collections.binarySearch verwenden, entschied ich mich, eine neue Variable Obj x = new Obj(element, ""); zu erstellen. Es sieht so aus, als ob die Zeichenfolge keine Probleme verursacht (sie hat meine JUnit-Tests bestanden), da meine Methode compareTo zwei elem s vergleicht und die zweite Variable Obj x ignoriert.

Meine aktualisiert Methode:

public int search(String element) { 
    Obj x = new Obj(element, ""); 
    int index = Collections.binarySearch(pairs, x); 

Answer 2

Wenn Ihre Masterliste (pairs) ändert sich nicht, dann würde ich empfehlen, ein TreeMap Schaffung index Struktur beizubehalten zu umkehren, zum Beispiel:

List<String> pairs = new ArrayList<String>(); //list containing 4000 entries 

Map<String, Integer> indexMap = new TreeMap<>(); 

int index = 0; 
for(String element : pairs){ 
    indexMap.put(element, index++); 
} 

Jetzt, während für ein Element gesucht alles, was Sie tun müssen, ist:

indexMap.get(element); 

das gibt Ihnen die erforderliche index oder null, wenn das Element nicht e tut xist. Wenn ein Element mehrere Male in der Liste vorhanden sein kann, können Sie auch die indexMap in Map<String, List<Integer>> ändern.

Ihr aktueller Algorithmus iteriert die Liste und ruft die binäre Suche, so würde die Komplexität O(n) für Iteration und O(log n) während TreeMap Garantien log(n) Zeitkosten sein, so wird es viel schneller sein.

Here ist die Dokumentation von TreeMap.