正如你在下面的pprof输出中看到的，我有这些嵌套的for循环，它们占用了我程序的大部分时间。源代码在 golang 中，但代码解释如下：
8.55mins 1.18hrs 20: for k := range mapSource {
4.41mins 1.20hrs 21: if positions, found := mapTarget[k]; found {
. . 22: // save all matches
1.05mins 1.05mins 23: for _, targetPos := range positions {
2.25mins 2.33mins 24: for _, sourcePos := range mapSource[k] {
1.28s 15.78s 25: matches = append(matches, match{int32(targetPos), int32(sourcePos)})
. . 26: }
. . 27: }
. . 28: }
. . 29: }
目前我使用的结构是 2 map[int32][]int32 、targetMap 和 sourceMap。
对于给定键，这些映射包含一个整数数组。现在我想找到两个映射中匹配的键，并将元素的组合保存在数组中。
所以例如：
sourceMap[1] = [3,4]
sourceMap[5] = [9,10]
targetMap[1] = [1,2,3]
targetMap[2] = [2,3]
targetMap[3] = [1,2]
唯一的共同键是1，结果将是[(3,1), (3,2), (3,3), (4,1), (4,2), (4,3)]
是否有任何可能的方法（更合适的数据结构或其他方法）可以提高我的程序速度？
就我而言，映射可以包含 1000 到 150000 个键，而内部的数组通常很小。
编辑：并发不是一个选项，因为它已经在多个线程中同时运行多次。
我可以进一步优化它以使其运行得更快吗？
是否有任何可能的方法（更合适的数据结构或 无论如何）可以提高我的程序速度？
可能。
XY问题是询问您的 尝试的解决方案而不是您的实际问题。这导致 人们浪费了大量的时间和精力 寻求帮助，以及提供帮助的人。
我们甚至没有关于您的问题的最基本信息，对原始输入数据的形式、内容和频率的描述，以及您想要的输出。哪些原始数据应该推动基准测试？
我创建了一些虚构的原始数据，产生了一些虚构的输出和结果：
BenchmarkPeterSO-4 30 44089894 ns/op 5776666 B/op 31 allocs/op
BenchmarkIvan-4 10 152300554 ns/op 26023924 B/op 6022 allocs/op
您的算法可能很慢。
我可能会这样做，以便我可以同时完成一些工作：
https://play.golang.org/p/JHAmPRh7jr
package main
import (
"fmt"
"sync"
)
var final [][]int32
var wg sync.WaitGroup
var receiver chan []int32
func main() {
final = [][]int32{}
mapTarget := make(map[int32][]int32)
mapSource := make(map[int32][]int32)
mapSource[1] = []int32{3, 4}
mapSource[5] = []int32{9, 10}
mapTarget[1] = []int32{1, 2, 3}
mapTarget[2] = []int32{2, 3}
mapTarget[3] = []int32{1, 2}
wg = sync.WaitGroup{}
receiver = make(chan []int32)
go func() {
for elem := range receiver {
final = append(final, elem)
wg.Done()
}
}()
for k := range mapSource {
if _, ok := mapTarget[k]; ok {
wg.Add(1)
go permutate(mapSource[k], mapTarget[k])
}
}
wg.Wait()
fmt.Println(final)
}
func permutate(a, b []int32) {
for i := 0; i < len(a); i++ {
for j := 0; j < len(b); j++ {
wg.Add(1)
receiver <- []int32{a[i], b[j]}
}
}
wg.Done()
}
您甚至可能想看看您是否从中获得任何好处：
for k := range mapSource {
wg.Add(1)
go func(k int32) {
if _, ok := mapTarget[k]; ok {
wg.Add(1)
go permutate(mapSource[k], mapTarget[k])
}
wg.Done()
}(k)
}
最好的优化可能涉及更改源和目标数据结构，这样您就不必迭代那么多，但是如果不详细了解您正在解决的潜在问题是什么，以及地图是如何生成的，就很难确定。
但是，有一个优化应该可以让您获得大约 2 倍的提升（只是一个有根据的猜测），具体取决于确切的数字。
var sources, targets []int32
for k, srcPositions := range mapSource {
if tgtPositions, found := mapTarget[k]; found {
sources = append(sources, srcPositions...)
targets = append(targets, tgtPositions...)
}
}
matches = make([]match, len(sources) * len(targets))
i := 0
for _, s := range(sources) {
for _, t := range(targets) {
matches[i] = match{s, t}
i++
}
}
一般的想法是尽量减少必须完成的复制量，并改善内存引用的局部性。我认为这是你可以用这个数据结构做的最好的事情。我的预感是，这不是解决潜在问题的最佳数据结构，而且还有更大的收获。
起初我在想：
-
在一个批次中计算共同键，并计算最终切片大小。
-
使用步骤 1 计算的容量制作切片。
-
逐个附加。
然后是下一个结构，但它不会将最终结果生成为数组，但所有追加工作都只是链接节点。
type node struct {
val int
parent *node
next *node
child *node
}
type tree struct {
root *node
level int
}
var sourceMap map[int]*tree