Кол-во посещений наименьших чисел n целых чисел

Question

Я реализую Bagwell's Ideal Hash Trie в Haskell. Чтобы найти элемент в суб-синтаксического дерева, он говорит, чтобы сделать следующее:

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

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

Answer 1

Да. В частности, маска и 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) 

Вот что я сделал в 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