Datentypen Große Datenmenge Sortiert halten

[ppapsd]

hi

Ich benötige mal einen Denkanstoß bezüglich das ständig Sortiert halten von Großen Datenmengen.

Folgende Situation:

- Ich habe eine Datenmenge die etwa 200000 Einträge enthält momentan in einer Hashmap.

Nun müssen diese Einträge aber so abgearbeitet werden, dass immer die zwei kleinsten entnommen werden und anschließend ein neuer Eintrag (mit dem Wert der beiden entnommenen zusammen) eingefügt wird aber an der richtigen Position.
So das die Sortierung erhalten bleibt. Für die nächste Entnahme.

Nur ich finde einfach keine passende Datenstruktur.

Ich habe es schon mit einem TreeSet versucht nur anscheinend speichert er mir nicht alle Objecte ab, da ich von den 200000 Einträgen danach nur noch 174 habe. Zurückgegeben mit size();

Was mache ich falsch, oder welche Möglichkeiten gibt es noch?

 

[Gast2]

TreeSet ist schon die richtige Wahl.
Wenn du nach dem Hinzufügen der 200.000 Einträge nur 174 in dem Set hast dann sind vermutlich equals und/oder hashCode nicht korrekt implementiert.
Die HashMap legt listen an falls hashWerte kollidieren, das TreeSet macht das nicht.

Poste doch mal deine Klasse die du in das Set setzen willst.

 

[ppapsd]

Das ist das Object was in den TreeSet soll. Und ich habe keine Ahnung, wie ich das mit dem HashCode mache. Was gibt den der HashCode an? ???:L

Das ist das erste mal, das ich das benötige. :bahnhof:

public class TreeNode implements Comparable<TreeNode> {

	// Speichert die Häufigkeit
	private int frequency = 1;
	
	// Der RGB Wert
	private RGB rgb;
	
	public TreeNode (int frequency) {
		this.frequency = frequency;
	}
	
	/**
	 * @return the frequency
	 */
	public int getFrequency() {
		return frequency;
	}

	/**
	 * @param rgb the rgb to set
	 */
	public void setRGB(RGB rgb) {
		this.rgb = rgb;
	}

	/**
	 * @return the rgb
	 */
	public RGB getRGB() {
		return rgb;
	}
	
	public int compareTo(TreeNode compareObject) {
		
		if(getFrequency() < compareObject.getFrequency()) {
			return -1;
		} else if(getFrequency() == compareObject.getFrequency()) {
			return 0;
		} else {
			return 1;
		}
		
	}
	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((rgb == null) ? 0 : rgb.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		TreeNode other = (TreeNode) obj;
		
		if (rgb == null) {
			if (other.rgb != null)
				return false;
		} else if (!rgb.equals(other.rgb))
			return false;

		return true;
	}
}

 

[Gast2]

Der Hinweis mit dem hashcode war glaube ich nicht ganz richtig.
Das TreeSet orientiert sich nur am equals und dem Comparator.

Du vergleichst in deiner equals Methode nur den RGB Wert.
Das heißt wenn zwei Objekt den selben RGB Wert haben aber unterschiedlichen Frequenzen werden diese beiden als gleich betrachtet, und es landet nur das erste im Set. Du solltest die equals methode also noch um den frequency erweitern.

EDIT:

Was gibt den der HashCode an?

Am HashCode orientiert sich z.b. die HashMap. Anhand des HashCodes macht die Map fest wie die Objekte eingeordnet werden. Damit kann man eine konstante Zugriffszeit für z.b. add, remove erreichen.
Idealerweise unterscheiden sich die hashwerte von Objekten die unterschiedlich sind.

 

[ppapsd]

Ja, aber ich habe in der HashMap nur 200.000 unterschiedliche RGB Werte. Von daher müsste doch die equals Methode so trotzdem funktionieren.

Aber ich habe es auch mal anders getestet. Gleiches Ergebnis! ;(

und Danke für die Erklährung ;-)

 

[Gast2]

Kannst du mal nen KSKB posten wo das problem auftritt?

 

[tagedieb]

Die Methoden

hashcode()

und

equals(..)

werden von TreeSet NICHT benutzt.

Das einzig entscheidende ist die

compareTo(..)

Methode. Return Werte -1 oder 1 fuegen einen neuen Eintrag in das Set hinzu. Return 0 ueberschreibt einen bestehenden Eintrag, da ein Set keine doppelten Eintraege haben darf.

Ich vermute deswegen, dass du nur 174 verschiede Frequencies verwendest. Kann das sein?

 

[andiv]

Wenn ich die Doku richtig verstehe, dann verwendet TreeSet nur die compareTo-Methode. D.h. dass bei a.compareTo(b) == 0 nur a im Set landet und b nicht. Da du in compareTo nur frequency vergleichst und in equals nur rgb sind diese beiden Methoden nicht mehr konsistent und aus a.compareTo(b) == 0 folgt eben nicht a.equals(b) == true.

Falls du das ganze für eine Huffmann-Kodierung oder ähnliches brauchst würde ich dir zu einem Heap (realisiert z.B. durch die PriorityQueue) raten. Das ist die ideale Datenstruktur wenn man immer das kleinste Element entnehmen will und neue geordnet hinzufügen muss.

 

[ppapsd]

Ja, das stimmt es soll für einen HuffmanCode dienen, aber wenn ich PriorityQueue verwende muss ich auch eine compareTo Methode verwenden oder? nur bekomme ich dort keine geordnete Reihenfolge zurück.

public int compareTo(TreeNode compareObject) {
		
	if(getFrequency() < compareObject.getFrequency()) {
		return -1;
	} else if(getFrequency() == compareObject.getFrequency()) {
		return 0;
	} else {
		return 1;
	}
	
}

 

[andiv]

Mach mal ein KSKB bei dem man dieses Verhalten beobachten kann.

 

[ppapsd]

OK, hier in der Datei ist jetzt mal ein mit Eclipse exportiertes kleines Projekt in dem der Fehler auftritt.

Also es gibt RGB-Werte die unsortiert in einem HashSet stehen und diese werden in ein PriorityQueue geladen und sollten eigentlich mit compareTo sortiert werden. Ich verstehe einfach nicht warum bei der Sortierten Ausgabe die Ausgabe nicht Sortiert ist???

RGBMain.java

public class RGBMain {

	public static void main(String[] args) {
		new RGBGen();
	}

}

RGBGen.java

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

public class RGBGen {
	
	/**
	 * @param args
	 */
	public RGBGen() {
		
        Comparator<TreeNode> comparator = new FreqComparator();
        PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>(10, comparator);
		
		queue.add(new TreeNode(3));
		queue.add(new TreeNode(7));
		queue.add(new TreeNode(1));
		queue.add(new TreeNode(5));

		Iterator<TreeNode> itere = queue.iterator();
		while(itere.hasNext()) {
			System.out.println(itere.next().getFrequency());
		}
		
		/*
		 * Ausgabe:
		 * 1
		 * 5
		 * 3
		 * 7
		 * 
		 * Sollte aber:
		 * 1
		 * 3
		 * 5
		 * 7
		 * 
		 */
		
	}

}

TreeNode.java

import java.io.Serializable;

public class TreeNode implements Serializable {

	private static final long serialVersionUID = 2991550336209813549L;
	
	private int frequency;

	public TreeNode (int frequency) {
		this.frequency = frequency;
	}
	
	/**
	 * @return the frequency
	 */
	public int getFrequency() {
		return frequency;
	}
	
}

FreqComparator.java

import java.util.Comparator;

public class FreqComparator implements Comparator<TreeNode> {

	@Override
	public int compare(TreeNode o1, TreeNode o2) {
        
		if (o1.getFrequency() < o2.getFrequency())
        {
            return -1;
        }
        if (o1.getFrequency() > o2.getFrequency())
        {
            return 1;
        }
        return 0;
        
	}

}

 

[andiv]

Verwende statt dem Iterator eine Schleife mit while(!queue.isEmpty()) { TreeNode node = queue.poll(); ... } dann solltest du die gewünschte sortierte Reihenfolge erhalten. Das Geheimnis ist dass ein Heap keine totale Ordnung sondern nur eine partielle Ordnung verwendet. Mehr brauchst du in deinem Anwendungsfall aber auch nicht.

 

[ppapsd]

DANKE das ist es ..... :toll::toll: