blocks|key|1664018|text|这似乎很简单。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1664019|您可以使用row*maxcolums%2Bcolumn作为索引来使用数据的二叉树。|1664020|要查找项，您只需计算row*maxcolums%2Bcolumn并在树中查找它，如果不存在，则可以返回null+(它是О(log+)，其中n是包含对象的单元格的数量)。|1664021|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

This seems to be simple.

You could use a binary tree of the data using row*maxcolums+column as an index.

To find item, you simply calculate row*maxcolums+column and binary search the tree looking for it, if it's not there, you can return null (it's О(log n) where n is the number of cells which contain an object).

blocks|key|1664101|text|可能不是最快的运行时解决方案，但我能想到的最快的运行时解决方案似乎是有效的。创建索引类并将其用作SortedMap的键，如下所示：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1664102|++++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)));|code-block|syntax|javascript|1664103|我的Index类看起来像这样(在Eclipse代码生成器的帮助下)。|1664104|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+%2B+(int)+(x+%5E+(x+>>>+32));
++++++++result+=+PRIME+*+result+%2B+(int)+(y+%5E+(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;
++++}
}|1664105|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Not the fastest runtime solution probably, but the fastest I could come up with that seems to work. Create an Index class and use it as a key for a SortedMap, like:

<pre><code> SortedMap&lt;Index, Object&gt; entries = new TreeMap&lt;Index, Object&gt;();
 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)));
</code></pre>

My Index class looks like this (with some help from Eclipse code generator).

<pre><code>public static class Index implements Comparable&lt;Index&gt;
{
 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 &lt; y)
 {
 return -1;
 }
 else
 {
 return 1;
 }
 }
 else if (ix &lt; x)
 {
 return -1;
 }
 else
 {
 return 1;
 }
 }

 public int hashCode()
 {
 final int PRIME = 31;
 int result = 1;
 result = PRIME * result + (int) (x ^ (x &gt;&gt;&gt; 32));
 result = PRIME * result + (int) (y ^ (y &gt;&gt;&gt; 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;
 }
}
</code></pre>

blocks|key|1449270|text|您可以只使用嵌套的map，但如果需要在其上进行矩阵演算，这可能不是最好的选择|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1449271|+Map<Integer,+Map<integer,+Object>>+matrix;|code-block|syntax|javascript|1449272|也许用一些元组代替对象来表示实际数据，这样在提取之后你就可以更容易地使用它，比如：|1449273|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|1449274|为简洁起见，省略了null检查等|1449275|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

you could just use a nested map although if you need to do matrix calculus on it that might not be the best option

<pre><code> Map&lt;Integer, Map&lt;integer, Object&gt;&gt; matrix;
</code></pre>

maybe instead of object use some tuple for the actual data so you can work with it easier after extraction, something like:

<pre><code>class Tuple&lt;T extends yourDataObject&gt; {
 public final int x;
 public final int y;
 public final T object;
}

class Matrix {
 private final Map&lt;Integer, Map&lt;interger, Tupple&gt;&gt; data = new...;

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


//etc
</code></pre>

null check etc omitted for brevity

blocks|key|1449333|text|下面是测试Java+Matrix+Libraries的框架，还提供了这些！https://lessthanoptimal.github.io/Java-Matrix-Benchmark/的一个很好的列表|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1449334|已测试的库：|1449335|*+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)+|code-block|syntax|javascript|1449336|entityMap|0|LINK|mutability|MUTABLE|url|https://lessthanoptimal.github.io/Java-Matrix-Benchmark/^0|11|1K|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@$A|T|B|U|1|V]]|C|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|X|8|@]|9|@]|C|$I|J]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]]]

Following framework to test Java Matrix Libraries, provides also a good list of these!
<a href="https://lessthanoptimal.github.io/Java-Matrix-Benchmark/" rel="nofollow noreferrer">https://lessthanoptimal.github.io/Java-Matrix-Benchmark/</a>

Tested Libraries:

<pre><code>* 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) 
</code></pre>

blocks|key|1664269|text|你应该看看la4j+(线性代数for+Java)库。它支持稀疏矩阵的CRS+(Compressed+Row+Storage)和CCS+(Compressed+Column+Storage)内部表示。因此，这些是稀疏数据最高效、最快速的内部结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1664270|下面是在la4j中使用稀疏矩阵的简单示例|1664271|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|code-block|syntax|javascript|1664272|entityMap|0|LINK|mutability|MUTABLE|url|http://la4j.org/|1|http://netlib.org/utk/papers/templates/node91.html|2|http://netlib.org/utk/papers/templates/node92.html|3^0|5|4|0|Y|S|1|1R|V|2|0|4|4|3|0|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@$A|Y|B|Z|1|10]|$A|11|B|12|1|13]|$A|14|B|15|1|16]]|C|$]]|$1|D|3|E|5|6|7|17|8|@]|9|@$A|18|B|19|1|1A]]|C|$]]|$1|F|3|G|5|H|7|1B|8|@]|9|@]|C|$I|J]]|$1|K|3|-4|5|6|7|1C|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|R]]|S|$5|N|O|P|C|$Q|T]]|U|$5|N|O|P|C|$Q|V]]|W|$5|N|O|P|C|$Q|R]]]]

You migth look at <a href="http://la4j.org" rel="nofollow">la4j</a> (Linear Algebra for Java) library. It supports <a href="http://netlib.org/utk/papers/templates/node91.html" rel="nofollow">CRS (Compressed Row Storage)</a> as well as <a href="http://netlib.org/utk/papers/templates/node92.html" rel="nofollow">CCS (Compressed Column Storage)</a> internal representaions for sparse matrices. So, these are the most efficient and fast internal stuctures for sparse data.

Here is the brief example of using sparse matrices in <a href="http://la4j.org" rel="nofollow">la4j</a>:

<pre><code>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
</code></pre>

blocks|key|1449424|text|HashMap很棒。只需使用StringBuilder+(而不是%2B或String.format)将索引(作为字符串)与分隔符连接起来，例如'/'，并将其用作键。没有比这更快、更高效的内存了。稀疏矩阵在20世纪是非常流行的。:-)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1449425|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

HashMap rocks. Just concatenate the indexes (as strings) with a separator, say '/', using StringBuilder (not + or String.format), and use that as the key. You can't get faster and more memory-efficient than that. Sparse matrices are soo 20th century. :-)

I'm working on a project, written in Java, which requires that I build a very large 2-D sparse array. Very sparse, if that makes a difference. Anyway: the most crucial aspect for this application is efficency in terms of time (assume loads of memory, though not nearly so unlimited as to allow me to use a standard 2-D array -- the key range is in the billions in both dimensions).

Out of the kajillion cells in the array, there will be several hundred thousand cells which contain an object. I need to be able to modify cell contents VERY quickly.

Anyway: Does anyone know a particularly good library for this purpose? It would have to be Berkeley, LGPL or similar license (no GPL, as the product can't be entirely open-sourced). Or if there's just a very simple way to make a homebrew sparse array object, that'd be fine too.

I'm considering <a href="http://ressim.berlios.de/" rel="noreferrer">MTJ</a>, but haven't heard any opinions on its quality.

Sparse matrices / arrays in Java

我正在做一个用Java编写的项目，它需要我构建一个非常大的2-D稀疏数组。非常稀疏，如果这有区别的话。无论如何:这个应用程序最关键的方面是时间效率(假设内存负载很大，尽管不是无限的，以至于我可以使用标准的2-D数组--键的范围在两个维度上都有数十亿)。在数组中的kajillion单元之外，将有数十万个单元包含一个对象。...

问Java中的稀疏矩阵/数组
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java中的稀疏矩阵/数组EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java中的稀疏矩阵/数组
EN