表示短位串的最佳方式是什么？

Question

我想表示最多 120 位左右的字符串，速度很关键。我需要能够通过重复的 snoc 操作来构建位串，然后通过重复的 uncons 操作来使用它。一种想法是从 data-dword 窃取 Word128 的实现并使用类似这样的东西来构建：

empty = 1
snoc xs x = (xs `shiftL` 1) .|. x

但 unconsing 似乎有点难看，必须先 countLeadingZeros 并向左移动以消除它们，然后才能通过移动和屏蔽高位来读取元素。

是否有更愉快的方式至少同样快，或者更快的方式不是太令人不快？

上下文

Phil Ruffwind 已经为 Data.Map 提出了 lens 的 at 的一个版本，但是到目前为止所有的实现都比 lens 当前使用的原始实现要慢得多当密钥比较便宜时。如果我可以在查找条目时生成一个非常廉价的路径表示，然后使用 insert 或 delete 的专用版本非常有效地使用它，那么也许我可以让这变得有价值。

Answer 1

我不确定这是否符合条件。我担心我正在以某种形式重新实现 countLeadingZeros...

无论如何，这个想法是从左边开始，向右移动。然后，我们可以使用 x-1 和 XOR "count" x 的尾随零。 "count" 的结果是掩码“00..01..11”，它大致是尾随零的一元表示。我们不将此一元转换为二进制，因为我们不需要：通过一些位级的工作，我们可以取消转换。

以下是未经测试和验证的代码。

import Data.Word
import Data.Bits
import Text.Printf

type T = Word64     -- can be adapted to any WordN

-- for pretty printing
pr :: T -> String
pr x = printf "%064b\n" x

empty :: T
empty = shiftL 1 63

snoc :: T -> T -> T
snoc x xs = shiftR xs 1 .|. (shiftL x 63)

-- returns (head, tail)
-- head is not normalized (0 or 1), only (0 or /=0)
uncons :: T -> (T, T)
uncons xs = 
   let -- example
       -- 0101001100000000000   xs  
       y = (xs `xor` (xs - 1))
       -- 0000000111111111111   y
       z = shiftR y 1 + 1
       -- 0000000100000000000   z
       z' = shiftL z 1
       -- 0000001000000000000   z'
   in (xs .&. z' , (xs .&. complement z) .|. z' )

表示短位串的最佳方式是什么？

What's the best way to represent a short bit string?

dictionary

haskell

bit-manipulation

haskell-lens

上下文