在CRS稀疏矩阵中查找值？

2013-03-18 57 views 0 likes

我是使用稀疏矩阵的新手，但现在需要在我的工作中利用一个来节省空间。据我所知，下面的矩阵：在CRS稀疏矩阵中查找值？

10 0 0 0 -2 0 
3 9 0 0 0 3 
0 7 8 7 0 0 
3 0 8 7 5 0 
0 8 0 9 9 13 
0 4 0 0 2 -1

可以与这样的三个矢量来表示：

[10 -2 3 9 3 7 8 7 3 8 7 5 8 9 9 13 3 2 -1] // nonzero_vals 

[1 5 1 2 6 2 3 4 1 3 4 5 2 4 5 6 2 5 6] // col_indices 

[1 3 6 9 13 17 20] // row_ptr (indices of values that start row)

我的问题是现在确定用于在O（1）时间值查找适当的方程式。例如，如果我想要返回位置（2,2）处存储的矩阵值，我该如何返回9？另外，如果查找坐标未在稀疏矩阵中表示，那么在O（1）时间内如何返回0？

我很感谢您提供的任何帮助。我确信这方面有很好的方程式，但我无法找到它们。

来源

2013-03-18 user1764386

回答

没有为在任意（I，J）获得的值没有O（1）过程坐标（至少在没有预处理）。通过对列索引的二分搜索程序，您可以做的最好的平均值为O（log N）（其中矩阵是MxN）。 ^*

_{*好了，说实在的，为O（log k）的，其中ķ是行非零的个数。但是，如果假定密度与矩阵大小无关（通常是这种情况），那么O（logN）是有效的。}

来源

2013-03-18 22:30:21

什么是正确（最快）的过程来做一个查找呢？（对于CSR矩阵） – user1764386 2013-03-18 23:15:36

@ user1764386：那么，您可以在相同的时间内获得相关的row_ptr值。然后使用这些在col_indices数组上绑定二进制搜索。 – 2013-03-18 23:16:42

在CRS稀疏矩阵中查找值？

回答

相关问题