Golang中的Map访问瓶颈

Question

我正在使用Golang实现朴素贝叶斯分类器，用于处理一个具有超过30000个可能标签的数据集。我已经构建了模型并处于分类阶段。我正在努力对1000条记录进行分类，但这需要长达5分钟的时间。我已经使用pprof功能对代码进行了分析;以下是前10个结果：

Total: 28896 samples
   16408  56.8%  56.8%    24129  83.5% runtime.mapaccess1_faststr
    4977  17.2%  74.0%     4977  17.2% runtime.aeshashbody
    2552   8.8%  82.8%     2552   8.8% runtime.memeqbody
    1468   5.1%  87.9%    28112  97.3% main.(*Classifier).calcProbs
     861   3.0%  90.9%      861   3.0% math.Log
     435   1.5%  92.4%      435   1.5% runtime.markspan
     267   0.9%  93.3%      302   1.0% MHeap_AllocLocked
     187   0.6%  94.0%      187   0.6% runtime.aeshashstr
     183   0.6%  94.6%     1137   3.9% runtime.mallocgc
     127   0.4%  95.0%      988   3.4% math.log10

令人惊讶的是，地图访问似乎成为了瓶颈。有没有人有过这样的经验？还有哪些键值数据结构可以用来避免这种瓶颈？以下代码片段中完成了所有地图访问：

func (nb *Classifier) calcProbs(data string) *BoundedPriorityQueue{
    probs := &BoundedPriorityQueue{} 
    heap.Init(probs)

    terms := strings.Split(data, " ")
    for class, prob := range nb.classProb{
        condProb := prob
        clsProbs := nb.model[class]
        for _, term := range terms{
            termProb := clsProbs[term]
            if termProb != 0{
                condProb += math.Log10(termProb)
            }else{
                condProb += -6 //math.Log10(0.000001)
            }
        }
       entry := &Item{
            value: class,
            priority: condProb,
        }
        heap.Push(probs,entry)
    }
    return probs
}

这些图是nb.classProb，其中包含map[string]float64类型，而nb.model是一个嵌套的map，其类型为

map[string]map[string]float64

- cobie

---

如果你知道一个方法很天真，为什么要实现它呢？ - Fallenreaper

看到实际代码会很有用，至少可以知道你正在使用什么类型的键/值。Map 应该相当快。 - siritinga

我已经在字符串和整数上使用本地映射获得了疯狂快速的基准测试，达到了1000万个项目。正如siritinga所说，代码是好的。是哪种类型的映射？ - Eve Freeman

是的，我也是这么认为。所以我猜测可能出了什么问题，或者密钥太大了，计算哈希需要很长时间。 - siritinga

你期望哪一部分会成为瓶颈呢？如果你的 for _, term := range terms 循环是主要代码（内循环），那么显然 map 查找将是最耗时的。 - Volker

Answer 1

除了@tomwilde所说的内容之外，另一个可能加快算法速度的方法是字符串池。也就是说，如果您预先知道键的域，可以完全避免使用映射。我编写了一个小程序包，可以为您进行字符串池化。

- BurntSushi5

---

你需要添加一个许可证，否则 pkg.go.dev 目前无法显示它。 - Nv7

Answer 2

是的，地图访问将成为此代码中的瓶颈：它是两个嵌套循环中最重要的操作。

从您提供的代码中无法确定，但我预计您拥有有限数量的类。您可以对它们进行编号，并像这样存储逐项类概率：

map[string][NumClasses]float64

(ie: 对于每个术语，存储一组按类别划分的概率[或者已经预先计算好概率的对数]，NumClasses是您拥有的不同类别的数量)。

然后，首先迭代术语，再迭代内部的类别。昂贵的映射查找将在外层循环中完成，内部循环将迭代一个数组。

这将把映射查找的次数减少NumClasses倍。如果您的数据非常稀疏，则可能需要更多的内存。

下一个优化是使用多个goroutine进行计算，假设您有多个CPU核可用。

- Paul Hankin