ArrayList Expertenfrage

[Zwiebelsalat]

Achtung Experten oder sonstigen, die ihr mir helfen könnt:

Wie bekomme ich in einer ArrayList mit vielen vielen Strings drinne, den ersten Index zurück, an dem der dort abgelegte String mit einem bestimmten Wert anfängt ? (die Liste ist nummerisch sortiert)


Ich habe einen String "888999"

in der ArrayList sind ab index n alle Werte die mit 8 anfangen, dieser Index soll als Einsprungspunkt für eine Schleife dienen und diesen Einsprungspunkt möchte ich über die erste Stelle des Strings (8) herausfinden.

 

[Wildcard]

Iterieren und prüfen, muss man kein Experte für sein :wink:

 

[Gelöschtes Mitglied 5909]

In meinem besoffenen zustand würde ich des jetzt so mahcen:

List<String> list = new ArrayList<String>();
List.add("Adam");
//...

public static int getLetterIndex(List<String> list, char searchLetter)
{

	Iterator<String> iter = list.iterator();
	String element;
	int i = 0;
	
	for (; iter.hasNext(); i++, element = iter.next())
	{
		if (element.charAt(0) == searchLetter)
		{
			break;
		}
	}
	return i;
}

// ab wann gehts mit F los?

int index = getLetterIndex(list, 'F');

String nameMitF = list.get(index);

geht aber sicher eleganter denk ich

 

[Zwiebelsalat]

Jo. Das Problem ist halt, dass in der Liste 4000 Einträge sind und die Methode auch zig mal aufgerufen wird und Performance hier sehr wichtig ist und bisher war es so, dass ich immer wieder für den zu untersuchenden String von 0 bis arraylist.size() angefangen habe mit der Suche und dann bei einem Treffer ein break gesetzt habe.
Ich habe gestern noch von einem Kollegen einen Tip bekommen und das ist schon mal eine deutliche Verbesserung.

public String check(String string) {

     int a = Integer.parseInt(string.charAt(0)+"");

     if(a < 5)     {
          for(int i = 0;i<2553;i++){
            Suche hier...
             breaK;
         }        
     }
     else  {

       for (int j = arrayList.size();j>2553;j--) {
             Suche hier..
             break;
       }
    }
}

Kann man das noch weiter verfeinern. Wie sieht es da mit irgendwelchen Suchen oder Sortieralgorithmen aus?

 

[byte]

Du kannst die Performance verbessern, indem Du die Liste zunächst sortieren lässt:

Collections.sort(liste);

Da Deine Liste ja offenbar nur Strings enthält, brauchst Du auch keinen eigenen Comparator mit angeben. Danach kannst Du mittels Binary Search in log(n) Zeit suchen:

Collections.binarySearch(liste, string);

Beachte aber, dass Du - falls Du die Liste nach dem Sortieren nochmal veränderst - die Sortierung erneut durchführen musst. Die Sortierung dauert auch mit n*log(n) entsprechend länger. Die Lösung ist also nur dann zu empfehlen, wenn die Liste zur Laufzeit mehr oder weniger konstant bleibt und sich nicht verändert.

Ansonsten würde ich mal über eine andere Collection nachdenken, z.B. ein TreeSet. Da werden die Elemente schon beim hinzufügen einsortiert. Du musst also nicht explizit sortieren und hast immer schnelleren Zugriff, wenn Du mit contains() prüfst. Dafür dauert die add() aber z.B. länger als bei Listen...

 

[podi]

Hallo, die Liste ist schon sortiert und bleibt immer konstant!

Collections.binarySearch(liste, string);

Das hört sich gut an!
Ich guck mir das mal an.

 

[Zwiebelsalat]

Wow, Collections.binarySearch rockt. Die Methode schafft nun auf meiner lokalen 1 Ghz Kiste 100 000 Operationen in ca 9 Sekunden im Vergleich zu 13 Sekunden vorher und ca 20 Sekunden am Anfang.

Lasst uns einen Salat zubereiten.

Ähh, welche Aussage kann man über die Laufzeit machen ?? O(log n) ?

 

[Wildcard]

Ja, O(log n).
Bei solchen Fragen einfach in die API schauen