Sparse Matrizen / Arrays in Java

Ich arbeite an einem in Java geschriebenen Projekt, für das ich ein sehr großes 2-D-Array mit geringer Dichte erstellen muss. Sehr spärlich, wenn das einen Unterschied macht. Wie auch immer: Der wichtigste Aspekt für diese Anwendung ist die Effizienz in Bezug auf die Zeit (nehmen Sie eine Menge Speicher an, wenn auch nicht annähernd so unbegrenzt, dass ich ein Standard-2D-Array verwenden kann - der Schlüsselbereich liegt in beiden Dimensionen in Milliardenhöhe ).

Von den Kajillion Zellen im Array gibt es mehrere hunderttausend Zellen, die ein Objekt enthalten. Ich muss in der Lage sein, den Zellinhalt SEHR schnell zu ändern.

Wie auch immer: Kennt jemand eine besonders gute Bibliothek für diesen Zweck? Es müsste sich um eine Berkeley-, LGPL- oder ähnliche Lizenz handeln (keine GPL, da das Produkt nicht vollständig Open-Source sein kann). Oder wenn es nur eine sehr einfache Möglichkeit gibt, ein Homebrew-Objekt mit spärlichem Array zu erstellen, wäre das auch in Ordnung.

Ich denke über MTJ nach , habe aber noch keine Meinung zu seiner Qualität gehört.

Mit Hashmaps erstellte Sparsed-Arrays sind für häufig gelesene Daten sehr ineffizient. Die effizienteste Implementierung verwendet einen Trie, der den Zugriff auf einen einzelnen Vektor ermöglicht, in dem Segmente verteilt sind.

Ein Trie kann berechnen, ob ein Element in der Tabelle vorhanden ist, indem er nur eine schreibgeschützte ZWEI-Array-Indizierung durchführt, um die effektive Position zu ermitteln, an der ein Element gespeichert ist, oder um festzustellen, ob es im zugrunde liegenden Speicher nicht vorhanden ist.

Es kann auch eine Standardposition im Sicherungsspeicher für den Standardwert des sparsed Arrays bereitstellen, sodass Sie keinen Test für den zurückgegebenen Index benötigen, da der Trie garantiert, dass alle möglichen Quellindizes mindestens dem Standardwert zugeordnet werden Position im Hintergrundspeicher (wo Sie häufig eine Null, eine leere Zeichenfolge oder ein Nullobjekt speichern).

Es gibt Implementierungen, die schnell aktualisierbare Versuche unterstützen, mit einer optionalen "compact ()" - Operation, um die Größe des Sicherungsspeichers am Ende mehrerer Operationen zu optimieren. Versuche sind VIEL schneller als Hashmaps, da sie keine komplexe Hashing-Funktion benötigen und keine Kollisionen für Lesevorgänge verarbeiten müssen (Bei Hashmaps haben Sie Kollisionen BEIDES zum Lesen und Schreiben, dies erfordert eine Schleife, um zum zu springen nächste Kandidatenposition und ein Test für jeden von ihnen, um den effektiven Quellindex zu vergleichen ...)

Darüber hinaus kann Java Hashmaps nur Objekte indizieren, und das Erstellen eines Integer-Objekts für jeden Hash-Quellindex (diese Objekterstellung wird für jeden Lesevorgang und nicht nur für Schreibvorgänge benötigt) ist im Hinblick auf Speicheroperationen kostspielig, da dies den Garbage Collector belastet .

Ich hatte wirklich gehofft, dass die JRE eine IntegerTrieMap <Object> als Standardimplementierung für die langsame HashMap <Integer, Object> oder LongTrieMap <Object> als Standardimplementierung für die noch langsamere HashMap <Long, Object> enthält immer noch nicht der Fall.

Sie fragen sich vielleicht, was ein Trie ist?

Es ist nur ein kleines Array von Ganzzahlen (in einem kleineren Bereich als der gesamte Koordinatenbereich für Ihre Matrix), mit dem die Koordinaten einer ganzzahligen Position in einem Vektor zugeordnet werden können.

Angenommen, Sie möchten eine 1024 * 1024-Matrix, die nur wenige Werte ungleich Null enthält. Anstatt diese Matrix in einem Array mit 1024 * 1024 Elementen (mehr als 1 Million) zu speichern, möchten Sie sie möglicherweise nur in Unterbereiche der Größe 16 * 16 aufteilen, und Sie benötigen nur 64 * 64 solcher Unterbereiche.

In diesem Fall enthält der Trie-Index nur 64 * 64 Ganzzahlen (4096), und es gibt mindestens 16 * 16 Datenelemente (die die Standardnullen oder den häufigsten Teilbereich in Ihrer Sparse-Matrix enthalten).

Und der Vektor, der zum Speichern der Werte verwendet wird, enthält nur 1 Kopie für Unterbereiche, die gleich sind (die meisten von ihnen sind voller Nullen und werden durch denselben Unterbereich dargestellt).

Anstatt eine Syntax wie zu verwenden matrix[i][j], würden Sie eine Syntax wie: verwenden.

trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] +
            ((i & 15) << 4) + (j & 15)]

Dies wird bequemer mit einer Zugriffsmethode für das Trie-Objekt gehandhabt.

Hier ist ein Beispiel, das in eine kommentierte Klasse integriert ist (ich hoffe, es wird OK kompiliert, da es vereinfacht wurde; signalisieren Sie mir, wenn es Fehler zu korrigieren gibt):

/**
 * Implement a sparse matrix. Currently limited to a static size
 * (<code>SIZE_I</code>, <code>SIZE_I</code>).
 */
public class DoubleTrie {

    /* Matrix logical options */        
    public static final int SIZE_I = 1024;
    public static final int SIZE_J = 1024;
    public static final double DEFAULT_VALUE = 0.0;

    /* Internal splitting options */
    private static final int SUBRANGEBITS_I = 4;
    private static final int SUBRANGEBITS_J = 4;

    /* Internal derived splitting constants */
    private static final int SUBRANGE_I =
        1 << SUBRANGEBITS_I;
    private static final int SUBRANGE_J =
        1 << SUBRANGEBITS_J;
    private static final int SUBRANGEMASK_I =
        SUBRANGE_I - 1;
    private static final int SUBRANGEMASK_J =
        SUBRANGE_J - 1;
    private static final int SUBRANGE_POSITIONS =
        SUBRANGE_I * SUBRANGE_J;

    /* Internal derived default values for constructors */
    private static final int SUBRANGES_I =
        (SIZE_I + SUBRANGE_I - 1) / SUBRANGE_I;
    private static final int SUBRANGES_J =
        (SIZE_J + SUBRANGE_J - 1) / SUBRANGE_J;
    private static final int SUBRANGES =
        SUBRANGES_I * SUBRANGES_J;
    private static final int DEFAULT_POSITIONS[] =
        new int[SUBRANGES](0);
    private static final double DEFAULT_VALUES[] =
        new double[SUBRANGE_POSITIONS](DEFAULT_VALUE);

    /* Internal fast computations of the splitting subrange and offset. */
    private static final int subrangeOf(
            final int i, final int j) {
        return (i >> SUBRANGEBITS_I) * SUBRANGE_J +
               (j >> SUBRANGEBITS_J);
    }
    private static final int positionOffsetOf(
            final int i, final int j) {
        return (i & SUBRANGEMASK_I) * MAX_J +
               (j & SUBRANGEMASK_J);
    }

    /**
     * Utility missing in java.lang.System for arrays of comparable
     * component types, including all native types like double here.
     */
    public static final int arraycompare(
            final double[] values1, final int position1,
            final double[] values2, final int position2,
            final int length) {
        if (position1 >= 0 && position2 >= 0 && length >= 0) {
            while (length-- > 0) {
                double value1, value2;
                if ((value1 = values1[position1 + length]) !=
                    (value2 = values2[position2 + length])) {
                    /* Note: NaN values are different from everything including
                     * all Nan values; they are are also neigher lower than nor
                     * greater than everything including NaN. Note that the two
                     * infinite values, as well as denormal values, are exactly
                     * ordered and comparable with <, <=, ==, >=, >=, !=. Note
                     * that in comments below, infinite is considered "defined".
                     */
                    if (value1 < value2)
                        return -1;        /* defined < defined. */
                    if (value1 > value2)
                        return 1;         /* defined > defined. */
                    if (value1 == value2)
                        return 0;         /* defined == defined. */
                    /* One or both are NaN. */
                    if (value1 == value1) /* Is not a NaN? */
                        return -1;        /* defined < NaN. */
                    if (value2 == value2) /* Is not a NaN? */
                        return 1;         /* NaN > defined. */
                    /* Otherwise, both are NaN: check their precise bits in
                     * range 0x7FF0000000000001L..0x7FFFFFFFFFFFFFFFL
                     * including the canonical 0x7FF8000000000000L, or in
                     * range 0xFFF0000000000001L..0xFFFFFFFFFFFFFFFFL.
                     * Needed for sort stability only (NaNs are otherwise
                     * unordered).
                     */
                    long raw1, raw2;
                    if ((raw1 = Double.doubleToRawLongBits(value1)) !=
                        (raw2 = Double.doubleToRawLongBits(value2)))
                        return raw1 < raw2 ? -1 : 1;
                    /* Otherwise the NaN are strictly equal, continue. */
                }
            }
            return 0;
        }
        throw new ArrayIndexOutOfBoundsException(
                "The positions and length can't be negative");
    }

    /**
     * Utility shortcut for comparing ranges in the same array.
     */
    public static final int arraycompare(
            final double[] values,
            final int position1, final int position2,
            final int length) {
        return arraycompare(values, position1, values, position2, length);
    }

    /**
     * Utility missing in java.lang.System for arrays of equalizable
     * component types, including all native types like double here.
     */ 
    public static final boolean arrayequals(
            final double[] values1, final int position1,
            final double[] values2, final int position2,
            final int length) {
        return arraycompare(values1, position1, values2, position2, length) ==
            0;
    }

    /**
     * Utility shortcut for identifying ranges in the same array.
     */
    public static final boolean arrayequals(
            final double[] values,
            final int position1, final int position2,
            final int length) {
        return arrayequals(values, position1, values, position2, length);
    }

    /**
     * Utility shortcut for copying ranges in the same array.
     */
    public static final void arraycopy(
            final double[] values,
            final int srcPosition, final int dstPosition,
            final int length) {
        arraycopy(values, srcPosition, values, dstPosition, length);
    }

    /**
     * Utility shortcut for resizing an array, preserving values at start.
     */
    public static final double[] arraysetlength(
            double[] values,
            final int newLength) {
        final int oldLength =
            values.length < newLength ? values.length : newLength;
        System.arraycopy(values, 0, values = new double[newLength], 0,
            oldLength);
        return values;
    }

    /* Internal instance members. */
    private double values[];
    private int subrangePositions[];
    private bool isSharedValues;
    private bool isSharedSubrangePositions;

    /* Internal method. */
    private final reset(
            final double[] values,
            final int[] subrangePositions) {
        this.isSharedValues =
            (this.values = values) == DEFAULT_VALUES;
        this.isSharedsubrangePositions =
            (this.subrangePositions = subrangePositions) ==
                DEFAULT_POSITIONS;
    }

    /**
     * Reset the matrix to fill it with the same initial value.
     *
     * @param initialValue  The value to set in all cell positions.
     */
    public reset(final double initialValue = DEFAULT_VALUE) {
        reset(
            (initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES :
                new double[SUBRANGE_POSITIONS](initialValue),
            DEFAULT_POSITIONS);
    }

    /**
     * Default constructor, using single default value.
     *
     * @param initialValue  Alternate default value to initialize all
     *                      positions in the matrix.
     */
    public DoubleTrie(final double initialValue = DEFAULT_VALUE) {
        this.reset(initialValue);
    }

    /**
     * This is a useful preinitialized instance containing the
     * DEFAULT_VALUE in all cells.
     */
    public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie();

    /**
     * Copy constructor. Note that the source trie may be immutable
     * or not; but this constructor will create a new mutable trie
     * even if the new trie initially shares some storage with its
     * source when that source also uses shared storage.
     */
    public DoubleTrie(final DoubleTrie source) {
        this.values = (this.isSharedValues =
            source.isSharedValues) ?
            source.values :
            source.values.clone();
        this.subrangePositions = (this.isSharedSubrangePositions =
            source.isSharedSubrangePositions) ?
            source.subrangePositions :
            source.subrangePositions.clone());
    }

    /**
     * Fast indexed getter.
     *
     * @param i  Row of position to set in the matrix.
     * @param j  Column of position to set in the matrix.
     * @return   The value stored in matrix at that position.
     */
    public double getAt(final int i, final int j) {
        return values[subrangePositions[subrangeOf(i, j)] +
                      positionOffsetOf(i, j)];
    }

    /**
     * Fast indexed setter.
     *
     * @param i      Row of position to set in the sparsed matrix.
     * @param j      Column of position to set in the sparsed matrix.
     * @param value  The value to set at this position.
     * @return       The passed value.
     * Note: this does not compact the sparsed matric after setting.
     * @see compact(void)
     */
    public double setAt(final int i, final int i, final double value) {
       final int subrange       = subrangeOf(i, j);
       final int positionOffset = positionOffsetOf(i, j);
       // Fast check to see if the assignment will change something.
       int subrangePosition, valuePosition;
       if (Double.compare(
               values[valuePosition =
                   (subrangePosition = subrangePositions[subrange]) +
                   positionOffset],
               value) != 0) {
               /* So we'll need to perform an effective assignment in values.
                * Check if the current subrange to assign is shared of not.
                * Note that we also include the DEFAULT_VALUES which may be
                * shared by several other (not tested) trie instances,
                * including those instanciated by the copy contructor. */
               if (isSharedValues) {
                   values = values.clone();
                   isSharedValues = false;
               }
               /* Scan all other subranges to check if the position in values
                * to assign is shared by another subrange. */
               for (int otherSubrange = subrangePositions.length;
                       --otherSubrange >= 0; ) {
                   if (otherSubrange != subrange)
                       continue; /* Ignore the target subrange. */
                   /* Note: the following test of range is safe with future
                    * interleaving of common subranges (TODO in compact()),
                    * even though, for now, subranges are sharing positions
                    * only between their common start and end position, so we
                    * could as well only perform the simpler test <code>
                    * (otherSubrangePosition == subrangePosition)</code>,
                    * instead of testing the two bounds of the positions
                    * interval of the other subrange. */
                   int otherSubrangePosition;
                   if ((otherSubrangePosition =
                           subrangePositions[otherSubrange]) >=
                           valuePosition &&
                           otherSubrangePosition + SUBRANGE_POSITIONS <
                           valuePosition) {
                       /* The target position is shared by some other
                        * subrange, we need to make it unique by cloning the
                        * subrange to a larger values vector, copying all the
                        * current subrange values at end of the new vector,
                        * before assigning the new value. This will require
                        * changing the position of the current subrange, but
                        * before doing that, we first need to check if the
                        * subrangePositions array itself is also shared
                        * between instances (including the DEFAULT_POSITIONS
                        * that should be preserved, and possible arrays
                        * shared by an external factory contructor whose
                        * source trie was declared immutable in a derived
                        * class). */
                       if (isSharedSubrangePositions) {
                           subrangePositions = subrangePositions.clone();
                           isSharedSubrangePositions = false;
                       }
                       /* TODO: no attempt is made to allocate less than a
                        * fully independant subrange, using possible
                        * interleaving: this would require scanning all
                        * other existing values to find a match for the
                        * modified subrange of values; but this could
                        * potentially leave positions (in the current subrange
                        * of values) unreferenced by any subrange, after the
                        * change of position for the current subrange. This
                        * scanning could be prohibitively long for each
                        * assignement, and for now it's assumed that compact()
                        * will be used later, after those assignements. */
                       values = setlengh(
                           values,
                           (subrangePositions[subrange] =
                            subrangePositions = values.length) +
                           SUBRANGE_POSITIONS);
                       valuePosition = subrangePositions + positionOffset;
                       break;
                   }
               }
               /* Now perform the effective assignment of the value. */
               values[valuePosition] = value;
           }
       }
       return value;
    }

    /**
     * Compact the storage of common subranges.
     * TODO: This is a simple implementation without interleaving, which
     * would offer a better data compression. However, interleaving with its
     * O(N²) complexity where N is the total length of values, should
     * be attempted only after this basic compression whose complexity is
     * O(n²) with n being SUBRANGE_POSITIIONS times smaller than N.
     */
    public void compact() {
        final int oldValuesLength = values.length;
        int newValuesLength = 0;
        for (int oldPosition = 0;
                 oldPosition < oldValuesLength;
                 oldPosition += SUBRANGE_POSITIONS) {
            int oldPosition = positions[subrange];
            bool commonSubrange = false;
            /* Scan values for possible common subranges. */
            for (int newPosition = newValuesLength;
                    (newPosition -= SUBRANGE_POSITIONS) >= 0; )
                if (arrayequals(values, newPosition, oldPosition,
                        SUBRANGE_POSITIONS)) {
                    commonSubrange = true;
                    /* Update the subrangePositions|] with all matching
                     * positions from oldPosition to newPosition. There may
                     * be several index to change, if the trie has already
                     * been compacted() before, and later reassigned. */
                    for (subrange = subrangePositions.length;
                         --subrange >= 0; )
                        if (subrangePositions[subrange] == oldPosition)
                            subrangePositions[subrange] = newPosition;
                    break;
                }
            if (!commonSubrange) {
                /* Move down the non-common values, if some previous
                 * subranges have been compressed when they were common.
                 */
                if (!commonSubrange && oldPosition != newValuesLength) {
                    arraycopy(values, oldPosition, newValuesLength,
                        SUBRANGE_POSITIONS);
                    /* Advance compressed values to preserve these new ones. */
                    newValuesLength += SUBRANGE_POSITIONS;
                }
            }
        }
        /* Check the number of compressed values. */
        if (newValuesLength < oldValuesLength) {
            values = values.arraysetlength(newValuesLength);
            isSharedValues = false;
        }
    }

}

Hinweis: Dieser Code ist nicht vollständig, da er eine einzelne Matrixgröße verarbeitet und sein Kompaktor nur gemeinsame Unterbereiche erkennt, ohne sie zu verschachteln.

Außerdem bestimmt der Code nicht, wo die beste Breite oder Höhe zum Aufteilen der Matrix in Unterbereiche (für x- oder y-Koordinaten) entsprechend der Matrixgröße verwendet werden kann. Es werden nur die gleichen statischen Unterbereichsgrößen von 16 (für beide Koordinaten) verwendet, es kann jedoch auch jede andere kleine Potenz von 2 (aber eine Nicht-Potenz von 2 würde die int indexOf(int, int)und int offsetOf(int, int)interne Methoden verlangsamen ), unabhängig für beide Koordinaten und höher auf die maximale Breite oder Höhe der Matrix. Idealerweise sollte die compact()Methode in der Lage sein, die besten Anpassungsgrößen zu bestimmen.

Wenn diese Aufspaltung Teilbereiche Größen variieren können, dann wird es notwendig sein , um beispielsweise Mitglieder für diese subrange Größen anstelle der statischen hinzufügen SUBRANGE_POSITIONS, und die statischen Methoden zu machen int subrangeOf(int i, int j)und int positionOffsetOf(int i, int j)in nicht statisch; und die Initialisierungsarrays DEFAULT_POSITIONSund DEFAULT_VALUESmüssen anders gelöscht oder neu definiert werden.

Wenn Sie Interleaving unterstützen möchten, teilen Sie zunächst die vorhandenen Werte in zwei Werte mit ungefähr derselben Größe (beide sind ein Vielfaches der minimalen Teilbereichsgröße, wobei die erste Teilmenge möglicherweise einen Teilbereich mehr als die zweite hat) und Sie scannen die größere an allen aufeinander folgenden Positionen, um eine passende Verschachtelung zu finden. Dann werden Sie versuchen, diese Werte abzugleichen. Dann werden Sie eine Schleife durchlaufen, indem Sie die Teilmengen in zwei Hälften teilen (auch ein Vielfaches der minimalen Teilbereichsgröße) und erneut scannen, um diese Teilmengen abzugleichen (dies multipliziert die Anzahl der Teilmengen mit 2: Sie müssen sich fragen, ob sich die Teilmengen verdoppelt haben Die Größe des subrangePositions-Index ist den Wert im Vergleich zur vorhandenen Größe der Werte wert, um festzustellen, ob er eine effektive Komprimierung bietet (wenn nicht, hören Sie dort auf: Sie haben die optimale Teilbereichsgröße direkt aus dem Interleaving-Komprimierungsprozess ermittelt. In diesem Fall; Die Größe des Unterbereichs kann während der Komprimierung geändert werden.

Dieser Code zeigt jedoch, wie Sie Werte ungleich Null zuweisen und das dataArray für zusätzliche Unterbereiche (ungleich Null) neu zuweisen. Anschließend können Sie die Speicherung dieser Daten ( compact()nachdem Zuweisungen mithilfe der setAt(int i, int j, double value)Methode durchgeführt wurden) optimieren, wenn Duplikate vorhanden sind Unterbereiche, die innerhalb der Daten vereinheitlicht und an derselben Position im subrangePositionsArray neu indiziert werden können .

Auf jeden Fall werden dort alle Prinzipien eines Versuchs umgesetzt:

1. Es ist immer schneller (und kompakter im Speicher, was eine bessere Lokalität bedeutet), eine Matrix unter Verwendung eines einzelnen Vektors anstelle eines doppelt indizierten Arrays von Arrays (jedes einzeln zugewiesen) darzustellen. Die Verbesserung ist in der double getAt(int, int)Methode sichtbar !

2. Sie sparen viel Platz, aber beim Zuweisen von Werten kann es einige Zeit dauern, neue Unterbereiche neu zuzuweisen. Aus diesem Grund sollten die Unterbereiche nicht zu klein sein, da sonst zu häufige Neuzuordnungen zum Einrichten Ihrer Matrix auftreten.

3. Es ist möglich, eine anfängliche große Matrix automatisch in eine kompaktere Matrix umzuwandeln, indem gemeinsame Unterbereiche erkannt werden. Eine typische Implementierung enthält dann eine Methode wie compact()oben. Wenn der Zugriff auf get () jedoch sehr schnell und set () sehr schnell ist, kann compact () sehr langsam sein, wenn viele gemeinsame Unterbereiche komprimiert werden müssen (z. B. wenn eine große, nicht dünn besetzte, zufällig gefüllte Matrix mit sich selbst subtrahiert wird oder multiplizieren Sie es mit Null: In diesem Fall ist es einfacher und viel schneller, den Versuch zurückzusetzen, indem Sie einen neuen instanziieren und den alten löschen.

4. Gemeinsame Unterbereiche verwenden gemeinsamen Speicher in den Daten, daher müssen diese gemeinsam genutzten Daten schreibgeschützt sein. Wenn Sie einen einzelnen Wert ändern müssen, ohne den Rest der Matrix zu ändern, müssen Sie zunächst sicherstellen, dass im subrangePositionsIndex nur einmal auf ihn verwiesen wird . Andernfalls müssen Sie einen neuen Unterbereich an einer beliebigen Stelle (bequemerweise am Ende) des valuesVektors zuweisen und dann die Position dieses neuen Unterbereichs im subrangePositionsIndex speichern .

Beachten Sie, dass die generische Colt-Bibliothek, obwohl sie sehr gut ist, bei der Arbeit mit spärlichen Matrizen nicht so gut ist, da sie Hashing- (oder zeilenkomprimierte) Techniken verwendet, die die Unterstützung für Versuche vorerst nicht implementieren, obwohl es sich um eine handelt Hervorragende Optimierung, die sowohl platzsparend als auch zeitsparend ist, insbesondere für die häufigsten getAt () -Operationen.

Selbst die hier für Versuche beschriebene Operation setAt () spart viel Zeit (der Weg wird hier implementiert, dh ohne automatische Komprimierung nach dem Einstellen, die je nach Bedarf und geschätzter Zeit implementiert werden könnte, bei der die Komprimierung noch viel Speicherplatz sparen würde Zeitpreis): Die Zeitersparnis ist proportional zur Anzahl der Zellen in Unterbereichen, und die Platzersparnis ist umgekehrt proportional zur Anzahl der Zellen pro Unterbereich. Ein guter Kompromiss, wenn dann eine Unterbereichsgröße wie die Anzahl der Zellen pro Unterbereich verwendet wird, ist die Quadratwurzel der Gesamtzahl der Zellen in einer 2D-Matrix (bei der Arbeit mit 3D-Matrizen wäre dies eine Kubikwurzel).

Hashing-Techniken, die in Colt-Sparse-Matrix-Implementierungen verwendet werden, haben den Nachteil, dass sie viel Speicheraufwand verursachen und die Zugriffszeit aufgrund möglicher Kollisionen verlangsamen. Versuche können alle Kollisionen vermeiden und können dann garantieren, dass im schlimmsten Fall lineare O (n) -Zeit bis O (1) -Zeit eingespart wird, wobei (n) die Anzahl möglicher Kollisionen ist (was im Fall einer spärlichen Matrix der Fall sein kann) bis zu der Anzahl der Zellen mit nicht standardmäßigem Wert in der Matrix, dh bis zur Gesamtzahl der Größe der Matrix multipliziert mit einem Faktor, der proportional zum Hashing-Füllfaktor ist, für eine nicht spärliche (dh vollständige Matrix).

Die in Colt verwendeten RC-Techniken (zeilenkomprimiert) sind näher an Tries, aber dies ist zu einem anderen Preis, hier die verwendeten Komprimierungstechniken, die eine sehr langsame Zugriffszeit für die häufigsten schreibgeschützten get () -Operationen haben und sehr langsam sind Komprimierung für setAt () -Operationen. Darüber hinaus ist die verwendete Komprimierung nicht orthogonal, anders als in dieser Darstellung von Versuchen, bei denen die Orthogonalität erhalten bleibt. Versuche würden auch sein, diese Orthogonalität für verwandte Betrachtungsoperationen wie Schreiten, Transposition (betrachtet als eine auf ganzzahligen zyklischen modularen Operationen basierende Schrittoperation), Unterordnung (und Unterauswahl im Allgemeinen, einschließlich mit Sortieransichten) beizubehalten.

Ich hoffe nur, dass Colt in Zukunft aktualisiert wird, um eine andere Implementierung mit Tries zu implementieren (dh TrieSparseMatrix anstelle von nur HashSparseMatrix und RCSparseMatrix). Die Ideen sind in diesem Artikel.

Die Trove-Implementierung (basierend auf int-> int-Maps) basiert ebenfalls auf Hashing-Techniken, die der HashedSparseMatrix von Colt ähneln, dh sie haben die gleichen Unannehmlichkeiten. Versuche werden viel schneller sein, mit einem moderaten zusätzlichen Speicherplatzbedarf (aber dieser Speicherplatz kann optimiert werden und in einer verzögerten Zeit sogar noch besser als Trove und Colt werden, indem eine endgültige compact () -Ionenoperation für die resultierende Matrix / Test durchgeführt wird).

Hinweis: Diese Trie-Implementierung ist an einen bestimmten nativen Typ gebunden (hier doppelt). Dies ist freiwillig, da die generische Implementierung unter Verwendung von Boxtypen einen enormen Platzbedarf hat (und in der Zugriffszeit viel langsamer ist). Hier werden nur native eindimensionale Arrays von Double anstelle von generischem Vector verwendet. Aber es ist sicherlich auch möglich, eine generische Implementierung für Tries abzuleiten ... Leider erlaubt Java immer noch nicht, wirklich generische Klassen mit allen Vorteilen nativer Typen zu schreiben, außer durch das Schreiben mehrerer Implementierungen (für einen generischen Objekttyp oder für jede nativer Typ) und Bedienung all dieser Vorgänge über eine Typfabrik. Die Sprache sollte in der Lage sein, die nativen Implementierungen automatisch zu instanziieren und die Factory automatisch zu erstellen (im Moment ist dies selbst in Java 7 nicht der Fall, und dies ist etwas, wo.

Das folgende Framework zum Testen von Java Matrix Libraries bietet auch eine gute Liste davon! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

Getestete Bibliotheken:

* Colt
* Commons Math
* Efficient Java Matrix Library (EJML)
* Jama
* jblas
* JScience (Older benchmarks only)
* Matrix Toolkit Java (MTJ)
* OjAlgo
* Parallel Colt
* Universal Java Matrix Package (UJMP) 

Das scheint einfach zu sein.

Sie können einen Binärbaum der Daten verwenden, indem Sie row * maxcolums + column als Index verwenden.

Um ein Element zu finden, berechnen Sie einfach row * maxcolums + column und durchsuchen den Baum nach ihm. Wenn es nicht vorhanden ist, können Sie null zurückgeben (es ist О (log n), wobei n die Anzahl der Zellen ist, die ein Objekt enthalten).

Wahrscheinlich nicht die schnellste Laufzeitlösung, aber die schnellste, die ich finden konnte, scheint zu funktionieren. Erstellen Sie eine Indexklasse und verwenden Sie sie als Schlüssel für eine SortedMap, z.

    SortedMap<Index, Object> entries = new TreeMap<Index, Object>();
    entries.put(new Index(1, 4), "1-4");
    entries.put(new Index(5555555555l, 767777777777l), "5555555555l-767777777777l");
    System.out.println(entries.size());
    System.out.println(entries.get(new Index(1, 4)));
    System.out.println(entries.get(new Index(5555555555l, 767777777777l)));

Meine Indexklasse sieht folgendermaßen aus (mit Hilfe des Eclipse-Codegenerators).

public static class Index implements Comparable<Index>
{
    private long x;
    private long y;

    public Index(long x, long y)
    {
        super();
        this.x = x;
        this.y = y;
    }

    public int compareTo(Index index)
    {
        long ix = index.x;
        if (ix == x)
        {
            long iy = index.y;
            if (iy == y)
            {
                return 0;
            }
            else if (iy < y)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }
        else if (ix < x)
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }

    public int hashCode()
    {
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + (int) (x ^ (x >>> 32));
        result = PRIME * result + (int) (y ^ (y >>> 32));
        return result;
    }

    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Index other = (Index) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    public long getX()
    {
        return x;
    }

    public long getY()
    {
        return y;
    }
}

Sie sollten sich die Bibliothek la4j (Lineare Algebra für Java) ansehen . Es unterstützt CRS (Compressed Row Storage) sowie CCS (Compressed Column Storage) interne Darstellungen für dünn besetzte Matrizen. Dies sind also die effizientesten und schnellsten internen Strukturen für spärliche Daten.

Hier ist das kurze Beispiel für die Verwendung spärlicher Matrizen in la4j :

Matrix a = new CRSMatrix(new double[][]{ // 'a' - CRS sparse matrix
   { 1.0, 0.0, 3.0 },
   { 0.0, 5.0, 0.0 },
   { 7.0, 0.0. 9.0 }
});

Matrix b = a.transpose(); // 'b' - CRS sparse matrix

Matrix c = b.multiply(a, Matrices.CCS_FACTORY); // 'c' = 'b' * 'a'; 
                                                // 'c' - CCS sparse matrix

Sie können einfach eine verschachtelte Karte verwenden. Wenn Sie jedoch eine Matrixberechnung durchführen müssen, ist dies möglicherweise nicht die beste Option

 Map<Integer, Map<integer, Object>> matrix;

Verwenden Sie anstelle von Objekt möglicherweise ein Tupel für die tatsächlichen Daten, damit Sie nach dem Extrahieren einfacher damit arbeiten können.

class Tuple<T extends yourDataObject> {
  public final int x;
  public final int y;
  public final T object;
}

class Matrix {
  private final Map<Integer, Map<interger, Tupple>> data = new...;

 void add(int x, int y, Object object) {
     data.get(x).put(new Tupple(x,y,object);
 }
}


//etc

Nullprüfung usw. der Kürze halber weggelassen

HashMap rockt. Verketten Sie einfach die Indizes (als Zeichenfolgen) mit einem Trennzeichen, z. B. '/', mit StringBuilder (nicht + oder String.format) und verwenden Sie dieses als Schlüssel. Schneller und speichereffizienter geht es nicht. Spärliche Matrizen sind soo 20. Jahrhundert. :-)