Matrizes / matrizes esparsas em Java

Eu estou trabalhando em um projeto, escrito em Java, que requer que eu construa uma matriz esparsa 2-D muito grande. Muito escasso, se isso faz diferença. De qualquer forma: o aspecto mais crucial para esta aplicação é a eficiência em termos de tempo (assumir cargas de memory, embora não seja tão ilimitado a ponto de permitir o uso de uma matriz 2-D padrão – o intervalo chave é de bilhões em ambas as dimensões) ).

Das células kajillion na matriz, haverá várias centenas de milhares de células que contêm um object. Eu preciso ser capaz de modificar o conteúdo da célula muito rapidamente.

Enfim: Alguém conhece uma biblioteca particularmente boa para esse propósito? Teria de ser Berkeley, LGPL ou licença similar (sem GPL, pois o produto não pode ser totalmente aberto). Ou se há apenas uma maneira muito simples de fazer um object de matriz esparsa homebrew, isso seria ótimo também.

Estou considerando o MTJ , mas não ouvi nenhuma opinião sobre sua qualidade.

Matrizes sparsed construídas com hashmaps são muito ineficientes para dados lidos com freqüência. As implementações mais eficientes usam um Trie que permite o access a um único vetor onde os segmentos são distribuídos.

Um Trie pode calcular se um elemento está presente na tabela executando somente indexação de matriz TWO somente leitura para obter a posição efetiva onde um elemento é armazenado ou para saber se ele está ausente do armazenamento subjacente.

Ele também pode fornecer uma posição padrão no armazenamento de backup para o valor padrão da matriz sparsed, para que você não precise de ANY test no índice retornado, porque o Trie garante que todo possível índice de origem seja mapeado pelo menos para o padrão posição no backing store (onde você frequentemente armazena um zero ou uma string vazia ou um object nulo).

Existem implementações que oferecem suporte a Tries atualizável rapidamente, com uma operação otional “compact ()” para otimizar o tamanho do armazenamento de backup no final de várias operações. Tentativas são MUITO mais rápidas que hashmaps, porque elas não precisam de nenhuma function complexa de hash, e não precisam lidar com colisões para leituras (com Hashmaps, você tem colisão tanto para leitura quanto para escrita, isso requer um loop para pular para o próxima posição do candidato e um teste em cada um deles para comparar o índice de fonte efetiva …)

Além disso, o Java Hashmaps só pode indexar em Objetos, e criar um object Integer para cada índice de origem hash (essa criação de object será necessária para cada leitura, não apenas gravações) é dispendiosa em termos de operações de memory, pois enfatiza o coletor de lixo .

Eu realmente esperava que o JRE incluísse um IntegerTrieMap como a implementação padrão para o lento HashMap ou LongTrieMap como a implementação padrão para o HashMap mais lento … Mas isso é ainda não é o caso.



Você pode se perguntar o que é uma Trie?

É apenas uma pequena matriz de números inteiros (em um intervalo menor que o intervalo completo de coordenadas para sua matriz) que permite mapear as coordenadas em uma posição inteira em um vetor.

Por exemplo, suponha que você queira uma matriz 1024 * 1024 contendo apenas alguns valores diferentes de zero. Em vez de armazenar essa matriz em uma matriz contendo 1024 * 1024 elementos (mais de 1 milhão), você pode apenas querer dividi-la em sub-tamanhos de tamanho 16 * 16, e você só precisará de 64 * 64 desses sub-intervalos.

Nesse caso, o índice Trie conterá apenas 64 * 64 inteiros (4096), e haverá pelo menos 16 * 16 elementos de dados (contendo os zeros padrão, ou o sub-intervalo mais comum encontrado em sua matriz esparsa).

E o vetor usado para armazenar os valores conterá apenas 1 cópia para subranges que são iguais entre si (a maioria deles é cheia de zeros, eles serão representados pelo mesmo subintervalo).

Então, ao invés de usar uma syntax como matrix[i][j] , você usaria uma syntax como:

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

que será mais convenientemente tratado usando um método de access para o object trie.

Aqui está um exemplo, construído em uma class comentada (espero que compile OK, como foi simplificado; avise-me se houver erros para corrigir):

 /** * Implement a sparse matrix. Currently limited to a static size * (SIZE_I, SIZE_I). */ 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  * (otherSubrangePosition == subrangePosition), * 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 não está completo porque manipula um único tamanho de matriz e seu compactador é limitado para detectar apenas sub-intervalos comuns, sem intercalá-los.

Além disso, o código não determina onde é a melhor largura ou altura a ser usada para dividir a matriz em sub-intervalos (para coordenadas x ou y), de acordo com o tamanho da matriz. Ele usa apenas os mesmos tamanhos estáticos de subintervalos de 16 (para ambas as coordenadas), mas poderia ser convenientemente qualquer outra pequena potência de 2 (mas um poder não de 2 retardaria o int indexOf(int, int) e int offsetOf(int, int) methods internos), independentemente para ambas as coordenadas, e até a largura ou altura máxima da matriz. raramente o método compact() deve ser capaz de determinar os melhores tamanhos de assembly.

Se esses tamanhos de subfaixa de divisão puderem variar, haverá a necessidade de include membros de instância para esses tamanhos de subintervalo em vez de SUBRANGE_POSITIONS estáticos e de tornar os methods estáticos int subrangeOf(int i, int j) e int positionOffsetOf(int i, int j) em não estático; e os arrays de boot DEFAULT_POSITIONS e DEFAULT_VALUES precisarão ser eliminados ou redefinidos de forma diferente.

Se você quiser dar suporte à intercalação, basicamente começará dividindo os valores existentes em dois de aproximadamente o mesmo tamanho (ambos sendo um múltiplo do tamanho mínimo do subintervalo, o primeiro subconjunto possivelmente tendo mais um subintervalo que o segundo) e você digitalizará a maior em todas as posições sucessivas para encontrar uma intercalação correspondente; então você tentará combinar esses valores. Em seguida, você fará um loop recursivamente dividindo os subconjuntos em metades (também um múltiplo do tamanho mínimo do subintervalo) e fará a varredura novamente para corresponder a esses subconjuntos (isso multiplicará o número de subconjuntos por 2: você deve se perguntar se o dobro O tamanho do índice subrangePositions vale o valor comparado ao tamanho existente dos valores para ver se ele oferece uma compactação efetiva (se não, você pára por aí: encontrou o tamanho ideal de subintervalo diretamente do processo de compactação da intercalação). caso, o tamanho do sub-intervalo será mutável, durante a compactação.

Mas esse código mostra como você atribui valores diferentes de zero e realoca a matriz de data para subfaixas adicionais (diferentes de zero) e como você pode otimizar (com compact() após as atribuições terem sido executadas usando o método setAt(int i, int j, double value) método) o armazenamento desses dados quando há sub-conjuntos duplicados que podem ser unificados nos dados e reindexados na mesma posição na matriz subrangePositions .

De qualquer forma, todos os princípios de um trie são implementados lá:

  1. É sempre mais rápido (e mais compacto na memory, ou seja, melhor localidade) para representar uma matriz usando um único vetor em vez de uma matriz de matrizes indexadas duplamente (cada uma alocada separadamente). A melhoria é visível no double getAt(int, int) !

  2. Você economiza muito espaço, mas ao atribuir valores, pode levar algum tempo para realocar novos sub-intervalos. Por esse motivo, os sub-intervalos não devem ser muito pequenos ou as realocações ocorrerão com muita frequência para configurar sua matriz.

  3. É possível transformar uma matriz grande inicial automaticamente em uma matriz mais compacta, detectando sub-escalas comuns. Uma implementação típica, em seguida, conterá um método como compact() acima. No entanto, se o access get () for muito rápido e set () for muito rápido, o compact () poderá ser muito lento se houver muitos subgrupos comuns a serem compactados (por exemplo, ao subtrair uma matriz grande e esparsa aleatoriamente com ela , ou multiplicando-o por zero: será mais simples e muito mais rápido, nesse caso, redefinir o arquivo instanciando um novo e descartando o antigo).

  4. As subfaixas comuns usam armazenamento comum nos dados, portanto, esses dados compartilhados devem ser somente leitura. Se você precisar alterar um único valor sem alterar o restante da matriz, primeiro certifique-se de que ele seja referenciado apenas uma vez no índice subrangePositions . Caso contrário, você precisará alocar um novo subintervalo em qualquer lugar (convenientemente no final) do vetor de values e, em seguida, armazenar a posição desse novo subintervalo no índice subrangePositions .



Note que a biblioteca genérica do Colt, apesar de muito boa como é, não é tão boa quando se trabalha em matrizes esparsas, porque usa técnicas de hashing (ou compactadas por linhas) que não implementam o suporte para tentativas por enquanto, apesar de ser uma excelente otimização, que economiza espaço e economia de tempo, notavelmente para as operações getAt () mais freqüentes.

Até mesmo a operação setAt () descrita aqui para tentativas economiza muito tempo (o caminho é implementado aqui, ou seja, sem compactação automática após a configuração, que ainda pode ser implementado com base na demanda e no tempo estimado em que a compactação ainda economiza muito espaço de armazenamento o preço do tempo): a economia de tempo é proporcional ao número de células em sub-intervalos e a economia de espaço é inversamente proporcional ao número de células por subintervalo. Um bom comprometimento se, então, usar um tamanho de subfaixa como o número de células por subfaixa é a raiz quadrada do número total de células em uma matriz 2D (seria uma raiz cúbica ao trabalhar com matriz 3D).

As técnicas de hashing usadas nas implementações de matriz esparsa do Colt têm o inconveniente de adicionar muita sobrecarga de armazenamento e diminuir o tempo de access devido a possíveis colisões. Tentativas podem evitar todas as colisões e podem, então, garantia para salvar tempo linear O (n) em O (1) nos piores casos, onde (n) é o número de possíveis colisões (que, em caso de matriz esparsa, pode ser até o número de células de valor não-padrão na matriz, ou seja, até o número total de tamanho da matriz vezes um fator proporcional ao fator de preenchimento de hashing, para uma matriz completa não esparsa, por exemplo).

As técnicas RC (compactadas em linha) usadas no Colt estão mais próximas de Tries, mas isso tem outro preço, aqui as técnicas de compactação usadas, que têm tempo de access muito lento para as operações get () somente de leitura mais frequentes e muito lentas compactação para operações setAt (). Além disso, a compression utilizada não é ortogonal, diferentemente desta apresentação de Tries onde a ortogonalidade é preservada. Tentativas também preservariam essa ortogonalidade para operações de visualização relacionadas, como striding, transposição (vista como uma operação de striding baseada em operações modulares cíclicas inteiras), sub-agrupamento (e subseleções em geral, incluindo visualizações de sorting).

Eu só espero que o Colt seja atualizado em algum futuro para implementar outra implementação usando Tries (ou seja, TrieSparseMatrix em vez de apenas HashSparseMatrix e RCSparseMatrix). As ideias estão neste artigo.

A implementação do Trove (baseada em int-> int maps) também é baseada em técnicas de hashing semelhantes ao HashedSparseMatrix do Colt, isto é, elas têm o mesmo inconveniente. As tentativas serão muito mais rápidas, com um espaço adicional moderado consumido (mas esse espaço pode ser otimizado e tornar-se ainda melhor do que o Trove e o Colt, em um tempo diferido, usando uma operação final compacta () na matriz / tríade resultante).

Nota: esta implementação Trie está vinculada a um tipo nativo específico (aqui duplo). Isso é voluntário, porque a implementação genérica usando tipos de boxe tem uma enorme sobrecarga de espaço (e é muito mais lenta no tempo de access). Aqui ele usa apenas matrizes unidimensionais nativas de vetores duplos em vez de genéricos. Mas certamente é possível derivar uma implementação genérica também para Tries ... Infelizmente, o Java ainda não permite escrever classs realmente genéricas com todos os benefícios de tipos nativos, exceto escrevendo múltiplas implementações (para um tipo de object genérico ou para cada tipo nativo), e servindo todas estas operações através de uma fábrica de tipos. A linguagem deve ser capaz de automaticamente instanciar as implementações nativas e construir a fábrica automaticamente (por enquanto não é o caso mesmo no Java 7, e isso é algo em que o .Net ainda mantém sua vantagem para tipos realmente genéricos que são tão rápidos quanto o nativo. tipos).

Seguindo a estrutura para testar Bibliotecas Java Matrix, fornece também uma boa lista destes! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

Bibliotecas testadas:

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

Aqui está um artigo em que você pode estar interessado e que fala sobre estruturas de dados para cálculos matriciais, incluindo matrizes esparsas:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.7544

Você pode baixar o papel como PDF ou PS. Inclui código-fonte também.

Talvez o Colt seja de ajuda. Ele fornece uma implementação de matriz esparsa.

Isso parece ser simples.

Você poderia usar uma tree binária dos dados usando a linha * maxcolums + column como um índice.

Para encontrar o item, você simplesmente calcula a linha * maxcolums + coluna e busca binária a tree que procura, se não estiver lá, você pode retornar null (é О (log n) onde n é o número de células que contém um object).

Não é a solução de tempo de execução mais rápida, provavelmente, mas o mais rápido que eu consegui criar parece funcionar. Crie uma class Index e use-a como chave para um SortedMap, como:

  SortedMap entries = new TreeMap(); 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))); 

Minha class Index se parece com isso (com alguma ajuda do gerador de código do Eclipse).

 public static class Index implements Comparable { 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; } } 

Acabei de usar o Trove, que forneceu um desempenho muito melhor do que o Colt, ao usar o int-> int map (usado para implementar uma matriz esparsa).

Você pode ver a biblioteca la4j (Linear Algebra for Java). Ele suporta CRS (Compressed Row Storage) , bem como representações internas CCS (Compressed Column Storage) para matrizes esparsas. Então, essas são as estruturas internas mais eficientes e rápidas para dados esparsos.

Aqui está o breve exemplo do uso de matrizes esparsas em 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 

você poderia apenas usar um mapa nested, embora se você precisar fazer cálculos matriciais que podem não ser a melhor opção

  Map> matrix; 

talvez em vez de usar objects alguma tupla para os dados reais para que você possa trabalhar com isso mais facilmente após a extração, algo como:

 class Tuple { public final int x; public final int y; public final T object; } class Matrix { private final Map> data = new...; void add(int x, int y, Object object) { data.get(x).put(new Tupple(x,y,object); } } //etc 

verificação de nulos, etc. omitido por brevidade

O SuanShu tem um conjunto de solucionadores de matriz esparsa Java e de matriz esparsa Java .

HashMap rocks. Apenas concatene os índices (como strings) com um separador, digamos ‘/’, usando StringBuilder (não + ou String.format), e use isso como a chave. Você não pode ficar mais rápido e mais eficiente em termos de memory do que isso. As matrizes esparsas são do século XX. 🙂