Численность населения самых правых n целых чисел - PullRequest
Новая
       22

Численность населения самых правых n целых чисел

2 голосов
/ 27 декабря 2010

Я использую идеальный хеш-код Бэгвелла в Хаскеле. Чтобы найти элемент в поддереве, он говорит сделать следующее:

Нахождение дуги для символа s, требует поиска соответствующего бита в битовой карте, а затем считая один бит под ним на карте, чтобы вычислить индекс в порядке суб-Trie.

Каков наилучший способ сделать это? Похоже, что самый простой способ сделать это - выбрать биты ниже этого бита и выполнить подсчет населения по полученному числу. Есть ли более быстрый или лучший способ сделать это?

1 Ответ

4 голосов
/ 27 декабря 2010

Да. В частности, маска и popcount могут быть сделаны достаточно эффективными. Вот что делает реализация Clojure: 

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)

Вот что я сделал в моей реализации на 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
...