java algorithm sparse-matrix sparse-array

Matrices/matrices dispersas en Java



algorithm sparse-matrix (11)

Estoy trabajando en un proyecto, escrito en Java, que requiere que construya una matriz dispersa 2-D muy grande. Muy escaso, si eso hace la diferencia. De todos modos: el aspecto más crucial para esta aplicación es la eficiencia en términos de tiempo (suponga mucha memoria, aunque no tan ilimitada como para permitirme usar una matriz 2D estándar; el rango clave está en los miles de millones en ambas dimensiones )

Fuera de las células kajillion en la matriz, habrá varios cientos de miles de células que contienen un objeto. Necesito poder modificar contenido de la célula MUY rápido.

De todos modos: ¿Alguien conoce una biblioteca particularmente buena para este propósito? Tendría que ser Berkeley, LGPL o una licencia similar (no GPL, ya que el producto no puede ser de fuente abierta). O si simplemente hay una forma muy simple de hacer un objeto de matriz dispersa homebrew, estaría bien también.

Estoy considerando MTJ , pero no he escuchado ninguna opinión sobre su calidad.

podrías simplemente usar un mapa anidado, aunque si necesitas hacer un cálculo matricial no podría ser la mejor opción

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

Tal vez en lugar de utilizar algún objeto, una tupla para los datos reales para que pueda trabajar con él más fácilmente después de la extracción, algo como:

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

null check etc se omite por brevedad

Esto parece ser simple.

Puede usar un árbol binario de los datos usando la columna row * maxcolums + como índice.

Para encontrar el artículo, simplemente calcula row * maxcolums + column y binary busca en el árbol que lo busca, si no está allí, puede devolver null (es О (log n) donde n es el número de celdas que contienen un objeto).

No es la solución de tiempo de ejecución más rápida, pero la más rápida que pude encontrar parece funcionar. Cree una clase Index y úselo como clave para SortedMap, como:

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)));

Mi clase Index se ve así (con algo de ayuda del generador de código Eclipse).

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; } }

Quizás Colt sea ​​de ayuda. Proporciona una implementación de matriz dispersa.

Acabo de utilizar Trove, que proporcionó un rendimiento mucho mejor que Colt, mientras usaba el mapa int-> int (utilizado para implementar una matriz dispersa).

Puede ver la biblioteca la4j (Linear Algebra for Java). Es compatible con CRS (Almacenamiento de filas comprimidas) , así como representaciones internas CCS (almacenamiento de columnas comprimidas) para matrices dispersas. Por lo tanto, estas son las estructuras internas más eficientes y rápidas para datos dispersos.

Aquí está el breve ejemplo del uso de matrices dispersas en 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

Las matrices de Sparsed construidas con hashmaps son muy ineficientes para los datos de lectura frecuente. Las implementaciones más eficientes utilizan un Trie que permite el acceso a un único vector donde se distribuyen los segmentos.

Un Trie puede calcular si un elemento está presente en la tabla al realizar solo la indexación de matriz DOS de solo lectura para obtener la posición efectiva donde se almacena un elemento, o para saber si está ausente de la tienda subyacente.

También puede proporcionar una posición predeterminada en el almacén de respaldo para el valor predeterminado de la matriz espaciada, para que no necesite NINGUNA prueba en el índice devuelto, porque Trie garantiza que todos los índices de origen posibles se correlacionarán al menos con el valor predeterminado posición en la tienda de respaldo (donde con frecuencia almacenará un cero, o una cadena vacía o un objeto nulo).

Existen implementaciones que soportan las pruebas de actualización rápida, con una operación "compacta ()" opcional para optimizar el tamaño de la tienda de respaldo al final de las operaciones múltiples. Los intentos son MUCHO más rápidos que los hashmaps, porque no necesitan ninguna función de hashing compleja, y no necesitan manejar colisiones para lecturas (con Hashmaps, tienes colisión AMBOS para leer y para escribir, esto requiere un bucle para saltar al próximo puesto de candidato, y una prueba en cada uno de ellos para comparar el índice de fuente efectiva ...)

Además, Java Hashmaps solo puede indexar objetos y crear un objeto entero para cada índice fuente en hash (esta creación de objetos será necesaria para cada lectura, no solo para escritura) es costoso en términos de operaciones de memoria, ya que acentúa el recolector de basura .

Realmente esperaba que el JRE incluyera un <Object> IntegerTrieMap como la implementación predeterminada para el HashMap lento <Integer, Object> o LongTrieMap <Object> como la implementación predeterminada para el HashMap <Long, Object> aún más lento ... ... Pero esto es todavía no es el caso.

¿Te preguntas qué es un Trie?

Es solo una pequeña matriz de enteros (en un rango menor que el rango completo de coordenadas para su matriz) que permite mapear las coordenadas en una posición entera en un vector.

Por ejemplo, supongamos que quiere una matriz 1024 * 1024 que contiene solo unos pocos valores distintos de cero. En lugar de almacenar esa matriz en una matriz que contiene 1024 * 1024 elementos (más de 1 millón), es posible que desee dividirla en subintervalos de tamaño 16 * 16, y solo necesitará 64 * 64 de esos subintervalos.

En ese caso, el índice Trie contendrá solo 64 * 64 enteros (4096), y habrá al menos 16 * 16 elementos de datos (que contienen los ceros predeterminados, o el subrango más común encontrado en su matriz dispersa).

Y el vector utilizado para almacenar los valores contendrá solo 1 copia para los subintervalos que son iguales entre sí (la mayoría de ellos están llenos de ceros, estarán representados por el mismo subrango).

Entonces, en lugar de usar una sintaxis como matrix[i][j] , usarías una sintaxis como:

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

que será manejado más convenientemente usando un método de acceso para el objeto trie.

Aquí hay un ejemplo, integrado en una clase comentada (espero que compile bien, ya que fue simplificado, me indica si hay errores para corregir):

/** * 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; } } }

Nota: este código no está completo porque maneja un único tamaño de matriz, y su compactador está limitado para detectar solo subrangos comunes, sin intercalarlos.

Además, el código no determina dónde es el mejor ancho o alto para usar para dividir la matriz en subrangos (para coordenadas xey), de acuerdo con el tamaño de la matriz. Simplemente usa los mismos tamaños de subintervalos estáticos de 16 (para ambas coordenadas), pero podría ser convenientemente cualquier otra pequeña potencia de 2 (pero una no potencia de 2 ralentizaría el int indexOf(int, int) y int offsetOf(int, int) métodos internos), de forma independiente para ambas coordenadas, y hasta el ancho o alto máximo de la matriz. De forma especial, el método compact() debería poder determinar los mejores tamaños de ajuste.

Si estos tamaños de subrangos de división pueden variar, será necesario agregar miembros de instancia para estos tamaños de SUBRANGE_POSITIONS lugar de SUBRANGE_POSITIONS estáticas, y para hacer que los métodos estáticos int subrangeOf(int i, int j) y int positionOffsetOf(int i, int j) en no estático; y las matrices de inicialización DEFAULT_POSITIONS y DEFAULT_VALUES necesitarán descartarse o redefinirse de manera diferente.

Si desea admitir el entrelazado, básicamente comenzará dividiendo los valores existentes en dos de aproximadamente el mismo tamaño (siendo ambos un múltiplo del tamaño mínimo del subrango, el primer subconjunto posiblemente tenga un subrango más que el segundo), y escanearás la más grande en todas las posiciones sucesivas para encontrar un entrelazado coincidente; entonces intentará hacer coincidir estos valores. Luego, repetirá recíprocamente dividiendo los subconjuntos en mitades (también un múltiplo del tamaño mínimo del subrango) y escaneará nuevamente para hacer coincidir estos subconjuntos (esto multiplicará el número de subconjuntos por 2: debe preguntarse si el doble tamaño del subordenar índice de posiciones vale el valor en comparación con el tamaño existente de los valores para ver si ofrece una compresión efectiva (si no, se detiene allí: ha encontrado el tamaño de subrango óptimo directamente desde el proceso de compresión de entrelazado). caso, el tamaño del subrango será mutable, durante la compactación.

Pero este código muestra cómo asigna valores distintos de cero y reasigna la matriz de data para subrangos adicionales (distintos de cero), y luego cómo puede optimizar (con compact() después de que se hayan realizado asignaciones usando setAt(int i, int j, double value) método de setAt(int i, int j, double value) el almacenamiento de estos datos cuando existen subrangos duplicados que pueden unificarse dentro de los datos, y reindexados en la misma posición en la matriz de subrangePositions .

De todos modos, todos los principios de un trie se implementan allí:

  1. Siempre es más rápido (y más compacto en la memoria, lo que significa mejor ubicación) para representar una matriz utilizando un solo vector en lugar de una matriz de matrices de doble índice (cada una asignada por separado). ¡La mejora es visible en el double getAt(int, int) !

  2. Ahorras mucho espacio, pero al asignar valores puede llevar tiempo reasignar nuevos subintervalos. Por esta razón, los subrangos no deberían ser demasiado pequeños o las reasignaciones ocurrirán con demasiada frecuencia para configurar su matriz.

  3. Es posible transformar una matriz grande inicial automáticamente en una matriz más compacta mediante la detección de subrangos comunes. Una implementación típica contendrá un método como compact() arriba. Sin embargo, si el acceso get () es muy rápido y set () es bastante rápido, compact () puede ser muy lento si hay muchos subrangos comunes para comprimir (por ejemplo, al sustraer una gran matriz no dispersa aleatoriamente llena consigo misma , o multiplicándolo por cero: será más simple y mucho más rápido en ese caso restablecer el trie al instanciar uno nuevo y soltar el anterior).

  4. Los subrangos comunes usan almacenamiento común en los datos, por lo que estos datos compartidos deben ser de solo lectura. Si debe cambiar un solo valor sin cambiar el resto de la matriz, primero debe asegurarse de que solo se haga referencia a él una vez en el índice de subrangePositions . De lo contrario, tendrá que asignar un nuevo subrango en cualquier lugar (convenientemente al final) del vector de values , y luego almacenar la posición de este nuevo subrango en el índice de subrangePositions .

Tenga en cuenta que la biblioteca genérica de Colt, aunque es muy buena, no es tan buena cuando se trabaja con matrices dispersas, ya que utiliza técnicas de hash (o de compresión de filas) que no implementan el soporte para intentos por el momento, a pesar de que es excelente optimización, que ahorra espacio y ahorra tiempo, especialmente para las operaciones getAt () más frecuentes.

Incluso la operación setAt () descrita aquí para intentos ahorra mucho tiempo (el camino se implementa aquí, es decir, sin compactación automática después de la configuración, que aún podría implementarse en función de la demanda y el tiempo estimado donde la compactación aún ahorraría mucho espacio de almacenamiento en el precio del tiempo): el ahorro de tiempo es proporcional al número de celdas en subrangos, y el ahorro de espacio es inversamente proporcional al número de celdas por subrango. Un buen compromiso si luego se usa un tamaño de subrango, como la cantidad de celdas por subrango, es la raíz cuadrada del número total de celdas en una matriz 2D (sería una raíz cúbica cuando se trabaja con matrices 3D).

Las técnicas de hash utilizadas en las implementaciones de matrices dispersas de Colt tienen el inconveniente de que agregan una gran cantidad de gastos generales de almacenamiento y un tiempo de acceso lento debido a posibles colisiones. Tries puede evitar todas las colisiones y puede entonces garantizar el ahorro de O (n) lineal en O (1) tiempo en los peores casos, donde (n) es el número de posibles colisiones (que, en el caso de una matriz dispersa, puede ser hasta el número de celdas con valores no predeterminados en la matriz, es decir, hasta el número total de tamaños de la matriz multiplicado por un factor proporcional al factor de relleno hash, para una matriz no dispersa, es decir, completa).

Las técnicas RC (fila comprimida) utilizadas en Colt están más cerca de Tries, pero esto tiene otro precio, aquí las técnicas de compresión utilizadas, que tienen un tiempo de acceso muy lento para las operaciones get () de lectura más lentas y muy lentas compresión para operaciones setAt (). Además, la compresión utilizada no es ortogonal, a diferencia de esta presentación de Tries donde se preserva la ortogonalidad. También se preservaría esta ortogonalidad para operaciones de visualización relacionadas, como zancadas, transposición (vista como una operación de zancada en base a operaciones modulares cíclicas enteras), suborganización (y subsecciones en general, incluso con vistas ordenadas).

Solo espero que Colt se actualice en algún futuro para implementar otra implementación usando Tries (es decir, TrieSparseMatrix en lugar de solo HashSparseMatrix y RCSparseMatrix). Las ideas están en este artículo.

La implementación de Trove (basada en int-> int maps) también se basa en técnicas de hash similares a la HashedSparseMatrix del Colt, es decir, tienen el mismo inconveniente. Las pruebas serán mucho más rápidas, con un espacio adicional moderado consumido (pero este espacio se puede optimizar e incluso ser mejor que Trove y Colt, en un tiempo diferido, utilizando una operación iónica compacta final () en la matriz / trie resultante).

Nota: esta implementación de Trie está vinculada a un tipo nativo específico (aquí doble). Esto es voluntario, porque la implementación genérica usando tipos de boxeo tiene una gran sobrecarga de espacio (y son mucho más lentos en el tiempo de acceso). Aquí solo utiliza matrices unidimensionales nativas de vectores en lugar de genéricos. Pero también es posible obtener una implementación genérica para Tries ... Desafortunadamente, Java aún no permite escribir clases genéricas con todos los beneficios de los tipos nativos, excepto al escribir múltiples implementaciones (para un tipo de Objeto genérico o para cada tipo nativo) y al servicio de todas estas operaciones a través de una fábrica de tipos. El lenguaje debería ser capaz de instanciar automáticamente las implementaciones nativas y construir la fábrica automáticamente (por ahora no es el caso incluso en Java 7, y esto es algo donde .Net aún mantiene su ventaja para tipos realmente genéricos que son tan rápidos como nativos tipos).

HashMap rocas. Simplemente concatene los índices (como cadenas) con un separador, diga ''/'', usando StringBuilder (no + o String.format), y úselo como la clave. No puede ser más rápido y más eficiente con la memoria que eso. Las matrices dispersas son tan del siglo XX. :-)

El siguiente marco para probar Java Matrix Libraries, ¡también proporciona una buena lista de estos! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

Bibliotecas probadas:

* 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)