go - 按字节比较 varint 编码的 int64

Question

我正在使用 levigo ，Go 的 leveldb 绑定(bind)。我的 key 是 int64 的，需要保持排序。默认情况下，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

playground

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

编辑:

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

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

Answer 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
        }
}

Playground

(*) 原因是(也是)位fiddling performed .