Anzahl der verwendeten Farben eines (Buffered)Image bestimmen?

L

lui7172

Mitglied
Hallo,

sollte es über eine der Standardmethoden bereits möglich sein und ich den Wald vor lauter Bäumen nicht sehen, dann entschuldige ich mich schon mal.
Mein Simple-Algo, alle Pixel ablaufen und ggf. die Farbwerte in eine ArrayListe schmeißen, ist bei etwas größeren Bildern (vielen Farben) unerträglich langsam. Aber wie geht es schneller?

Gruß
lui
 
Ist mal nur ein Vorschlag, birg natürlich eine gewisse Ungenauigkeit:
1. In Intervallen über das Bild gehen - z.B. 20 px
2. Wenn die Anfangspixel der Intervalle gleich sind, dann ist es ziemlich unwahrscheinlich, dass dazwischen eine Farbveränderung stattgefunden hat.
3. Sind sie verschieden, wird dazwischen warscheinlich eine Farbänderung oder ein -verlauf vorliegen.
4. Intervall für diesen Bereich verkleinern und wieder von vorne
 
Hi,

ne ne, ich brauche schon eine exakte Methode.
Aber das bringt mich auf eine andere Idee; Teuer ist ja hauptsächlich die Frage nach "hatte ich die Farbe schon". So lange die ArrayListe wenige Elemente enthält, ist die Abfrage per contains() ok. Später dann könnte es sinnvoll sein, die Liste per Quick- und danach per Heapsort zu sortieren und per binarySearch abzufragen. Die Idee dahinter ist, dass wenn schon fast alle Farben in der Liste sind, die Abfragen per contains immer teurer werden, die Einfügungen aber derart selten werden, dass die erhöhten Kosten durch die Sortierung von den Einsparungen bei den Abfragen per binarySearch mehr als wett gemacht werden.
"Wenige" und "später" hängt von der max. Anzahl an Farben ab.

Danke
lui
 
Hallo,

würde sich für diesen Fall nicht am ehesten eine Hashmap eignen? Damit solltest du in konstanter Zeit einfügen (bzw. überschreiben, falls die Farbe schon vorkam) können.

Grüße,
Matthias
 
Hi Matthias,

die Frage ist, ab wann sich die Hashmap lohnt. Bei wenigen Elementen wird die ArrayList wohl schneller sein. Leider habe ich im Moment nicht die Zeit, dass alles genauer zu untersuchen/testen :-(

Gruß
lui
 
Ist die Geschwindigkeit so wichtig, liegt doch warscheinlich bei dir nichtmal im Sekunden Bereich!? Ich denke sogar mit einem Set geht es schneller, da du nicht jedesmal mit contains prüfen musst, ob der Wert schon vorhanden ist. In einem Set kommt jeder Wert nämlich nur einmal vor.
 
lui7172 hat gesagt.:
die Frage ist, ab wann sich die Hashmap lohnt. Bei wenigen Elementen wird die ArrayList wohl schneller sein.
Zum Vergrößern anklicken....
Warum sollte die ArrayList schneller sein? Und selbst wenn es so wäre – dein Problem waren doch genau die großen Bilder?

Mit folgendem Benchmark kann man sich leicht einen Überblick verschaffen:
Java: 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;


public class ArrayListVsHashMapVsHashSet {
	public static final int LOOPS = 100;
	public static final int COLORS = 1000;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();		
		HashSet<Integer> hs = new HashSet<Integer>();
		long start, end;
		
		start = System.currentTimeMillis();
		for (int j = 0; j < LOOPS; ++j) {
			for (int i = 0; i < COLORS; ++i) {
				if (!al.contains(i)) {
					al.add(i);
				}
			}
		}
		al.size();
		end = System.currentTimeMillis();
		System.out.println("ArrayList finished in " + (end - start) + "ms");
		
		start = System.currentTimeMillis();
		for (int j = 0; j < LOOPS; ++j) {
			for (int i = 0; i < COLORS; ++i) {
				hm.put(i, true);
			}
		}		
		hm.size();
		end = System.currentTimeMillis();
		System.out.println("HashMap finished in " + (end - start) + "ms");
				
		start = System.currentTimeMillis();
		for (int j = 0; j < LOOPS; ++j) {
			for (int i = 0; i < COLORS; ++i) {
				hs.add(i);
			}
		}
		hs.size();
		end = System.currentTimeMillis();
		System.out.println("HashSet finished in " + (end - start) + "ms");
	}

}
Auf meinem System ergibt das folgende Ausgabe:
Code: 
ArrayList finished in 940ms
HashMap finished in 14ms
HashSet finished in 9ms
Selbst bei nur 1000 verschiedenen Werten ziehen HashMap und HashSet der ArrayList also um Größenordnungen davon. Ich hab auch ein bisschen mit den Werten von LOOP und COLORS rumgespielt und keine Konstellation gefunden, in der die ArrayList schneller gewesen wäre. Stellt sich nur noch die Frage, wie schnell das Auslesen der Pixel aus dem Bild ist und ob die verwendete Collection überhaupt eine große Rolle spielt :) Aber kannst ja mal ausprobieren und berichten.

Grüße,
Matthias
 
Ist es mit einem einfachen Set nicht noch schneller? Immerhin muss man dann nicht noch extra den Boolean(oder anderen) Wert mit speichern.
 
Schon, aber da ein HashSet ja Set implementiert, dachte ich das Set (nicht HashSet) noch etwas schneller ist. War halt mein Vorschlag, da ich den Eindruch habe, dass es lui7172 hier um Performance geht.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück