散列反射类型 [英] Hashing reflect.Type

问题描述

我试图找到一种在两个[]reflect.Type之间进行比较的快速方法.现在，我有以下内容:

I'm trying to find a quick way of performing comparisons between two []reflect.Type. Right now I have the following:

func Equal(left, right []reflect.Type) bool {
    if len(left) != len(right) {
        return false
    }
    for i := 0; i < len(left); i++ {
        if left[i] != right[i] {
            return false
        }
    }
    return true
}

大多数切片不变.因此，如果我能找到一种对它们进行哈希处理的方法，那么我将获得极大的性能提升.

Most of the slices don't change. So if I can find a way to hash them, I'd get a huge perf boost.

背景

我正试图(出于娱乐目的)使用reflect包在Go中实现某种形式的函数重载.我要做的第一件事是将每个专用/重载函数转换为签名类型.

I'm trying to (for fun) implement a form of function overloading in Go using the reflect package. The first thing I did is to convert each specialised/overloaded function into a signature type.

type Signature struct {
    Variadic bool
    In, Out  []reflect.Type
}

这个想法是，当重载函数被调用时，我会将参数转换为reflect.Type的一部分，然后找到Signature类型匹配的Signature.

The idea is that, when the overloaded function gets called, I'll convert the arguments into a slice of reflect.Type and then find a Signature where the In types match.

这是可行的，但是对于每个比较而言，它都是一个线性扫描，非常慢.如果我可以对[]reflect.Type的切片进行哈希处理，则可以将其粘贴在地图中并进行恒定时间的查找.

This works, but for each comparison, it's a linear scan which is pretty slow. If I could hash the slice of []reflect.Type I could stick that in a map and get constant time lookups.

推荐答案

我最终滥用了内置的map为每个reflect.Type分配唯一的ID.然后，我使用djb2对其进行哈希处理.

I ended up abusing the built-in map to assign unique ids to each reflect.Type. Then I hash those using djb2.

type TypeCode struct {
    seq   int64
    codes map[reflect.Type]int64
}

func (td *TypeCode) TypeID(t reflect.Type) int64 {
    if code, ok := td.codes[t]; ok {
        return code
    }
    td.seq++
    td.codes[t] = td.seq
    return td.seq
}

func (td *TypeCode) SliceTypeID(tt []reflect.Type) int64 {
    id := int64(5381)
    for _, t := range tt {
        id = ((id << 5) + id) + td.TypeID(t)
    }
    return id
}

编辑:我改用了基于字符串的方法，该方法效率较低，但消除了可能发生的冲突.

edit: I switched to a string based approach which is less efficient, but removes any potential for collisions.

type TypeCode struct {
    seq   int64
    codes map[reflect.Type]string
}

func (td *TypeCode) TypeID(t reflect.Type) string {
    if code, ok := td.codes[t]; ok {
        return code
    }
    td.seq++
    id := strconv.FormatInt(td.seq, 10)
    td.codes[t] = id
    return id
}

func (td *TypeCode) SliceTypeID(tt []reflect.Type) string {
    ids := make([]string, len(tt))
    for i := 0; i < len(tt); i++ {
        ids[i] = td.TypeID(tt[i])
    }
    return strings.Join(ids, ".")
}

这篇关于散列反射类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！