2

我正在使用一个Nx3行N数非常大的位矩阵，比如说2^40。
一个典型的矩阵是这样的 

000
001
010
011
...

我做这样的事情

transform_row(5); //return 000
transform_row(10); //return 101
assemble_array(000,101); 
//return a 10x3 matrix, where:
//row 5: 000
//row 10: 101
//the other rows wait for the other iteration to be filled

...//repeat

initial_matrixmy和中的位模式transformed_matrix要么非常冗余，要么非常备用。例如，第一列可以只有0，也可以有巨大的1.

在这种情况下，我有哪些组装和有效压缩的选择？
我应该推出自己的组装算法，还是可以使用一些压缩库？
我正在考虑自己动手，因为我不知道压缩库是否可以在这种连续情况下有效地工作。

我assemble_array在 GPU 上并行执行。
所以函数需要是线程安全的、关联的和可交换的。

bit_matrix_transform.cu

bit_matrix initial_matrix;
first=0;
last=2^40;
UnaryFunction bit_vector transform_row::operator(long row_index);
BinaryFunction bit_matrix assemble_array::operator(bit_array x, bit_array y);
bit_matrix transformed_matrix = thrust::transform_reduce(first, last, transform_row, init, assemble_array);
//a bit_array being either a bit_vector or a bit_matrix
4

1 回答 1

1

我将从数组的简单游程表示开始，将其初始化为 2^40 个零的运行。（或者，如果零与空不同，则使用 -1 或 8。）初始运行长度表示将只是 2^40, 0。当您插入一个元素时，您会将一次运行分成两个。因此，要将 111 放在位置 n（从零开始计数），您会得到 n, 0, 1, 7, 2^40-n-1, 0。如果我在第一个相邻的位置插入另一个 111，我会这样做一次运行：n, 0, 2, 7, 2^40-n-2, 0。依此类推。

如果位级别的相关性多于三位级别，则执行此操作 3 次，每列位执行一次。

于 2012-05-30T15:36:28.183 回答