8

我们认为位矩阵是一个包含大小为 的整数行的(n x m)规则数组。nm

我查看了Hacker's Delight和其他来源，我为此找到的算法相当专业：具有 8x8、32x32、64x64 等两种大小的幂的方阵（这是正常的，因为机器是这样构建的）。

我想到了一种更通用的算法（对于任意nand m），在最坏的情况下，它具有预期的复杂性（我认为），但是对于包含大部分相似列或零多于一的矩阵，该算法似乎更有趣（在极端情况下，如果矩阵一遍又一遍地包含同一行，则它是线性的）。它遵循一种二元决策图操作。

输出不是转置矩阵，而是压缩转置矩阵：一个对列表，(V,L)其中L是int_m表示转置矩阵的行（通过设置相应位置的位）应包含int_n V. 未出现在任何对中的转置矩阵的行用 填充0。

例如，对于矩阵

1010111
1111000
0001010

有转置的

110
010
110
011
100
101
100

算法输出：

(010,0100000)
(011,0001000)
(100,0000101)
(101,0000010)
(110,1010000)

并且将这对读(100,0000101)作“将值100放在转置矩阵的第 5 行和第 7 行”的意思。

这是算法（用伪 OCaml/C 编写）和上例中算法的进度图。

我们将根据三元组来运行(index_of_current_line, V, L)，它的类型是(int, int_n, int_m)，其中int_n是 n 位宽整数的类型，并且int只是一个机器整数，其宽度足以容纳n。该函数获取这些三元组的列表、矩阵、行数和用于输出的累加器，(list of pairs (int_m, int_n))并在某个点返回该累加器。

list of (int_n, int_m) transpose(list of triple t, 
                                int_m[n] mat, 
                                int n,  
                                list of (int_n, int_m) acc)

转置函数的第一次调用是

transpose([(0, 0, 2^m-1)], mat, n, []).

取“&”、“|” "xor" 是通常的按位运算

transpose(t, mat, n, acc) =
 match t with 
  | [] -> (* the list is empty, we're done *)
    return acc
  | (i, v, l)::tt -> 
    let colIn = mat[i] & l in
    (* colIn contains the positions that were set in the parent's mask "l" 
     and that are also set in the line "i" *)
    match colIn with
    |0 -> (* None of the positions are set in both, do not branch *)
     if (i<n) then (* not done with the matrix, simply move to next line *)
      transpose((i+1,v,l)::tt,mat,n,acc)
     else (* we reached the end of the matrix, we're at a leaf *)
       if (v>0) then
         transpose(tt,mat,n,(v,l)::acc)
       else  (* We ignore the null values and continue *)
         transpose(tt,mat,n,acc)
     |_ -> (* colIn is non null, ie some of the positions set at the parent
              mask "l" are also set in this line. If ALL the positions are, we 
              do not branch either. If only some of them are and some of them
              are not, we branch *)
         (* First, update v *)
        let vv = v | (2^(n-i-1)) in
         (* Then get the mask for the other branch *)
        let colOut = colIn xor l in, 
        match colOut with
        | 0 -> (* All are in, none are out, no need to branch *)
            if (i<n) then
                transpose((i+1,vv,colIn)::tt,mat,n,acc)
            else (* we reached the end of the matrix, we're at a leaf *)             
               transpose(tt,mat,n,(vv,colIn)::acc)
        | _ -> (* Some in, some out : now we branch *)
            if (i<n) then 
               transpose((i+1,vv,colIn)::(i+1,v,colOut)::tt,mat,n,acc)
            else 
             if (v>0) then
               transpose(tt,mat,n,(vv,colIn)::(v,colOut)::acc)
             else
               transpose(tt,mat,n,(vv,colIn)::acc)

在此处输入图像描述

请注意，如果矩阵的宽度大于高度，则它会更快（例如，如果 n = 3 和 m = 64）

我的问题是：

  • 这有趣和/或有用吗？
  • 我在重新发明轮子吗？
  • “几乎为零”矩阵或“小微分线”矩阵是否足够常见以至于有趣？

PS：如果有什么不清楚的地方，请告诉我，我会重写任何需要的！

4

0 回答 0