dongluan6784
2017-05-13 21:47 阅读 24
已采纳

哈希表:不进行转换的转换?

I am implementing a specialized hashtable. I'm trying store a lot of data in a single 64-bit int key, for space usage and performance reasons.

Each key should have this structure:

// Key structure, from LSB
// eval result (16 bits)
// move (16 bits)
// age (16 bits): the move of the game on which this position would have occurred
// depth (8 bits)
// node type (8 bits): from the three constants above

Here is a simple implementation:

var keys [1000]uint64
var values [1000]uint64

func Put(b *dragontoothmg.Board, m dragontoothmg.Move, eval int16, depth uint8, ntype uint8) {
    var value uint64 = uint64(eval) | (uint64(m) << 16) | (uint64(b.Fullmoveno) << 32) |
        (uint64(depth) << 48) | (uint64(ntype) << 56)
    hash := b.Hash()
    key := hash ^ value
    index := hash % uint64(len(keys))
    keys[index] = key
    values[index] = value
}

func Get(b *dragontoothmg.Board) (found bool, move dragontoothmg.Move,
    eval int16, depth uint8, ntype uint8) {
    hash := b.Hash()
    index := hash % uint64(len(keys))
    key := keys[index]
    value := values[index]
    found = (hash == (key ^ value))
    if !found {
        return false, 0, 0, 0, 0
    }
    eval = int16(value & 0xFFFF)
    move = dragontoothmg.Move((value >> 16) & 0xFFFF)
    depth = uint8((value >> 48) & 0xFF)
    ntype = uint8((value >> 56) & 0xFF)
    return
}

However, when I try to Get() the data, it comes back corrupted. I suspect this might be related to the fact that eval is a signed int, and the cast converts it to a signed uint64. What have I done wrong, and how can I fix it?

This is failing test result:

--- FAIL: TestSimpleTt (0.10s)
    transtable_test.go:37: Simple ttable test failed. 
        Put data: (board: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 0) e2e4 -30 6 2 
         Fetched data: true h8h8 -30 255 255
FAIL

h8h8 is the maximum value of the field, for what it's worth.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    dongzaobei0942 dongzaobei0942 2017-05-14 02:39

    Thanks to everyone who responded. This was the solution to my issue:

    uint64(eval) for negative values was moving the sign bit to the most significant bit of the 64-bit int, which then interfered with the data that was supposed to be stored at that bit. I solved it by first converting to uint16:

    uint64(uint16(eval))

    点赞 评论 复制链接分享
  • dongling3243 dongling3243 2017-05-13 23:52

    I can't reproduce your resultat in simplified code https://play.golang.org/p/shPN-1waZa:

    func Pack(m, eval int16, depth, ntype uint8) (value uint64) {
        value = (uint64(eval) |
            (uint64(m) << 16) |
            // (uint64(b.Fullmoveno) << 32) |  <-- My suspicion is here !
            (uint64(depth) << 48) |
            (uint64(ntype) << 56))
        return
    }
    func Unpack(value uint64) (move int16, eval int16, depth uint8, ntype uint8) {
        eval = int16(value & 0xFFFF)
        move = int16((value >> 16) & 0xFFFF)
        depth = uint8((value >> 48) & 0xFF)
        ntype = uint8((value >> 56) & 0xFF)
        return
    }
    
    func main() {
        m, e, d, n := int16(8), int16(8), uint8(8), uint8(8)
        packedValue := Pack(m, e, d, n)
        fmt.Printf("%v
    ", packedValue)
        move, eval, depth, ntype := Unpack(packedValue)
        fmt.Printf("%v %v %v %v", move, eval, depth, ntype)
    }
    

    But I have suspicions:

    a) dragonthooth.Move - is it really int16? I suppose you have set of consts with values for this type

    b) You're packing 5 values and extract 4. Maybe it's not error, but check type of b.Fullmoveno is it int16?

    c) I can not judge about correctness of your other code. I just hope that you did not make errors in hash, index, keys, values.

    I can't quite understand your remaining code.

    1. I suppose you mean value structure and not key structure (because in your code it's value packed)

    2. Why did you define 2 keys and values in separate arrays? Why not []{uint64,uint64}? Or even map[uint64]uint64?

    点赞 评论 复制链接分享

相关推荐