algorithm - Golang maps/hashmaps，优化迭代速度

Question

在将生产 NodeJS 应用程序迁移到 Golang 时，我注意到 GO 的原生 Map 的迭代实际上比 Node 慢。

我想出了一个替代解决方案，通过公开一个可以迭代的数组并将 key=>index 对存储在单独的映射中，以迭代速度牺牲删除/插入速度。

虽然此解决方案有效并且性能显着提高，但我想知道是否有更好的解决方案可供我研究。

我的设置是从散列图中删除了非常罕见的东西，只有添加和替换是常见的，这个实现“有效”，尽管感觉更像是一种解决方法，而不是实际的解决方案。

map 总是由一个整数索引，包含任意数据。

FastMap:    500000 Iterations -  0.153000ms
Native Map: 500000 Iterations -  4.988000ms

/*
  Unordered hash map optimized for iteration speed.
  Stores values in an array and holds key=>index mappings inside a separate hashmap
*/

type FastMapEntry[K comparable, T any] struct {
    Key   K
    Value T
}

type FastMap[K comparable, T any] struct {
    m       map[K]int            // Stores key => array index mappings
    entries []FastMapEntry[K, T] // Array holding entries and their keys
    len     int                  // Total map size
}

func MakeFastMap[K comparable, T any]() *FastMap[K, T] {
    return &FastMap[K, T]{
        m:       make(map[K]int),
        entries: make([]FastMapEntry[K, T], 0),
    }
}

func (m *FastMap[K, T]) Set(key K, value T) {
    index, exists := m.m[key]
    if exists {
        // Replace if key already exists
        m.entries[index] = FastMapEntry[K, T]{
            Key:   key,
            Value: value,
        }
    } else {
        // Store the key=>index pair in the map and add value to entries. Increase total len by one
        m.m[key] = m.len
        m.entries = append(m.entries, FastMapEntry[K, T]{
            Key:   key,
            Value: value,
        })
        m.len++
    }
}

func (m *FastMap[K, T]) Has(key K) bool {
    _, exists := m.m[key]

    return exists
}

func (m *FastMap[K, T]) Get(key K) (value T, found bool) {
    index, exists := m.m[key]
    if exists {
        found = true
        value = m.entries[index].Value
    }

    return
}

func (m *FastMap[K, T]) Remove(key K) bool {
    index, exists := m.m[key]
    if exists {
        // Remove value from entries
        m.entries = append(m.entries[:index], m.entries[index+1:]...)
        // Remove key=>index mapping
        delete(m.m, key)
        m.len--

        for i := index; i < m.len; i++ {
            // Move all index mappings up, starting from current index
            m.m[m.entries[i].Key] = i
        }
    }

    return exists
}

func (m *FastMap[K, T]) Entries() []FastMapEntry[K, T] {
    return m.entries
}

func (m *FastMap[K, T]) Len() int {
    return m.len
}

运行的测试代码是:

// s.Variations is a native map holding ~500k records

start := time.Now()
iterations := 0
for _, variation := range s.Variations {
    if variation.Id > 0 {

    }
    iterations++
}
log.Printf("Native Map: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

// Copy data into FastMap
fm := helpers.MakeFastMap[state.VariationId, models.ItemVariation]()
for key, variation := range s.Variations {
    fm.Set(key, variation)
}

start = time.Now()
iterations = 0
for _, variation := range fm.Entries() {
    if variation.Value.Id > 0 {

    }
    iterations++
}
log.Printf("FastMap: %d Iterations -  %fms\n", iterations, float64(time.Since(start).Microseconds())/1000)

Answer 1

我觉得这种比较和标杆有点跑题了。 map 的 Go 实现与你的实现有很大的不同，主要是因为它需要覆盖更广泛的条目，编译时使用的结构实际上有点重(虽然不是那么多，它们基本上存储了一些关于你使用的类型的信息在你的 map 等等)，实现方法是不同的! map 的 Go 实现基本上是一个 hashmap(你的不是很明显，或者是，但实际的哈希实现委托(delegate)给你内部持有的 m map)。

让你得到这个结果的其他因素之一是，如果你看一下这个:

for _, variation := range fm.Entries() {
    if variation.Value.Id > 0 {

    }
    iterations++
}

基本上，你在一个 slice 上迭代，它比一个映射更容易和更快地迭代，你有一个数组 View ，它包含彼此相邻的相同类型的元素，这是有道理的，对吧?
为了更好地进行比较，您应该这样做:

for _, y := range fastMap.m {
        _ = fastMap.Entries()[y].Value + 1 // some simple calculation
}

如果您真的在寻找性能，那么编写良好的散列函数和固定大小的数组将是您的最佳选择。