1

我正在使用levigo,即 Go 的 leveldb 绑定。我的钥匙是int64's 并且需要保持排序。默认情况下,leveldb 使用字节比较器,所以我尝试使用 varint 编码。

func i2b(x int64) []byte {
    b := make([]byte, binary.MaxVarintLen64)
    n := binary.PutVarint(b, x)
    return key[:n]
}

我的钥匙没有被正确排序。我写了以下内容作为测试。

var prev int64 = 0
for i := int64(1); i < 1e5; i++ {
    if bytes.Compare(i2b(i), i2b(prev)) <= 0 {
        log.Fatalf("bytewise: %d > %d", b2i(prev), i)
    }
    prev = i
}

输出: bytewise: 127 > 128

操场

我不确定问题出在哪里。我做错编码了吗?varint 不是正确的编码吗?

编辑:

BigEndian 固定宽度编码是按字节可比的

func i2b(x int64) []byte {
  b := make([]byte, 8)
  binary.BigEndian.PutUint64(b, uint64(x))
  return b
}
4

1 回答 1

1

varint 编码与它所携带的值的顺序不可按字节比较* wrt。例如,如何编写排序/整理功能(cmp波纹管)的一种选择是:

package main

import (
        "encoding/binary"
        "log"
)

func i2b(x int64) []byte {
        var b [binary.MaxVarintLen64]byte
        return b[:binary.PutVarint(b[:], x)]
}

func cmp(a, b []byte) int64 {
        x, n := binary.Varint(a)
        if n < 0 {
                log.Fatal(n)
        }

        y, n := binary.Varint(b)
        if n < 0 {
                log.Fatal(n)
        }

        return x - y
}

func main() {
        var prev int64 = 0
        for i := int64(1); i < 1e5; i++ {
                if cmp(i2b(i), i2b(prev)) <= 0 {
                        log.Fatal("fail")
                }
                prev = i
        }
}

操场

(*) 原因是(也)进行了位摆弄

于 2013-05-08T14:23:45.097 回答