小编Zak*_*akC的帖子

我们认为位矩阵(nxm)是包含n行的大小为m的常规数组整数.

我查看了Hacker's Delight和其他来源,我发现的算法是相当专业的:方形矩阵的大小为2,8x8,32x32,64x64(这是正常的,因为机器是这样构建的).

我想到了一个更通用的算法(对于任意的n和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的机器整数.该函数获取这些三元组的列表,矩阵,行数和输出的累加器(对的列表(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 …

我的理解是"纯OCaml"意味着OCaml中标准的一切,包括其非 "纯粹"功能特征,而"纯功能"意味着通常的属性:没有副作用,没有异常处理等.从这个意义上说,"纯OCaml"实现与OCaml相反,例如,C或C++实现.

然而,最近我和一个非常坚持认为"纯OCaml"的人在某些圈子里,对OCaml的"纯粹功能子集"进行了辩论.

这两个含义在社区中是否真正使用过？是否存在这种歧义？是否有指向某些备受推崇的消息来源在第二种意义上使用"纯OCaml"？