douzi4724 2013-05-08 14:01
浏览 93
已采纳

按字节比较varint编码的int64

I'm using levigo, the leveldb bindings for Go. My keys are int64's and need to be kept sorted. By default, leveldb uses a bytewise comparator so I'm trying to use varint encoding.

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

My keys are not being sorted correctly. I wrote the following as a test.

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
}

output: bytewise: 127 > 128

playground

I'm not sure where the problem is. Am I doing the encoding wrong? Is varint not the right encoding to use?

EDIT:

BigEndian fixed width encoding is bytewise comparable

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

1条回答 默认 最新

  • dsiuy42084 2013-05-08 14:23
    关注

    The varint encoding is not bytewise comparable* wrt to the order of the values it caries. One option how to write the ordering/collating function (cmp bellow) is for example:

    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

    (*) The reason is (also) the bit fiddling performed.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 广告联盟的兜底广告是什么意思
  • ¥15 如何证明高斯噪声的包络公式
  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 乳腺癌数据集 相关矩阵 特征选择
  • ¥15 我的游戏账号被盗取,请问我该怎么做
  • ¥15 通关usb3.0.push文件,导致usb频繁断连
  • ¥15 有没有能解决微信公众号,只能实时拍照,没有选择相册上传功能,我不懂任何技术,,有没有给我发个软件就能搞定的方法
  • ¥15 Pythontxt文本可视化
  • ¥15 如何基于Ryu环境下使用scapy包进行数据包构造
  • ¥15 springboot国际化