Schnellste Collection/Liste

[mephi]

Ich sitze momentan an einem "Wecker" für die FH. Der Großteil war vorgegeben.. mehr oder weniger gut.
Bei jedem "tick" den der Wecker macht wird eine Liste mit Alarmen usw durchgegangen. Aus persönlichem Interesse und Ehrgeiz will ich das Ding nun so leistungsfähig wie möglich machen.

Daher meine Frage, was ist die schnellste Liste/Collection?
Bisher nutze ich eine HashMap und eine HashSet die mit Iteratoren durchlaufen werden. Gibts noch schnellere Lösungen?
Ein Vektor + forschleife? Oder eine ArrayList?

 

[Wildcard]

Das ist abhängig von den Operationen die durchgeführt werden.
Sonst bräuchte man die anderen ja nicht...

 

[mephi]

hm. ich laufe mit einem iterator über die elemente der hashset, caste jedes objekt und alle weiteren aktionen sind ja gleich egal bei welcher liste..
wo liegen denn die vorteile der einzelnen listen? steht das irgendwo?

 

[Wildcard]

-LinkedList ist sehr langsam bei wahlfreiem Zugriff, brauchen dafür aber wenig Speicher und sind schnell beim Einfügen, Entfernen und Iterieren.

-Vector: Legacy Klasse, vergiss sie

-ArrayList sehr schneller wahlfreier Zugriff, schnelle Iteration, Entfernen und Hinzufügen von Elementen unter Umständen sehr teuer, Speicher Overhead

-HashSet schnellster wahlfreier Zugriff für gut implementierten Hash, bricht bei falsch implementieren Hash ein. Iteration wird etwas langsamer sein als bei den anderen.

Einfach mal API lesen :wink:

 

[mephi]

vielen dank aber hätte da eine weitere frage. was ist ein gut implementierter hash? bzw was ist ein schlechter?
hab mir nie drüber gedanken gemacht was hash überhaupt heißt.. n übersetzer sagt mir dazu"hackfleisch" soll das also sowas wie eine ungeordnete menge sein?

 

[Wildcard]

Ein Hash ist ein Wert der einen großen Wertebereich auf einen kleineren Abbildet.
Das es dabei zu Kollisionen (zwei verschiedene Objekte mit gleichem Hash) kommen kann ergibt schon die Logik.
Ein guter Hash zeichnet sich durch wenige Kollisionen aus, ein schlechter durch das Gegenteil.

 

[mephi]

achso, meinen die da die native implementierung?
hmm.. da muss ich doch mal suchen was in java sache ist

danke

 

[Wildcard]

Nein, du wirst einfach nicht umhinkommen irgendwann selbst mal hashCode() zu überschreiben (nämlich immer dann wenn du equals überschreibst).
Und wenn du das tust ist's einfach Grottendämlich zB '0' zurückzugeben :wink:

 

[mephi]

achso. und du meinst die möglichst kollisionsfreie methode um einen eigenen hashcode zu generieren. damit hab ich noch nichts gemacht.
für das aktuelle projekt hab ich einfach eine ID die eindeutig sein muss. aber zum spass könnte ich ja mal hashCode() und equals() überschreiben und darin die ID benutzen

 

[Tellerrand]

Ich sitze momentan an einem "Wecker" für die FH. Der Großteil war vorgegeben.. mehr oder weniger gut.
Bei jedem "tick" den der Wecker macht wird eine Liste mit Alarmen usw durchgegangen. Aus persönlichem Interesse und Ehrgeiz will ich das Ding nun so leistungsfähig wie möglich machen.
[...]
Bisher nutze ich eine HashMap und eine HashSet die mit Iteratoren durchlaufen werden. Gibts noch schnellere Lösungen?
Ein Vektor + forschleife? Oder eine ArrayList?

Die schnellste Lösung dürfte eine priorisierte Warteschlange, in der die Alarme nach Zeit sortiert sind, sein. Dadurch musst du immer nur das erste Objekt prüfen und nicht über die komplette Liste iterieren.
http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html wäre meine Wahl.

 

[mephi]

EDIT: das ganze lässt sich leider nicht nutzen, da das interface für alarme nur 2 methoden mit boolschem rückgabte wert vorsieht was die "klingelzeit" angeht .. isAlarmTimeNow() und hasToBeRemoved()

außer ich lass danach sortiern. hmmm dann muss ich nur vorher mit peek schauen wann ein alarm kommt der nicht entfernt werden soll..

 

[mephi]

arg nein geht imo auch nicht.. kann euch ja mal meine aktuelle run methode zeigen..

	public void run() {
		long before = 0;
		long after = 0;
		while(true) {
			before = System.currentTimeMillis();
			makeATick();
			after = System.currentTimeMillis();
			try {
				Thread.sleep(updateTime-(after-before));
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			
		}
		
	}

und makeATick

	protected synchronized void makeATick() {
		updateTimeListeners(new TimeEventImpl(this));
		


		Iterator iterator = (Iterator) alarms.keySet().iterator();
		Alarm tmpAlarm = null;
		while (iterator.hasNext()){
			tmpAlarm = (Alarm) alarms.get(iterator.next());

			if(tmpAlarm.isAlarmTimeNow(new Date().getTime())){
				updateAlarmListeners(new AlarmEventImpl(this, tmpAlarm.getId()));
			}
			if(tmpAlarm.hasToBeRemoved()) delAlarms.add(tmpAlarm);
		}
		if( !delAlarms.isEmpty()) {
			iterator = delAlarms.iterator();
			while (iterator.hasNext()) {
				removeAlarm((Alarm)iterator.next());
			}
			delAlarms.clear();
		}
	}

vielleicht habt ihr noch eine idee, das schneller zu machen
alarms ist eine HashMap und delAlarms ein HashSet

 

[Tellerrand]

Ja wenn Alarm keine Methode der Zeit bietet, sowie nicht das Interface Compareable implementiert und du die Klasse nicht änderst dann fällt eine Queue weg

Bleibt also die Frage was mehr Ressourcen frisst von deinen Operationen.
Schwierige Frage, aus dem Gefühl heraus würde ich sagen eine LinkedList.

 

[mephi]

ok ich glaub ich kann da nicht mehr viel optimieren.
ich denke die meiste Zeit geht bei dem Thread.sleep() drauf, kann das sein? für meine makeATick methode bekomm ich zeiten von max. 16ms und bei extremen tests mit über 1mio listenern ca 150ms.

 

[DEvent]

ok ich glaub ich kann da nicht mehr viel optimieren.
ich denke die meiste Zeit geht bei dem Thread.sleep() drauf, kann das sein? für meine makeATick methode bekomm ich zeiten von max. 16ms und bei extremen tests mit über 1mio listenern ca 150ms.

Naja Thread.sleep() lässt ja den Thread solange schlafen, wie du willst. Also ein eindeutiges ja, updateTime ist sicher 1000ms?

 

[mephi]

ja sicher.
ein thread bekommt ja nicht genau nach der sleeptime also hier 1000ms die kontrolle zurück.. um wieviel ms kann sich das verzögern?