Matrici/array sparsi in Java
https://stackoverflow.com/questions/390181
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto lavorando a un progetto, scritto in Java, che richiede la creazione di un array sparso 2D molto grande.Molto scarso, se questo fa la differenza.Comunque:l'aspetto più cruciale per questa applicazione è l'efficienza in termini di tempo (si presuppone un sacco di memoria, anche se non così illimitato da permettermi di utilizzare un array 2D standard: l'intervallo chiave è di miliardi in entrambe le dimensioni).
Dei kajillion di celle dell'array, ci saranno diverse centinaia di migliaia di celle che contengono un oggetto.Devo essere in grado di modificare il contenuto della cella MOLTO rapidamente.
Comunque:Qualcuno conosce una biblioteca particolarmente adatta a questo scopo?Dovrebbe essere Berkeley, LGPL o una licenza simile (non GPL, poiché il prodotto non può essere interamente open source).O se c'è solo un modo molto semplice per creare un oggetto array sparso fatto in casa, andrebbe bene anche quello.
sto considerando MTJ, ma non ho sentito alcun parere sulla sua qualità.
Soluzione
Gli array sparsi creati con hashmap sono molto inefficienti per i dati letti di frequente.Le implementazioni più efficienti utilizzano un Trie che consente l'accesso a un singolo vettore in cui sono distribuiti i segmenti.
Un Trie può calcolare se un elemento è presente nella tabella eseguendo solo DUE indicizzazioni di array di sola lettura per ottenere la posizione effettiva in cui è memorizzato un elemento o per sapere se è assente dall'archivio sottostante.
Può anche fornire una posizione predefinita nell'archivio di backup per il valore predefinito dell'array sparso, in modo che non sia necessario NESSUN test sull'indice restituito, poiché Trie garantisce che tutti i possibili indici di origine verranno mappati almeno su quello predefinito posizione nell'archivio di backup (dove memorizzerai spesso uno zero, una stringa vuota o un oggetto nullo).
Esistono implementazioni che supportano tentativi aggiornabili rapidamente, con un'operazione opzionale "compact()" per ottimizzare la dimensione dell'archivio di backup al termine di più operazioni.I tentativi sono MOLTO più veloci degli hashmap, perché non necessitano di alcuna funzione di hashing complessa e non hanno bisogno di gestire le collisioni per le letture (con Hashmaps, hai collisioni SIA per la lettura che per la scrittura, questo richiede un ciclo per passare al posizione del candidato successivo, e un test su ciascuno di essi per confrontare l'effettivo indice di provenienza...)
Inoltre, Java Hashmaps può indicizzare solo oggetti e la creazione di un oggetto Integer per ogni indice sorgente con hash (la creazione di questo oggetto sarà necessaria per ogni lettura, non solo per la scrittura) è costosa in termini di operazioni di memoria, poiché stressa il garbage collector. .
Speravo davvero che JRE includesse un IntegerTrieMap<Object> come implementazione predefinita per il lento HashMap<Integer, Object> o LongTrieMap<Object> come implementazione predefinita per l'ancora più lento HashMap<Long, Object>...Ma non è ancora così.
Potresti chiederti cos'è un Trie?
È solo un piccolo array di numeri interi (in un intervallo più piccolo dell'intero intervallo di coordinate della matrice) che consente di mappare le coordinate in una posizione intera in un vettore.
Ad esempio, supponiamo di volere una matrice 1024*1024 contenente solo pochi valori diversi da zero.Invece di memorizzare quella matrice in un array contenente 1024*1024 elementi (più di 1 milione), potresti semplicemente dividerla in sottointervalli di dimensione 16*16 e avrai solo bisogno di 64*64 sottointervalli di questo tipo.
In tal caso, l'indice Trie conterrà solo 64*64 interi (4096) e ci saranno almeno 16*16 elementi di dati (contenenti gli zeri predefiniti o il sottointervallo più comune trovato nella matrice sparsa).
E il vettore utilizzato per memorizzare i valori conterrà solo 1 copia per i sottointervalli uguali tra loro (la maggior parte di essi essendo piena di zeri, saranno rappresentati dallo stesso sottointervallo).
Quindi, invece di usare una sintassi come matrix[i][j], dovresti usare una sintassi come:
trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] +
((i & 15) << 4) + (j & 15)]
che sarà gestito più convenientemente utilizzando un metodo di accesso per l'oggetto trie.
Ecco un esempio, integrato in una classe commentata (spero che venga compilato correttamente, poiché è stato semplificato;segnalatemi se ci sono errori da correggere):
/**
* 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:questo codice non è completo perché gestisce una singola dimensione di matrice e il suo compattatore è limitato a rilevare solo sottointervalli comuni, senza interlacciarli.
Inoltre, il codice non determina quale sia la larghezza o l'altezza migliore da utilizzare per suddividere la matrice in sottointervalli (per le coordinate xey), in base alla dimensione della matrice.Utilizza semplicemente le stesse dimensioni del sottointervallo statico di 16 (per entrambe le coordinate), ma potrebbe essere convenientemente qualsiasi altra piccola potenza di 2 (ma una potenza non pari a 2 rallenterebbe il int indexOf(int, int) E int offsetOf(int, int) metodi interni), indipendentemente per entrambe le coordinate, e fino alla larghezza o altezza massima della matrice. Idealmente il compact() Il metodo dovrebbe essere in grado di determinare le taglie più adatte.
Se le dimensioni di questi sottointervalli di suddivisione possono variare, sarà necessario aggiungere membri di istanza per queste dimensioni di sottointervallo anziché quelli statici SUBRANGE_POSITIONS, e per creare metodi statici int subrangeOf(int i, int j) E int positionOffsetOf(int i, int j) in non statico;e gli array di inizializzazione DEFAULT_POSITIONSE DEFAULT_VALUES dovrà essere eliminato o ridefinito diversamente.
Se vuoi supportare l'interleaving, in pratica inizierai dividendo i valori esistenti in due della stessa dimensione (entrambi multipli della dimensione minima del sottointervallo, il primo sottoinsieme possibilmente avendo un sottointervallo in più rispetto al secondo), e scansionerai quello più grande in tutte le posizioni successive per trovare un interlacciamento corrispondente;quindi proverai a far corrispondere questi valori.Quindi eseguirai un ciclo ricorsivo dividendo i sottoinsiemi a metà (anche un multiplo della dimensione minima del sottointervallo) ed eseguirai nuovamente la scansione per abbinare questi sottoinsiemi (questo moltiplicherà il numero di sottoinsiemi per 2:devi chiederti se la dimensione raddoppiata dell'indice subrangePositions vale il valore rispetto alla dimensione esistente dei valori per vedere se offre una compressione efficace (in caso contrario, ti fermi qui:hai trovato la dimensione ottimale del sottointervallo direttamente dal processo di compressione dell'interleaving).In quel caso;la dimensione del sottointervallo sarà modificabile, durante la compattazione.
Ma questo codice mostra come assegnare valori diversi da zero e riallocare il file data array per sottointervalli aggiuntivi (diversi da zero) e quindi come ottimizzare (con compact() dopo che gli incarichi sono stati eseguiti utilizzando il file setAt(int i, int j, double value) metodo) la memorizzazione di questi dati quando sono presenti sottointervalli duplicati che possono essere unificati all'interno dei dati e reindicizzati nella stessa posizione nel subrangePositions vettore.
Ad ogni modo, lì vengono implementati tutti i principi di un trie:
È sempre più veloce (e più compatto in memoria, il che significa una migliore località) rappresentare una matrice utilizzando un singolo vettore invece di un array di array con doppia indicizzazione (ciascuno allocato separatamente).Il miglioramento è visibile nel
double getAt(int, int)metodo !Si risparmia molto spazio, ma quando si assegnano valori potrebbe essere necessario del tempo per riallocare nuovi sottointervalli.Per questo motivo, i sottointervalli non dovrebbero essere troppo piccoli altrimenti le riallocazioni avverranno troppo frequentemente per impostare la matrice.
È possibile trasformare automaticamente una matrice iniziale grande in una matrice più compatta rilevando sottointervalli comuni.Un'implementazione tipica conterrà quindi un metodo come
compact()Sopra.Tuttavia, se l'accesso a get() è molto veloce e set() è abbastanza veloce, compact() potrebbe essere molto lento se ci sono molti sottointervalli comuni da comprimere (ad esempio quando si sottrae con se stessa una grande matrice non sparsa riempita casualmente o moltiplicandolo per zero:in quel caso sarà più semplice e molto più veloce resettare il trie istanziandone uno nuovo ed eliminando quello vecchio).Gli intervalli secondari comuni utilizzano l'archiviazione comune nei dati, quindi questi dati condivisi devono essere di sola lettura.Se è necessario modificare un singolo valore senza modificare il resto della matrice, è necessario innanzitutto assicurarsi che venga fatto riferimento solo una volta nella matrice
subrangePositionsindice.Altrimenti dovrai allocare un nuovo sottointervallo ovunque (convenientemente alla fine) del filevaluesvettore, quindi memorizzare la posizione di questo nuovo sottointervallo nel filesubrangePositionsindice.
Da notare che la libreria Colt generica, anche se molto buona così com'è, non è altrettanto buona quando si lavora su matrici sparse, perché utilizza tecniche di hashing (o compressione di riga) che per ora non implementano il supporto per i tentativi, nonostante sia una libreria ottima ottimizzazione, che è allo stesso tempo salvaspazio E risparmio di tempo, in particolare per le operazioni getAt() più frequenti.
Anche l'operazione setAt() qui descritta per i tentativi fa risparmiare molto tempo (il modo in cui è implementato qui, ad es.senza compattazione automatica dopo l'impostazione, che potrebbe comunque essere implementata in base alla domanda e al tempo stimato laddove la compattazione farebbe comunque risparmiare molto spazio di stoccaggio al prezzo del tempo):il risparmio di tempo è proporzionale al numero di celle nei sottointervalli e il risparmio di spazio è inversamente proporzionale al numero di celle per sottointervallo.Un buon compromesso se si utilizza quindi una dimensione del sottointervallo tale che il numero di celle per sottointervallo sia la radice quadrata del numero totale di celle in una matrice 2D (sarebbe una radice cubica quando si lavora con una matrice 3D).
Le tecniche di hashing utilizzate nelle implementazioni a matrice sparsa di Colt presentano l'inconveniente di aggiungere molto sovraccarico di archiviazione e tempi di accesso lenti a causa di possibili collisioni.I tentativi possono evitare tutte le collisioni e quindi garantire di risparmiare tempo lineare da O(n) a O(1) nei casi peggiori, dove (n) è il numero di possibili collisioni (che, in caso di matrice sparsa, può essere fino al numero di celle con valore diverso da quello predefinito nella matrice, ovverofino al numero totale di dimensioni della matrice moltiplicato per un fattore proporzionale al fattore di riempimento dell'hashing, per un non-sparse cioèmatrice completa).
Le tecniche RC (row-compressed) usate in Colt sono più vicine a Tries, ma questo ha un altro prezzo, qui le tecniche di compressione usate, che hanno tempi di accesso molto lenti per le operazioni get() di sola lettura più frequenti, e molto lente compressione per le operazioni setAt().Inoltre, la compressione utilizzata non è ortogonale, a differenza di questa presentazione di Tries dove viene preservata l'ortogonalità.Si cercherà anche di preservare questa ortogonalità per operazioni di visualizzazione correlate come lo striding, la trasposizione (vista come un'operazione di striding basata su operazioni modulari cicliche di numeri interi), il subranging (e le sottoselezioni in generale, comprese le viste di ordinamento).
Spero solo che Colt venga aggiornato in futuro per implementare un'altra implementazione utilizzando Tries (ad es.TrieSparseMatrix invece che solo HashSparseMatrix e RCSparseMatrix).Le idee sono in questo articolo.
L'implementazione di Trove (basata su mappe int->int) si basa anche su tecniche di hashing simili a HashedSparseMatrix di Colt, ovverohanno lo stesso inconveniente.I tentativi saranno molto più veloci, con un moderato spazio aggiuntivo consumato (ma questo spazio può essere ottimizzato e diventare anche migliore di Trove e Colt, in un tempo differito, utilizzando un'operazione di compattazione finale sulla matrice/trie risultante).
Nota:questa implementazione di Trie è legata a un tipo nativo specifico (qui double).Questo è volontario, perché l'implementazione generica che utilizza i tipi boxing ha un enorme sovraccarico di spazio (e è molto più lenta nel tempo di accesso).Qui utilizza solo array unidimensionali nativi di vettore doppio anziché generico.Ma è certamente possibile ricavare un'implementazione generica anche per Tries...Sfortunatamente, Java non consente ancora di scrivere classi veramente generiche con tutti i vantaggi dei tipi nativi, tranne la scrittura di implementazioni multiple (per un tipo di oggetto generico o per ciascun tipo nativo) e l'esecuzione di tutte queste operazioni tramite una type factory.Il linguaggio dovrebbe essere in grado di istanziare automaticamente le implementazioni native e costruire automaticamente la factory (per ora non è così nemmeno in Java 7, e questo è qualcosa in cui .Net mantiene ancora il suo vantaggio per tipi veramente generici che sono veloci quanto quelli nativi tipi).
Altri suggerimenti
A seguito quadro per testare Java Matrix Biblioteche, fornisce anche una buona lista di questi! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/
Biblioteche testati:
* 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)
Questo sembra essere semplice.
Si potrebbe usare un albero binario dei dati utilizzando fila * maxcolums + colonna come un indice.
Per trovare voce, è sufficiente calcolare fila * maxcolums + colonna e ricerca binaria l'albero alla ricerca di esso, se non è lì, si può restituire null (è О (log n), dove n è il numero di celle che contengono un oggetto).
Non è la soluzione di runtime più veloce, probabilmente, ma il più veloce che poteva venire con che sembra funzionare. Creare una classe di indice e usarlo come una chiave per una SortedMap, come:
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)));
La mia classe Index si presenta così (con qualche aiuto da generatore di codice 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;
}
}
la4j biblioteca (Algebra lineare per Java). Supporta CRS (Compressed Row Storage) così come CCS (Colonna compressa Storage) representaions interne per matrici sparse. Quindi, queste sono le Costruzioni interni più efficienti e veloci per i dati sparse.
Ecco la breve esempio di utilizzo di matrici sparse 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
si potrebbe utilizzare una mappa nidificato anche se avete bisogno di fare calcolo matriciale su di esso che potrebbe non essere la migliore opzione
Map<Integer, Map<integer, Object>> matrix;
Forse, invece di utilizzare alcuni oggetti tuple per i dati reali in modo da poter lavorare con più facile dopo l'estrazione, qualcosa come:
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
nullo controllare ecc omesse per brevità
rocce HashMap. Basta concatenare gli indici (come stringhe) con un separatore, dire '/', utilizzando StringBuilder (non + o String.Format), e l'uso che come chiave. Non è possibile ottenere più velocemente e più memoria-efficiente di quello. matrici sparse sono soo 20 ° secolo. : -)
