go - 有没有办法在 Go 中快速排序类型？

Question

我有一个必须订购 Go 类型的包，快速。

目前我使用reflect.Type s，用Name()得到他们的名字，并将名称排序为字符串:

if type1.Name() < type2.Name() { ...

但是，它使用了字符串比较。它有效，但我正在寻找更快速的解决方案。

这种比较究竟如何工作，对我来说并不重要 - 只有我需要的东西，

1. 比较的结果在进程的生命周期内应该是相同的。
2. 对于不同的类型应该是不相等的，但对于相同的类型应该是相等的。

比较 reflect.Type变量直接用 <不起作用，因为未为 reflect.Type 定义此操作Go 中的 s。

可以将类型名称的哈希值生成为 64 位或 128 位整数，然后比较这些整数。这是有可能的，但我正在寻找更快的解决方案。

另一种可能性是比较 reflect.Type变量的不安全指针(转换为 int64 )，但据我所知，在 Go 中不能保证 unsafe 指针地址在进程的生命周期中不会改变。因此，我将失去我的 (1) 要求。

Answer 1

使用 Type.Name() 是错误的

使用 Type.Name() 进行比较是一个非常糟糕的主意，因为有许多匿名类型，其中 Type.Name() 返回空字符串，例如 []int, *int 等。Type.Name() 返回的名称也不包括包名称，例如 的名称code>time.Time 和 foo.Time 将是 "Time"，因此被认为是相等的。无需多说。查看Identify non builtin-types using reflect了解更多详情。

使用内部注册表

一种简单快捷的方法是为所有需要比较的类型分配一个整数(例如 int 值)，然后您不需要任何 string 比较也不是散列，只是比较分配的 int 值。

剩下的唯一问题是如何分配和记住这些int 值。分配的值可能只是连续的值，从 1 开始，然后是 2、3 等。这种分配和查找可能是自动的(我们看不到)。

本质上我们想要一个像这样的函数:

// Compare compares 2 types, returns a negative number
// if t1 < t2, a positive number if t1 > t2, and 0 otherwise.
func Compare(t1, t2 reflect.Type) int {
}

而且实现非常简单/紧凑:

var (
    registry = map[reflect.Type]int{}
    max      int
)

func value(t reflect.Type) int {
    v := registry[t]
    if v == 0 {
        max++
        v, registry[t] = max, max
    }
    return v
}

// Compare compares 2 types, returns a negative number
// if t1 < t2, a positive number if t1 > t2, and 0 otherwise.
func Compare(t1, t2 reflect.Type) int {
    v1, v2 := value(t1), value(t2)
    return v1 - v2
}

测试它:

tstring := reflect.TypeOf("")
tint := reflect.TypeOf(int(1))
ttime := reflect.TypeOf(time.Time{})

fmt.Println(Compare(tstring, tstring)) // 0
fmt.Println(Compare(tint, ttime))      // -1, tint gets registered first
fmt.Println(Compare(ttime, tint))      // 1
fmt.Println(Compare(tint, tint))       // 0
fmt.Println(Compare(tstring, ttime))   // -2
fmt.Println(Compare(ttime, tstring))   // 2

输出(在 Go Playground 上尝试):

0
-1
1
0
-2
2

确保并发使用安全

不过有一个弱点:该实现对于并发使用(由多个 goroutines)来说是不安全的。如果我们需要并发使用的安全性，则必须同步访问 registry 映射(以及 max 变量):

var mu sync.RWMutex

func value(t reflect.Type) int {
    mu.RLock()
    v := registry[t]
    mu.RUnlock()
    if v == 0 {
        mu.Lock()
        max++
        v, registry[t] = max, max
        mu.Unlock()
    }
    return v
}

其余不变。输出是一样的。在 Go Playground 上试试这个.

引擎盖下(仔细观察)

现在这个 Compare() 意味着在后台使用锁。同样，为了获得类型的指定整数值，我们必须索引一个映射。此映射中的键类型是 reflect.Type，它是一种接口(interface)类型。 reflect.Type 的当前实现是 *reflect.rtype，它是一个指针，所以它仍然足够快，因为只对指针进行哈希处理，然后在桶中查找(内置映射是 HashMap 实现)。

最快的解决方案(摆脱锁和 map 索引)

现在这个 Compare() 意味着在引擎盖下使用锁(和索引 map )，所以如果您真的寻求最快的解决方案，这可能仍然是一个 Not Acceptable “负担”。如果您获取为该类型分配的内部 int 值并使用它，甚至可以直接与另一个类型的值进行比较，那么在需要比较时，您可以轻松地摆脱一直使用它们。

为此，您需要做的就是“发布”(导出)value() 函数:

func Value(t reflect.Type) int {
    // ...
}

Compare() 甚至可能被删除。所以需要这种类型比较的库可以查询分配给一个类型的整数值，并且它们可以“缓存”这个值以避免再次调用它(因为它在进程的生命周期中不会改变)，并且它可以与此 Value() 函数获得的其他值进行比较。

例如:

vstring := Value(reflect.TypeOf(""))
vint := Value(reflect.TypeOf(int(1)))
vtime := Value(reflect.TypeOf(time.Time{}))

fmt.Println(vstring - vstring) // 0
fmt.Println(vint - vtime)      // -1, tint gets registered first
fmt.Println(vtime - vint)      // 1
fmt.Println(vint - vint)       // 0
fmt.Println(vstring - vtime)   // -2
fmt.Println(vtime - vstring)   // 2

在 Go Playground 上试试这个.