最右边的 n 个整数的总数

发布于 2024-10-08 22:20:04 字数 416 浏览 0 评论 0原文

我正在 Haskell 中实现 Bagwell 的理想哈希特里。要在子特里树中查找元素，他说要执行以下操作：

求符号 s 的弧，需要找到其对应的位位图中，然后计数地图中其下方一位计算有序索引子特里树。

最好的方法是什么？听起来最简单的方法是选择该位下面的位并对结果数字进行人口计数。有没有更快或更好的方法来做到这一点？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

月亮坠入山谷 2024-10-15 22:20:04

是的。特别是，mask 和 popcount 可以变得非常高效。作用如下：

static int mask(int hash, int shift){
    //return ((hash << shift) >>> 27);// & 0x01f;
    return (hash >>> shift) & 0x01f;
}

......

static int bitpos(int hash, int shift){
    return 1 << mask(hash, shift);
}

final int index(int bit){
    return Integer.bitCount(bitmap & (bit - 1));
}

Clojure 实现的

public INode assoc(int levelShift, int hash, Object key, Object val, Box addedLeaf){
    int bit = bitpos(hash, shift);
    int idx = index(bit);
    if((bitmap & bit) != 0)

这是我在我在 Haskell 中的实现中所做的事情：

type Key    = Word
type Bitmap = Word
type Shift  = Int
type Subkey = Int -- we need to use this to do shifts, so an Int it is

-- These architecture dependent constants

bitsPerSubkey :: Int
bitsPerSubkey = floor . logBase 2 . fromIntegral . bitSize $ (undefined :: Word)

subkeyMask :: Bitmap
subkeyMask = 1 `shiftL` bitsPerSubkey - 1

maskIndex :: Bitmap -> Bitmap -> Int
maskIndex b m = popCount (b .&. (m - 1))

mask :: Key -> Shift -> Bitmap
mask k s = shiftL 1 (subkey k s)

{-# INLINE subkey #-}
subkey :: Key -> Shift -> Int
subkey k s = fromIntegral $ shiftR k s .&. subkeyMask

Yes. In particular, mask and popcount can be made to be quite efficient. Here is what the Clojure implementation does:

static int mask(int hash, int shift){
    //return ((hash << shift) >>> 27);// & 0x01f;
    return (hash >>> shift) & 0x01f;
}

...

static int bitpos(int hash, int shift){
    return 1 << mask(hash, shift);
}

final int index(int bit){
    return Integer.bitCount(bitmap & (bit - 1));
}

...

public INode assoc(int levelShift, int hash, Object key, Object val, Box addedLeaf){
    int bit = bitpos(hash, shift);
    int idx = index(bit);
    if((bitmap & bit) != 0)

Here is what I did in my implementation in Haskell:

type Key    = Word
type Bitmap = Word
type Shift  = Int
type Subkey = Int -- we need to use this to do shifts, so an Int it is

-- These architecture dependent constants

bitsPerSubkey :: Int
bitsPerSubkey = floor . logBase 2 . fromIntegral . bitSize $ (undefined :: Word)

subkeyMask :: Bitmap
subkeyMask = 1 `shiftL` bitsPerSubkey - 1

maskIndex :: Bitmap -> Bitmap -> Int
maskIndex b m = popCount (b .&. (m - 1))

mask :: Key -> Shift -> Bitmap
mask k s = shiftL 1 (subkey k s)

{-# INLINE subkey #-}
subkey :: Key -> Shift -> Int
subkey k s = fromIntegral $ shiftR k s .&. subkeyMask

回复收藏 0 原文

~没有更多了~