Suche Performanceoptimierung bei Stringsortierung

[FerFemNemBem]

Halloechen,

ich brauche in meinem Programm folgendes Konstrukt: Gegeben ist eine Anzahl von Strings, Ziel soll es sein in der Ausgabe die Strings alphabetisch zu sortieren, allerdings mit der entsprechenden Zuordnung zur Position in der Stringliste.

Abstrakt sieht das wie folgt aus:
String[] strings={"ABBA","VOLVO","BITTE","ANTWORT"};

das Ergebniss soll sein:
0: ABBA
3: ANTWORT
2: BITTE
1: VOLVO

Ich habe dazu in etwa folgendes gebastelt:

import java.text.CollationKey;
import java.text.Collator;
import java.util.ArrayList;
import java.util.TreeMap;

public class Main
{
	public static void main(String[] args) 
	{
	    String[] strings={"ABBA","VOLVO","BITTE","ANTWORT","ZETTEL","ABWASCH","KLEIN","HUT","FENSTER"};
	  
	    TreeMap<CollationKey, Integer> treeMap = new TreeMap<CollationKey, Integer>();
	  
	    Collator collator = Collator.getInstance();
	    collator.setStrength(Collator.PRIMARY);
	
	    for(int position=0; position<strings.length; position++)
	    {
	        treeMap.put(collator.getCollationKey(strings[position]), position);
	    }
	
	    int[] sortiert = getIntArrayFromTreeMap(treeMap);
	  
	    for(int i=0; i<sortiert.length; i++)
	    {
	        System.out.println(sortiert[i]+": "+strings[sortiert[i]]);
	    }
	}
	  
	static int[] getIntArrayFromTreeMap(TreeMap<? extends Object,Integer> treeMap)
	{
	    ArrayList<Integer> arrayList = new ArrayList<Integer>();
	    arrayList.addAll(treeMap.values());        
	    
	    int[] indexEntries = new int[arrayList.size()];
	
	    for(int i=0; i<arrayList.size(); i++)
	    {
	        indexEntries[i] = arrayList.get(i).intValue();
	    }
	    return indexEntries;
	}
}

Da ich das "im wirklichen Leben" mit vielen hunderttausend Strings machen muss, suche ich nun nach einer kostenguenstigeren Alternative.

Hat jemand eine Idee, wie ich das Problem schneller loesen kann?

Danke!

Gruss, FFNB.

 

[Ark]

Hast du es denn schon mal mit vielen Strings probiert? Hast du gemessen, wie lange das dauert? Ist es wirklich ein Problem?

Du weißt aber schon, dass in deinem bisherigen Lösungsansatz TreeMap alle doppelten Schlüssel entfernt!? Bist du dir sicher, dass das kein Problem ist?

Wenn du da etwas wesentlich schneller machen willst, müsste man das Drumherum genauer beleuchten: Wozu z.B. benötigst du überhaupt die Positionen im Array?

Ark

 

[FerFemNemBem]

Halloechen,

ja, die Performance ist ein Problem. Deswegen frage ich ja hier.

Der Mechanismus ansich ist auch so gefordert und die Funktionalitaet ist Ok. Nun muss genau das nur noch schneller werden...

Ob das geht?

Danke!

Gruss, FFNB.

 

[nrg]

und deine datenhaltung ist ein string-array oder ist das noch offen? für was brauchst du denn nach dem sortieren den index von vor dem sortieren?

 

[FerFemNemBem]

Halloechen,

die Daten kommen aus einer ArrayList mit "Track"-Objekten. Die Strings kommen aus den "Track"-Objekten selbst. Funktionieren tut das schon alles und ich brauche das auch genau so - aber mit der Performance bin ich noch nicht so ganz zufrieden...

Gruss, FFNB.

 

[nrg]

mir würde jetzt das einfallen:

	// TESTMAIN
	public static void main(String[] args) {
		String[] strings={"ABBA","VOLVO","BITTE","ANTWORT","ZETTEL","ABWASCH","KLEIN","HUT","FENSTER"};
		Map<Integer, String> map = getSortedMap(strings);
		for (Entry<Integer, String> entry : map.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}
	}
	
	private static Map<Integer, String> getSortedMap(final String[] array) {
		Map<Integer, String> map = new TreeMap<Integer, String>(new Comparator<Integer>() {
			@Override
			public int compare(Integer i1, Integer i2) {
				return array[i1].compareTo(array[i2]);
			}
		});
		for (int i = 0; i < array.length; i++) {
			map.put(i, array[i]);
		}
		return map;
	}

glaube auch nicht, dass es noch sehr viel schneller geht.

 

[Ark]

die Daten kommen aus einer ArrayList mit "Track"-Objekten. Die Strings kommen aus den "Track"-Objekten selbst. Funktionieren tut das schon alles und ich brauche das auch genau so - aber mit der Performance bin ich noch nicht so ganz zufrieden...

Du musst schon konkreter werden, sonst können wir dir nicht wirklich helfen. Für mich sieht es gerade sehr nach einem schlechten OO-Design aus (falls es da überhaupt ein Design gab).

Kann es sein, dass du so etwas wie [c]java.util.Comparator[/c] bzw. [c]java.lang.Comparable[/c] suchst? Damit kannst du selbst festlegen, nach welchen Kriterien etwas sortiert werden soll, und zusammen mit einem [c]TreeSet[/c] oder [c]TreeMap[/c] oder [c]Collections.sort()[/c] bzw. [c]Arrays.sort()[/c] könnte dein Problem schon gelöst sein. Aber das ist nur eine Vermutung, möglicherweise ist sie komplett falsch! Deshalb: mehr Infos, dann kann dir auch besser geholfen werden.

EDIT: nrg hat wohl so eine ähnliche Vermutung, schau dir das mal an.

Ark

 

[nrg]

ja wobei du dir Ark's Post schon zu Herzen nehmen solltest. Hatte ja auch erst expliziter nachgefragt. Vielleicht könnte man sich das mit einem anderen Design komplett sparen...

 

[FerFemNemBem]

Hallechen,

@nrg: ich werde mal Messungen mit Deiner Methode anstellen.

@Ark: was soll ich noch sagen? Was ich benoetige hatte ich geschrieben, und auch wo es herkommt. Welche Infos benoetigst Du noch? Ich liefere gern, nur wo soll ich anfangen.

Gruss, FFNB.

 

[FerFemNemBem]

Halloechen,

also um konkreter zu werden. In der iTunesDB werden verschiedene Indexe benoetigt, nach denen die Titel auf dem iPod am Ende angezeigt werden. Jeder Track hat eine feste aufsteigende "Position". Um den Index aufzubauen, muss ich nun die Sortierung so wie oben beschrieben aufbauen.

Beispiel:

TrackObjekt: memberPosition=0, memberTitel="ABBA"
TrackObjekt: memberPosition=1, memberTitel="VOLVO"
TrackObjekt: memberPosition=2, memberTitel="BITTE"
TrackObjekt: memberPosition=3, memberTitel="ANTWORT"

der Index, den ich aufbauen muss, muss dann "0,3,2,1" beinhalten.

Gruss, FFNB.

 

[nrg]

glaube auch nicht, dass es noch sehr viel schneller geht.

ich korrigiere mich lieber bevor das hier in einem Battle ausartet . das ist die schnellste Lösung mit sehr wenig Code. Natürlich könnte das noch mit einem eigenen Sortieralgorithmus, der ohne Autoboxing etc. zurecht kommt, schneller gehen. Aber das ist dann imho nicht wirklich signifikant.

 

[FerFemNemBem]

Halloechen,

von mir aus auch gern ein Battle, wenn das in der schnellstmoeglichen Indexerstellung reslutiert.

Gruss, FFNB.

 

[nrg]

was passt dir jetzt denn daran nicht? das ist schonmal ca. 30x so schnell wie dein Algo und mal rein logisch überlegt, ist das eine einzige Iteration über das Stringarray und ein Treesort mit einem Einzeiler Comparator. Was erwartest du denn noch da rauszuholen?

 

[FerFemNemBem]

Halloechen,

wie kommst Du darauf, das mir daran etwas nicht passt? Aber ein Battle ist doch immer klasse. (Hatte doch nun extre 'nen Smiley drangehangen...)

Die Frage ist jetzt nur, wie es sich bei Deiner Implementierung bei der Sortierung von z.B. russischen oder franzoesischen o.ä. Strings verhaelt. Das macht meines Wissens, der Collator recht ordentlich.

Danke!

Gruss, FFNB.

 

[nrg]

das macht die compareTo von String nicht anders

 

[Ark]

Okay, noch mal Glaskugel: In Wirklichkeit willst du gar keine Strings sortieren. In Wirklichkeit willst du Objekte sortieren, die unter anderem diese Strings enthalten.

Stimmt das, oder ist meine Glaskugel kaputt?

Ark

 

[FerFemNemBem]

Halloechen,

also noch genauer geht es nun nicht. Ich muss String aus den Track-Objekten Sortieren. Ein Track hat z.B. Titel, Album, Artist, Genre etc. und das sind Strings. Und ich muss ueber diese Strings in Bezug auf die Trackposition wie vorher beschrieben Indexe bauen.

Wozu brauchst Du da eine Glaskugel? Du versuchst da irgendwas "reinzuglaskugeln". Das ich Strings sortieren muss, hab ich nun schon 100x geschrieben und das ist nunmal so. Ok, Strings sind auch Objekte - da gehe ich mit.

Ich hatte das ganze im ersten Posting schon soweit runtergebrochen, um den Erklaerbedarf so gering wie moeglich zu halten. Daher ja auch - ich suche eine Optimierung fuer genau das, was ich im ersten Posting geschrieben habe. Nicht mehr und nicht weniger - nur eben schneller.

Gruss, FFNB.

 

[Ark]

Was machst du dann mit den Indizes? Kann es sein, dass du diese Track-Objekte nach verschiedenen Kriterien sortieren willst? Dann benutze verschiedene Comparator-Implementierungen (oder eine semi-dynamische, aber das wird wohl für den Anfang etwas zu kompliziert) und TreeSets.

Das wäre zumindest spontan meine Idee - wenn ich dein Problem so weit richtig aufgefasst habe.

Falls ich dein Problem aber nicht richtig aufgefasst habe: Was genau bezweckst du mit den Indizes? Was soll dann weiter mit denen gemacht werden? Welche Existenzberechtigung haben sie?

Ark

 

[FerFemNemBem]

Halloechen,

ich muss, um mit dem iPod arbeiten zu koennen, die iTunesDB "nachimplementieren" und die benoetigt die Indexe. Die will dann wirklich nur "1,3,6,0,4,2,5" haben und zeigt dementsprechen die Tracks nach deren Position an.

Gruss, FFNB.

 

[Ark]

Wer gibt vor, dass die Strings "ABBA","VOLVO","BITTE" usw. in dieser Reihenfolge auftauchen? Welche Größe hat Einfluss darauf, dass "ABBA" die Nummer 42 etc. bekommt? Steht diese Nummer in einem Objekt? Wenn ja: Was weiß dieses Objekt noch?

Ark

 

[FerFemNemBem]

Halloechen,

genau so wie hier beschrieben. Welche Info fehlt Dir noch?

Gruss, FFNB.

 

[Ark]

Weiter oben hast du noch geschrieben, ein Track habe noch viel mehr Informationen als nur Interpret und Index.

Okay, ich habe ne Ahnung. Wie wäre es damit?

Arrays.sort(meineTrackObjekte, new Comparator<TrackObjekt>() {

	@Override
	public int compare(final TrackObjekt o1, final TrackObjekt o2) {
		return o1.getMemberTitel().compareTo(o2.getMemberTitel());
	}
});

for (final TrackObjekt to : meineTrackObjekte) {
	System.out.println(to.getMemberPosition());
}

Ark

 

[FerFemNemBem]

Halloechen,

ja, aber der Index muss fuer jedes Merkmal (Titel, Artist, Album, Genre etc.) genau so und einzeln aufgebaut werden. Ich hab fuer das Beispiel hier den Titel rausgezogen.

Es geht sozusagen noch immer darum genau den code aus meinem ersten Posting zu optimieren.

Gruss, FFNB.

 

[Ark]

	private static final class AlbumComparator implements
			Comparator<TrackObjekt> {
		@Override
		public int compare(final TrackObjekt o1, final TrackObjekt o2) {
			return o1.getAlbum().compareTo(o2.getAlbum());
		}
	}

	private static final class GenreComparator implements
			Comparator<TrackObjekt> {
		@Override
		public int compare(final TrackObjekt o1, final TrackObjekt o2) {
			return o1.getGenre().compareTo(o2.getGenre());
		}
	}

	private static final class TitelComparator implements
			Comparator<TrackObjekt> {
		@Override
		public int compare(final TrackObjekt o1, final TrackObjekt o2) {
			return o1.getMemberTitel().compareTo(o2.getMemberTitel());
		}
	}

	/**
	 * @param args
	 */
	public static void main(final String[] args) {
		final Set<Comparator<TrackObjekt>> verschiedeneComparator = new HashSet<Comparator<TrackObjekt>>();
		verschiedeneComparator.add(new AlbumComparator());
		verschiedeneComparator.add(new GenreComparator());
		verschiedeneComparator.add(new TitelComparator());

		// […]

		for (final Comparator<TrackObjekt> comparator : verschiedeneComparator) {
			Arrays.sort(meineTrackObjekte, comparator);

			System.out.println("Eine mögliche (andere) Sortierung:");
			for (final TrackObjekt to : meineTrackObjekte) {
				System.out.println(to.getMemberPosition());
			}
			System.out.println();
		}
	}

Dieses Beispiel musst du unter Umständen noch anpassen. Vielleicht ist auch ein TreeSet besser als das mit den Arrays. Vielleicht brauchst du auch eine Liste. Aber das steht erst einmal nicht zur Debatte. Das Stück soll dir erst einmal nur demonstrieren, was möglich ist und wie man das machen könnte. (Wobei das hier nicht wirklich sauber ist; man könnte es noch "besser" machen, von wegen Singletons etc., aber das ist wohl gerade egal.)

Wenn das also in die richtige Richtung geht, wirst du wohl zugeben müssen, dass du - wie vermutet - gar keine Strings, sondern TrackObjekte sortieren willst.

Ark

 

[FerFemNemBem]

Halloechen,

ich muss die Track-Objekte wirklich nicht sortieren! Ich brauche eine "Liste mit Zahlen" - ich schwoere!

Ich brauche nur eine Liste mit integer-Werten die die Trackposition anhand der enthaltenen Titel, Album, Artist oder Genre etc. enthaelt. Die sortiereten Track-Objekte wuerden mir nicht helfen.

Danke!

Gruss, FFNB.

 

[Ark]

Ich brauche nur eine Liste mit integer-Werten die die Trackposition anhand der enthaltenen Titel, Album, Artist oder Genre etc. enthaelt.

Das sysout gegen Ende des Codes gibt doch diese int-Werte in der jeweiligen Reihenfolge aus (je nachdem, welcher Comparator gerade dran ist)!? Du musst auch nicht immer dasselbe Array sortieren, sondern kannst auch mehrere Arrays anlegen, die du dann entsprechend sortierst. Wenn du statt Arrays TreeSets benutzt (denen du jeweils den passenden Comparator im Konstruktor eingeben musst), besteht die jeweilige Sortierung sogar permanent.

Ich habe das im Code oben gerade noch einmal deutlicher hervorgehoben. Wenn es immer noch nicht das ist, was du willst, musst du dich wohl anders ausdrücken oder ich anders lesen/zuhören.

Ark

 

[FerFemNemBem]

Halloechen,

ich brauche den Index wirklich voellig losgeloest von den Track-Objekten. Ich formuliere die "Aufgabe" einfach mal so:

Vorgegeben sind 30.000 Trackobjekte mit einem "Position" (int) und einem "Titel" (String) Feld. Erzeuge Sprachabhaengig und schnellstmoeglich einen int[] index der die Postition des Track-Objektes abhanengig von der Stringsortierung des Track-Objektes enthaelt.

Gruss, FFNB.

 

[Ark]

Ja, und wo widerspricht da gerade mein Beispiel deinen Anforderungen? Wenn du ein int-Array brauchst, dann bastel dir halt eines:

		final int[] ergebnis = new int[meineTrackObjekte.length];
		for (final Comparator<TrackObjekt> comparator : verschiedeneComparator) {
			Arrays.sort(meineTrackObjekte, comparator);

			System.out.println("Eine mögliche (andere) Sortierung:");
			for (int i = 0; i < meineTrackObjekte.length; i++) {
				ergebnis[i] = meineTrackObjekte[i].getMemberPosition();
			}
			// Jetzt hat ergebnis die Indizes in der gewünschten Reihenfolge
			System.out.println(Arrays.toString(ergebnis));
		}

Anstatt die Indizes direkt auszugeben (siehe Code von vorher), werden sie jetzt in ein int-Array geschrieben. Ist das so besser? Wenn du Angst um dein Array meineTrackObjekte hast, leg dir halt vorher eine Kopie von dem Array an.

Ark

 

[FerFemNemBem]

Halloechen,

ich werde Deine Variante auch mal testen. Aber ob das performanter den Index erzeugt als das aus Posting 1... ich teste mal. Da muss ich aber erstmal einiges am Programm umstellen.

Danke!

Gruss, FFNB.

 

[Dow Jones]

Ich habe mir gerade den Quellcode von String.compareTo(...) angesehen - und das lässt mich mal vermuten das du mit den Bordmitteln von Java recht schnell an die Grenze der Performance kommst. Wenn es schneller gehen soll wirst du wohl selber etwas implementieren müssen.
Gerade für das Sortieren von Strings gibt's ja jede Menge interessante Algorithmen. Versuch es doch mal mit einem Multikey Quicksort, ggf. mit einer zwei level Hashtable (Bucketsort) vorneweg. Das sollte durchaus einen Geschwindigkeitsschub bringen.

 

[Ark]

(Warum nur habe ich so eine Ahnung, dass spätestens jetzt der TO auf eine Versionsverwaltung setzen sollte, sofern er das nicht schon tut?! )

@FFNB: Falls mit dem Code nun noch nicht die gewünschte Verbesserung eintrat: Bist du dir denn sicher, dass das, wo wir gerade herumdoktern, auch wirklich der Flaschenhals ist? Und bist du dir sicher, dass dein (OO-)Entwurf wirklich den Anforderungen entspricht, also das zu lösende Problem wirklich gut abbildet? Wenn ich mir den Code aus dem ersten Beitrag anschaue, soll es mich nicht wundern, wenn da das eigentliche Problem liegt.

Der Rechenaufwand hängt nämlich (in meinem Code) praktisch nur noch von [c]Arrays.sort()[/c] und [c]String.compareTo()[/c] ab, und auf diese Methoden haben wir keinen Einfluss. Dow Jones' Vorschlag ist zwar ein Ansatz, diesen würde ich aber nur dann weiterverfolgen, wenn es wirklich nicht an einem schlechten Entwurf deinerseits (FFNB) liegt.

Ich habe mir gerade mal [c]String.compareTo()[/c] angesehen, und dieser Code ist bereits stark optimiert (er enthält sogar den wesentlichen Teil zweimal, um je nach interner Darstellung die schnellere Variante auszuwählen). Wenn es also wirklich darauf hinausläuft, etwas noch Schnelleres zu schaffen, wird das extrem hässlich und saukompliziert. (Und dabei hat noch niemand gesagt, dass das letztlich wirklich schneller ist!) Ergo: schieben wir diesen Fall so weit wie möglich nach hinten.

Ark

 

[FerFemNemBem]

Halloechen,

zum Thema Versionsverwaltung: svn seit 2005 derzeit Rev. 1047 der betroffenen Klasse.

Das das der Flaschenhals ist, da bin ich mir zu 100% sicher. Ich habe an dem Programm schon so viel "rumprofiled" (und auch schon viel optimiert) und habe letztendlich genau die Indexerstellung als Flaschenahls extrahiert - und vereinfacht in Posting 1 verpackt. Das Posting ist also nicht so ganz spontan entstanden...

Ich habe den OO-Entwurf nicht selbst gestaltet. Dieser ergibt sich quasi aus dem Design der iTunesDB, deren "Sklave" ich bin.

Ok, ich versuche es nochmal zu erklaeren:

Ein Track in der iTunesDB hat ca. 80 "Merkmale". Einige davon sind: "Title", "Album", "Tracknumber", "Artist", "Genre", "Composer". Ueber diese (und auch ueber Varianten von diesen - z.B. ueber "Artist"+"Album"+"TrackTitle") muss man einen Index bilden, damit der Titel auf dem iPod in der richtigen Ordnung angezeigt wird - je nachdem in welchem Menue man gerade auf dem iPod browst.
Dazu benoetige ich die im Track gespeicherte Position in der Relation zu dem "Merkmal" am Track oder der "Merkmalkombination". Insgesamt muss ich 18 dieser Indexe erstellen, auf meinem "grossen" iPod hab ich 30.000 Titel. Das Erstellen aus meiner Methode (aus Posting 1) dauert ca. 10 Sekunden. Das ist mir einfach zu lang... daher such ich nach Optimierungsmoeglichkeiten.

Danke!

Gruss, FFNB.

PS: Ich hab gerade nochmal ganz viel "dazueditiert"

 

[Ark]

zum Thema Versionsverwaltung: svn seit 2005 derzeit Rev. 1047 der betroffenen Klasse.

Na, dann können wir uns ja austoben, hehe.

Das das der Flaschenhals ist, da bin ich mir zu 100% sicher. Ich habe an dem Programm schon so viel "rumprofiled" (und auch schon viel optimiert) und habe letztendlich genau die Indexerstellung als Flaschenahls extrahiert - und vereinfacht in Posting 1 verpackt. Das Posting ist also nicht so ganz spontan entstanden...

Falls bisherige Optimierungsversuche (hier im Forum) noch nicht den gewünschten Effekt hergevorbracht haben sollten, wirst du wohl mehr Code zeigen müssen - und zwar ohne irgendwelche Vereinfachungen.

Ark

 

[FerFemNemBem]

Halloechen,

...wirst du wohl mehr Code zeigen müssen - und zwar ohne irgendwelche Vereinfachungen.

Ark

Das wird schwierig! Da ich sicher bin, dass der Flaschenhals an ebenjender Stelle liegt, warum soll ich dann "rundrumcode" posten? Und wo soll ich anfangen und wo aufhoeren? Es wird hier doch immer gesagt, dass man ein Selbstcompilierendes Beispiel mit seinem Problem posten soll. Macht man das, ist es auch nicht richtig... verrueckt
Das Projekt hat ca. 30.000 LoC. Wo soll man denn da anfangen/aufhoeren, ohne zu vereinfachen? In Worte gefasst hab ichs ja schon. (hab mein letztes Posting uebrigens nochmal kraeftig "erweitereditiert").

Gruss, FFNB.

 

[bERt0r]

So oft wie du deine Strings umfüllst ist es klar dass das nicht performant ist.
Warum kann z.B deine getIntArrayFromTreeMap Funktion nicht mit der Collection arbeiten, die du von TreeMap.values erhältst? Iterator drauf und fertig.

 

[FerFemNemBem]

Halloechen,

@bERt0r: wo fuelle ich denn oft Strings um? Kannst Du Deine Vorschlaege bitte ein wenig konkretisieren, dann versuche das gerne mal umzusetzen. Momentan weiss ich wirklich nicht, was Du meinst.

Gruss, FFNB.

 

[Dow Jones]

Ich habe mir gerade mal [c]String.compareTo()[/c] angesehen, und dieser Code ist bereits stark optimiert

Jaaain, das solltest du schon präziser fassen: compareTo() ist darauf optimiert zwei beliebige Strings ohne Berücksichtigung eines Kontexts anzuordnen. Soviel Zeit muss sein.
Und da wir beim Sortieren durchaus einen Kontext haben den wir nutzen können ist compareTo() freilich nicht mehr wirklich die beste Möglichkeit einen Stringvergleich durchzuführen.

Wie Ark ja schon schrieb sind es vor allem sort() und compareTo(), welche die Laufzeit beschränken. Auf diese Methoden werden sich vermutlich alle Sortiermöglichkeiten die Java von Haus aus mitbringt abstützen. Wenn das nicht schnell genug ist dann wird es interessant. Dann muss man eben eigene Algorithmen schreiben (was auch in Java durchaus zulässig ist ). In dem hier gegebenen Fall könnte man zum Beispiel ersteinmal nur einen Bucketsort für jedes Merkmal anwenden und die einzelnen Buckets erst später, bei Bedarf weiter sortieren - etwa wenn die Daten eines Buckets angezeigt werden sollen. Oder man implementiert ein bekanntest Verfahren zur Stringsortierung (wie den schon erwähnten Multikey Quicksort). Oder natürlich man macht es sich leicht und googelt nach einer Bib. Erster Treffer: Burstsort4j. Vielleicht hilft das ja schon.

 

[Ark]

Da ich sicher bin, dass der Flaschenhals an ebenjender Stelle liegt, warum soll ich dann "rundrumcode" posten?

Ganz einfach: weil hier ohne zusätzliche Informationen über die Rahmenbedingungen bei weiteren Optimierungsversuchen der Aufwand extrem stark ansteigt, die Wirkung aber kaum abschätzbar wird.

Und wo soll ich anfangen und wo aufhoeren? Es wird hier doch immer gesagt, dass man ein Selbstcompilierendes Beispiel mit seinem Problem posten soll. Macht man das, ist es auch nicht richtig... verrueckt

Hast du denn inzwischen meinen Vorschlag umgesetzt? Hat es was (viel/wenig/Sekunden) gebracht?

Das Projekt hat ca. 30.000 LoC. Wo soll man denn da anfangen/aufhoeren, ohne zu vereinfachen?

Du sagtest, du wärst "Sklave" der iTunesDB. Dann lege doch mal (am besten in Form von Code ) dar, was genau dein Code momentan macht. Da ich mich mit der iTunesDB nicht auskenne, erkläre ich mal etwas allgemeiner:

Ich nehme an, dass am Anfang Daten in einer Art und Weise dargeboten werden, auf die du keinen Einfluss hast, weil du auf die Daten z.B. über eine Bibliothek zugreifst, die du nicht verändern kannst. Dort fängst du an und zeigst, wie du diese Daten für dein Programm aufbereitest. (Etwa: Methoden der Bibliothek geben nach und nach bestimmte Informationen preis, die du dann in eigenen Objekten speicherst.) Dein Programm verarbeitet diese Daten nun auf vielfältige Weise, und einige dieser Verarbeitungsschritte arbeiten auf die Indexerstellung hin bzw. sind momentan dafür notwendig. Diese Schritte musst du aufzeigen. Dann kommt die Indexerstellung selbst, die du ebenfalls möglichst genau so darstellst, wie sie letztendlich abläuft. Danach werden die erstellten Indizes wahrscheinlich weiterverarbeitet (z.B. wieder in Richtung iTunesDB), auch diese Schritte musst du zeigen.

Diese lange Abfolge von Arbeitsschritten, von denen die Indexerstellung einer ist, zeigst du dann (als Code). Also nur der Code, der die Daten erhebt, direkt auf die Indexerstellung hinarbeitet und das Ergebnis dieser Indexerstellung weiterverarbeitet bis zum letztendlichen Ergebnis, das gefordert ist. Sachen wie Benutzerschnittstellen oder Ähnliches können weggelassen werden. Miss dann unter Verwendung von Echtdaten (die du NICHT reinstellen brauchst) die Zeit, die das Gesamtsystem tatsächlich benötigt, sowie die Zeit, die nur für die Indexerstellung draufgeht. Sag dann, wie viel Zeit das Gesamtsystem(!) nur benötigen sollte.

Wenn der Code für das Gesamtsystem doch zu groß (fürs Forum) sein sollte, kannst du dich auch zunächst auf die "nächste Umgebung" beschränken und den Rest davor bzw. dahinter nur kurz andeuten. Wenn das Gesamtsystem, wie ich es dargestellt habe, in Wirklichkeit mit großen Pausen daherkommt (etwa: Einlesen der Daten erfolgt zu Beginn, anschließend kann der Nutzer was machen, und erst beim Drücken auf einen Knopf wird ein Index erstellt), sollte das auch kenntlich gemacht werden.

Aber bevor du das jetzt alles machst, solltest du erst einmal sagen, was nun rausgekommen ist (mit den Codevorschlägen hier).

@Dow Jones: Radixsort etc. ist mir auch schon als mögliche Alternative eingefallen, allerdings halte ich ein (vorschnelles) Austauschen des Sortieralgorithmus nur bedingt für eine gute Idee. Wenn der Code des "Gesamtsystems" (siehe oben) ähnlich aussehen sollte wie das Beispiel im ersten Beitrag, wäre eine Runderneuerung nicht nur aus Performancegründen, sondern auch in Bezug auf Wartbarkeit sinnvoll. Einfach einen "schnelleren" Algorithmus zu verwenden hat dann eher was von reiner Symptombekämpfung. (Das ist natürlich nicht immer schlecht, aber unter den aktuellen Umständen soll es mich nicht wundern, wenn auch ein besserer Algorithmus da nicht so viel rausholen kann, wie man erwartet hätte. Probieren kann man es natürlich trotzdem. )

Ark

 

[bERt0r]

Ich beziehe mich auf das hier:

static int[] getIntArrayFromTreeMap(TreeMap<? extends Object,Integer> treeMap)
    {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.addAll(treeMap.values());        
        
        int[] indexEntries = new int[arrayList.size()];
    
        for(int i=0; i<arrayList.size(); i++)
        {
            indexEntries[i] = arrayList.get(i).intValue();
        }
        return indexEntries;
    }

Wieso nicht einfach

public static void main(String[] args) 
    {
        String[] strings={"ABBA","VOLVO","BITTE","ANTWORT","ZETTEL","ABWASCH","KLEIN","HUT","FENSTER"};
      
        TreeMap<CollationKey, Integer> treeMap = new TreeMap<CollationKey, Integer>();
      
        Collator collator = Collator.getInstance();
        collator.setStrength(Collator.PRIMARY);
    
        for(int position=0; position<strings.length; position++)
        {
            treeMap.put(collator.getCollationKey(strings[position]), position);
        }
    
        Collection<Integer> positionen=treeMap.values();
        
        Integer[] sortiert = new Integer[positionen.size()];
        sortiert=positionen.toArray(sortiert);
  
        for(Integer i:sortiert)
        {
        	System.out.println(i);
        }
    }

Wie du siehst kannst du dir deine ArrayList komplett sparen.

 

[Shulyn]

[..]
Wie du siehst kannst du dir deine ArrayList komplett sparen.

Mit 300 Strings braucht dein Snippet um die :
40935734 Nano Sec.
Ohne die ArrayList Methode sind es nur noch um die :
38411508 Nano Sec.

So lässt sich schon "viel" sparen



Wie lädst du den die Daten in dein Program? Welche DB wird benutzt, und wie kannst du Daten aus dieser herrauslesen? Evtl könntest du bereits sortiert die Daten lesen. So würdest du dir den Initialen Sortier durchlauf sparen, und nur auf anforderung neu Sortieren (wenn es sein muss).

Könntest du die Daten evtl. gekapselt in einer anderen form speicher? Imo scheint es als würdest du um die 5 Indexes benötigen (Titel / Artist / usw.) vllt. ist es dir möglich die Daten bereits mit diesen indexes zu Speichern, so das ein umsortieren nicht mehr nötig ist.

PS: Habe leider ka. von Apple pPodukten, finde Sie einfach nicht so gut

 

[FerFemNemBem]

Halloechen,

um die Bibliothek zum Auslesen/Weiterverarbeiten der iTunesDB geht es hier gerade. Ich hab also grossen Enfluss darauf, da ich sie geschrieben habe. Ansich ist das Problem voellig trivial - nur schneller muss es eben werden. Es gibt da keine "lange Abfolge von Arbeitsschritten, von denen die Indexerstellung einer ist"...

In der Datenbank (es handelt sich im Grunde nicht um eine Datenbank sondern um ein Textfile mit sequentiell abgespeicherten Daten fuer den iPod) stehen Informationen zu jeden Track. Dazu gehoert eben "Position", "Artist", "Album" etc. Das lese ich aus der Datenbank aus und erzeuge Track-Objekte, die genau diese Informationen halten. An anderer Stelle in der Datenbank muss der "Index" stehen. Dieser setzt sich wie schon beschrieben aus den entsprechend sortierten "Position"-Feldern aller Tracks zusammen. Wenn ich die iTunesDB nun zurueckschreibe und neue Tracks hinzugekommen sind, muss ich diese "Reihe von Zahlen" neu sortieren und in die iTunesDB schreiben. Dazu suche ich nun einen schnellen Algorithmus.

An dem, fuer das Eingangsposting in sinnvoll das Problem beschreibender Form zusammengestrichenenen, Code auf ein Redesign der Impementierung der iTunesDB-Bibliothek schliessen zu wollen, ist dann doch etwas eigenartig...

Na ich werde erstmal Eure Vorschlaege umsetzen und vermelden was es bringt... das ist auf jeden Fall sinnvoller als hier weiterzulamentieren.

Danke!

Gruss, FFNB.

 

[Ark]

Okay, also noch mal mit eigenen Worten wiedergegeben: Es gibt eine Datei, in der stehen Datensätze mit allen "richtigen" Daten drin. Daneben gibt es noch andere Dateien, die selbst keine "richtigen" Daten enthalten, sondern nur Verweise auf die Datei mit den "richtigen" Daten, wobei diese Verweise je nach Datei einer bestimmten Ordnung gehorchen.

Habe ich das richtig zusammengefasst?

Wenn ja: Wie wäre es mit einer "richtigen" Datenbank? Wenn dir das nicht zusagt: Schau dir mal B+-Bäume an: B+-Baum ? Wikipedia Wenn du die verwendest/implementierst, kommt am Ende eigentlich auch nicht viel weniger als eine "richtige" Datenbank raus (okay, zwar nur mit rudimentärem DBMS etc., aber das ist gerade mal egal). Auf jeden Fall scheinen (nach diesem sehr wichtigen Beitrag, der auch zwei Seiten früher hätte kommen können ) Bäume das Mittel der Wahl zu sein.

Ansonsten wirst du wohl mehr Code zeigen müssen. Zumindest sehe ich das so. Wie sehen es die anderen?

Ark

 

[FerFemNemBem]

Halloechen,

Du hast das _fast_ richtig zusammengefasst. Es gibt genau eine Datei, in der alles hintereindander steht. In etwa so:

[track]hierkommenalletrackinformationen[track]hierkommenalletrackinformationen[track]hierkommenalletrackinformationen[track]hierkommenalletrackinformationen[titelindex]1,3,0,2[artistindex]0,2,1,3[genreindex]2,1,3,0

Warum man dafuer keine "richtige" DB genommen hat, kann Dir evtl. Steve Jobs beantworten. Ich muss nehmen, was da ist und das ist nunmal nur diese Datei. Auf aktuelleren iPods ist man dann uebrigens dazu uebergegangen SQLite zu benutzen - aber auch nur zusaetzlich zu der Datei. Was fuer ein "kram", das alles...

Gruss, FFNB.

 

[bERt0r]

Programmintern wirst du deine Trackobjekte aber doch in einer Liste halten und damit die TreeMaps bauen - du füllst nicht die zu sortierenden Strings dann wieder in Arrays oder?

Ich vermute, dass das Erzeugen der CollationKeys am meisten Zeit verbrauchst. Die könntest du doch eigentlich auch gleich beim einlesen der Daten generieren und im Speicher halten. Das würde dir einiges an Zeit ersparen, wenn du dann ein paar mp3s dazuaddest.

 

[FerFemNemBem]

Halloechen,

Ich vermute, dass das Erzeugen der CollationKeys am meisten Zeit verbrauchst.

Korrekt. Die Zeit geht bei [c]treeMap.put(collator.getCollationKey(strings[position]), position);[/c] drauf, wenn es dann sehr viele Elemente werden.

Das man mit dem Weglassen der ArrayList etwas Zeit sparen kann stimmt sicher, ist aber (mit insgesamt 42ms bei 29550 Tracks) im Vergleich zum Befuellen der TreeMap (insgesamt 5921ms bei 29550 Tracks) eher zu vernachlaessigen.

Die könntest du doch eigentlich auch gleich beim einlesen der Daten generieren und im Speicher halten. Das würde dir einiges an Zeit ersparen, wenn du dann ein paar mp3s dazuaddest.

Ich habe mich dafuer entschieden, den Index aus der vorhandenen Datei nicht auszulesen und dann weiterzupflegen (was ganz sicher die bessere/schnellere Loesung waere), da es Drittprogramme zur iPodverwaltung gab/gibt, die diesen Index nicht korrekt gepflegt haben. Daher gehe ich "auf Nummer sicher" und erzeuge den Index vor dem Rausschreiben in die Datei komplett neu.

Gruss, FFNB.

 

[bERt0r]

Halloechen,
Ich habe mich dafuer entschieden, den Index aus der vorhandenen Datei nicht auszulesen und dann weiterzupflegen (was ganz sicher die bessere/schnellere Loesung waere), da es Drittprogramme zur iPodverwaltung gab/gibt, die diesen Index nicht korrekt gepflegt haben. Daher gehe ich "auf Nummer sicher" und erzeuge den Index vor dem Rausschreiben in die Datei komplett neu.

Gruss, FFNB.

Glaube du hast mich falsch verstanden. Es geht darum die Anzahl getCollationKey Aufrufe zu minimieren indem du sie im Speicher hältst. Wenn du das erstellen der Collationkeys gleich beim einlesen der Daten - am besten in einem Thread im Hintergrund - machst, musst du nur mehr für neu hinzugekommene (schätze mal vom Benutzer) Trackobjekte diese aufwendige Berechnung machen.

Es geht vor allem darum, dass ich als Benutzer lieber am Anfang einen 10s ladebildschirm sehe, als jedes mal 10s zu warten, wenn ich auf speichern drück.

 

[FerFemNemBem]

Halloechen,

da habe ich Dich in der Tat falsch verstanden. Du meinst also es ist gar nicht die Sortierung an sich, sondern das erzeugen der CollationKeys, was hier so kostspielig ist. Das ist ein guter Punkt. Ich werde das auch mal testen.

Danke!

Gruss, FFNB.

 

[FerFemNemBem]

Halloechen,

ich habe nun das Erstellen der CollationKeys angepasst. Statt 5921ms bei der Erstindexerstellung mit 29550 Tracks dauert es jedes weitere Mal dann nur noch 563ms.

Danke an alle die geholfen haben!

Gruss, FFNB.

 

[bERt0r]

Wenn du deine TreeMaps<CollationKey,Integer> nicht jedes mal neu aufbaust dürfte es nochmal schneller gehen. Z.b würde ich mir eine Klasse IndexVerwaltung anlegen, die pro Index eine TreeMap als Membervariable hat und gleich die Methoden hat wie die int Arrays erstellen, ein neues Trackobjekt jeder Treemap hinzufügen bzw eines löschen.
Insofern ich mich nicht ganz täusche ist ja gerade das Sortierte einfügen in TreeMaps am schnellsten.

 

[FerFemNemBem]

Halloechen,

daran, die Indexe mitzupflegen, anstatt immer neu aufzubauen, hatte ich auch schon gedacht. Jedoch bin ich mit den 500ms nun so zufrieden, dass ich den Gedanken nicht weiterverfolgt habe - ich fauler Sack.

Und die 500ms sind schon der absolute "worstcase". Ich hab einen 160GB Festplattem-iPod voll mit Musik zum Testen genommen. Groesser geht nicht. Mit den "kleineren" Flash-Speicher iPods faellt das gar nicht weiter auf.

Gruss, FFNB.