Gibt es eine bereits implementierte Datenstruktur, die ich verwenden kann, um einem Objekt zuzuordnen? (in meinem Fall eine Kante), eine ganze Zahl? Ich lese ein Diagramm aus einer Datei, 10 Mil Scheitelpunkte, 60 Mil Kanten und ich zuweisen zu jeder Kante, eine Kosten, mit einer Karte (costs.put (e, Kosten)).
Ich erstelle die Kosten-Map auf diese Weise:
%Vor%Die Ausnahme, die es gibt, ist:
%Vor% HashMap ist die korrekte Datenstruktur für eine Basis Map . Das Problem, das Sie haben, ist, dass die JVM nicht angewiesen wird, genügend Speicherplatz zu reservieren, um den Dateiinhalt im Speicher zu behalten. Starten Sie die JVM mit einem -Xmx -Flag. Zum Beispiel erlaubt es -Xmx1G -Parameter, 1 Gigabyte Speicher zu verwenden.
Sie haben 6e7 Kanten. Ein einfaches Objekt benötigt 24 Bytes (64-Bit-HotSpot), also genau dort sind 1.449 Bytes (1.5 GB). Jetzt stellen Sie die effizienteste Karte vor, die Sie sich vorstellen können, indem Sie nur 6e7-Referenzen plus 6e7 Integer -Objekte hinzufügen. Das sind weitere 2.4e8 Bytes für die refs und 1.44e9 Bytes für die Integer s: weitere 1.5 GB, die Summe beträgt jetzt 3 GB - und das ist die theoretische Untergrenze für Ihr Problem (Modulo-Caching) , siehe unten).
Gestützt darauf schlage ich vor, dass Sie Ihre Edge -Klasse um ein weiteres int -Feld erweitern. Dies wird Ihren Speicherbedarf drastisch reduzieren.
Wenn dies jedoch keine Option ist und:
new Integer , sondern Integer.valueOf , Autoboxing usw., Sie profitieren automatisch von dem integrierten kleinen Integer-Cache. Wenn die Ganzzahlen Werte aus einem größeren Bereich annehmen, aber immer noch sehr dupliziert werden, ist ein benutzerdefinierter Cache sehr empfehlenswert.
Zusätzlich zum Ändern der jvms-Speichereinstellungen können Sie HashMap s Speicherverwaltung mit Anfangskapazität und Lastausgleich optimieren.
Javadoc Auszug:
Eine Instanz von HashMap hat zwei Parameter, die ihre Leistung beeinflussen: Anfangskapazität und Lastfaktor. Die Kapazität ist die Anzahl von Buckets in der Hash-Tabelle, und die anfängliche Kapazität ist einfach die Kapazität zum Zeitpunkt der Erstellung der Hash-Tabelle. Der Ladefaktor ist a Maß dafür, wie voll die Hash-Tabelle vor ihrer ist Die Kapazität wird automatisch erhöht. Wenn die Anzahl der Einträge in der Hash-Tabelle überschreitet das Produkt aus Ladefaktor und Strom Kapazität wird die Hash-Tabelle aktualisiert (dh interne Daten) Strukturen werden neu aufgebaut), so dass die Hash-Tabelle ungefähr zweimal vorhanden ist die Anzahl der Buckets.
Zurück zum ursprünglichen Problem: Sie haben Kanten, die Kosten haben. Da Ihr Diagramm spärlich ist, warum nicht eine dünn besetzte Matrix verwenden? Vielleicht ist ein Objekt-zu-Integer-Mapping nicht das, was Sie wirklich brauchen und wollen. Sie können apache.commons.math betrachten, ich denke, sie haben dünn besetzte Matrizen. Außerdem müssen Sie darüber nachdenken, wie Sie auf die Kosten in Ihren Algorithmen zugreifen, um das richtige Sparse-Format zu wählen (spaltenbasiertes Lauflängencodieren / zeilenbasiertes rle oder etwas anderes). Oder es ist dir egal, und verwenden Sie alle, aber dann sollten Sie das Ding am Anfang Ihrer Algorithmen konvertieren.
Sie erkennen, dass dies eine ganze Menge RAM erfordert, oder? Probieren Sie die Größe des Heapspeichers zu erhöhen , und alles wird gut ...
>Und um Ihre ursprüngliche Frage zu beantworten: Ja, das ist es, was Karte s sind für ...
Vielleicht suchen Sie nach TObjectIntHashMap Dies ist ähnlich wie in HashMap<Edge, Integer> , außer dass es int als primitives Element speichert, wodurch möglicherweise etwas Speicher gespart wird. Diese Sammlung kann auch geringfügig schneller sein, wenn die Sammlung größer ist (weil sie besser in den Cache passt)
Tags und Links java directed-graph