Datentypen Große Datenmenge Sortiert halten

ppapsd

Mitglied
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?
 
G

Gast2

Gast
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

Mitglied
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:

Java:
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;
	}
}
 
Zuletzt bearbeitet:
G

Gast2

Gast
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.
 
Zuletzt bearbeitet von einem Moderator:

ppapsd

Mitglied
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 ;-)
 
Zuletzt bearbeitet:

tagedieb

Top Contributor
Die Methoden
Code:
hashcode()
und
Code:
equals(..)
werden von TreeSet NICHT benutzt.

Das einzig entscheidende ist die
Code:
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

Bekanntes Mitglied
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

Mitglied
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.

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

ppapsd

Mitglied
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
Java:
public class RGBMain {

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

}

RGBGen.java
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
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
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;
        
	}

}
 
Zuletzt bearbeitet:

andiv

Bekanntes Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
P Große Datenmenge wie speichern (HashMap? TreeMap?) Allgemeine Java-Themen 11
P Performance: Ziehen ohne Zurücklegen (große Datenmenge) Allgemeine Java-Themen 10
B Welcher Datentyp für sehr große Zahlenbereiche? Allgemeine Java-Themen 1
F Große Datenmengen effizient programmieren Allgemeine Java-Themen 51
N Das große O berechnen Allgemeine Java-Themen 2
F Best Practice Große Anzahl an Objekten speichern und lesen Allgemeine Java-Themen 19
R Große Zahlen in Worten abkürzen Allgemeine Java-Themen 10
K Große JSON-Dateien schnell und effizient verarbeiten Allgemeine Java-Themen 16
K Große Mengen an Daten speichern Allgemeine Java-Themen 9
VfL_Freak Große und seltsame Probleme nach Java-Update auf V1.8.0_91 Allgemeine Java-Themen 3
E Best Practice Verdammt große Objekte Allgemeine Java-Themen 10
P Große Datenstruktur im Speicher halten Allgemeine Java-Themen 13
M Einfluss von Caching auf die Performance (große Arrays) Allgemeine Java-Themen 24
U Große Liste von Strings mit indiziertem Zugriff Allgemeine Java-Themen 31
D große Textdatei filtern Allgemeine Java-Themen 13
M Große Datei mit Regex durchsuchen Allgemeine Java-Themen 4
R POI große Exceldatei schreiben Allgemeine Java-Themen 7
R Dateigestützte Collection für große Datenmengen Allgemeine Java-Themen 5
K Scanner - große Textfile, nur 0 ab betim. Wert Allgemeine Java-Themen 4
trash Das große Problem: .jar Archiv Allgemeine Java-Themen 19
J Große Datei einlesen und gestückelt verarbeiten Allgemeine Java-Themen 4
I Große Datei am effektivsten/performantesten auslesen und auswerten? Allgemeine Java-Themen 6
S große CSV-Dateien Importieren. Beste Lösung ?! AWS,S3,Hadoop!? Allgemeine Java-Themen 4
P große double Zahlen und modulo Allgemeine Java-Themen 8
O Große Anzahl Bilder laden Allgemeine Java-Themen 7
A Mit RegEx große Dokumente erfassen Allgemeine Java-Themen 14
X Wie verdammt große Datein öffnen? Allgemeine Java-Themen 2
G Große Datenmengen per JDBC Allgemeine Java-Themen 5
G Große XML-Dateien einlesen und auswerten . Allgemeine Java-Themen 2
I JNI - Große Daten übertragen Allgemeine Java-Themen 6
T Große Dateibestände löschen - Speicherproblem Allgemeine Java-Themen 20
S Große ArrayListen Allgemeine Java-Themen 8
S große Datei einlesen! Allgemeine Java-Themen 7
J Große Zahl (double) as text ausgeben? Allgemeine Java-Themen 2
S Kleines Eclipse Problem, große Wirkung Allgemeine Java-Themen 7
H Referenzen statt Objekte für große Speicherstrukturen Allgemeine Java-Themen 19
K Große Herausforderung Allgemeine Java-Themen 2
F Zu große Werte beim byteweisen Lesen mit BufferedReader.read Allgemeine Java-Themen 5
D Große Klasse - was fällt euch so ins Auge? Kritik bitte! Allgemeine Java-Themen 10
M Große Dateien laden Allgemeine Java-Themen 2
F Große Dateien schnell einlesen Allgemeine Java-Themen 14
B OOP HashSet sortiert ausgeben Allgemeine Java-Themen 11
G Datentypen TreeMap nach Color sortiert (kd-Baum) Allgemeine Java-Themen 8
_dp Datentypen PriorityQueue sortiert falsch? Allgemeine Java-Themen 6
G File.listFiles nach Datum sortiert ausgeben Allgemeine Java-Themen 1
F (Wie) sortiert ihr eure Felder, Methoden, etc? Allgemeine Java-Themen 19
L Binärbaum sortiert ausgeben Allgemeine Java-Themen 11
M HashMap sortiert Allgemeine Java-Themen 6
T HashMap, sortiert nach Reihenfolge Allgemeine Java-Themen 7
m@nu FileTreeModel sortiert . uiuiui Allgemeine Java-Themen 14
E HashMap/Table sortiert nach nacheinander eingefuegten Elmeme Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben