Golang实现map[string][]string到反向map[string][]string的算法转换

Golang实现map[string][]string到反向map[string][]string的算法转换 你有一个数据集，表示狗和猫之间的关系。该数据集的结构是一个映射（map），其中每只狗都与一个猫名字列表相关联。给定狗的猫名字是唯一的。总体而言，所有猫名字和狗名字都是唯一的，尽管两只狗可能属于同一只猫，并且两只猫可能属于同一只狗。

问题：你的目标是生成一个新的数据集，反转这种关系，其中每只猫都与一个唯一的狗名字列表相关联。

你将如何高效地解决这个问题？对于大数据你会怎么做？Go 是否为这种情况提供了任何支持/库数据结构？解决这个问题的惯用方法是什么？

附注：我已经尝试过“遍历输入映射，对于每个值，将其添加到新映射中对应的键下，如果尚未存在”。我正在寻找比这更高效的方法。类似地，“使用辅助映射来检查狗是否已经属于这只猫”。


更多关于Golang实现map[string][]string到反向map[string][]string的算法转换的实战教程也可以访问 https://www.itying.com/category-94-b0.html

8 回复

这是另一个版本，但这次使用了虚拟数据进行初始化，而不是通过 append 构建：https://goplay.tools/snippet/r5lLSEkJTRW

底层数据结构是 map[string][]string。

更多关于Golang实现map[string][]string到反向map[string][]string的算法转换的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


为了好玩，这里有一个可运行环境中的算法：https://goplay.tools/snippet/6UoNk3saTo8

我很好奇大家能想出什么更高效的方法。也许是利用内存区域（memory arena）之类的东西？

duckduck:

甚至可能与内存有关

如果存在多个重复项，可以有一个辅助数据结构，dogCats 是一个 map[string]map[string]interface{}。构建完这个辅助数据结构后，再从中构建你的结果。

然而，这在很大程度上取决于重复项的数量，你可能会分配比实际需要更多的内存，等等。

N*M 布尔矩阵在内存中

猫/狗的例子很可能非常稀疏。如果你的实际问题也非常稀疏，可以考虑使用像 CSR 这样的稀疏矩阵实现。稀疏矩阵实现针对（相对）快速的矩阵/矩阵运算进行了优化，因此随机元素访问会带来运行时性能损失。

你也可以通过使用 int64 来存储 64 个矩阵元素来减少空间占用，但这可能与稀疏实现相悖，并且肯定会使其复杂化。

嗨 @duckduck

你的想法是跳出固有思维模式的绝佳例子，恭喜你，先生。话虽如此，我认为我无法使用它：如果你有N百万只狗和M百万只猫，甚至更多，你需要考虑在内存中存储一个N*M的布尔矩阵的成本，在这种情况下，这似乎太多了。

不直接相关的一点是，如果狗实体只是一个简单的小字符串，比如“dog1”，那么存储一个布尔值和字符串本身之间的差异并不足以证明值得进行记忆化。一个布尔值是一个字节，而一个字符串则类似于3个整数（其中一个是不可变符文切片本身的指针）。

请继续提出创新的想法，我相信这个问题可以比使用一对映射更高效地解决。

dogscats := make(map[string][]string)  // map each dog to a catlist.
for cat, doglist := range catsdogs {
  for _, dog := range doglist {
     dogscats[dog] = append(dogscats[dog], cat)
  }
}

如果每只狗对应许多猫，你可能会重新分配 catlist。如果这造成了性能问题，可以遍历 catsdogs 一次来统计每只狗对应的猫的数量，以便能够以正确的初始大小分配 catlist。另一个性能问题可能来自映射的增长。你可以统计唯一的狗的数量来预分配 dogscats 的大小，但这样做你将需要一个狗的集合（作为一个映射），这个集合需要像 dogscats 一样增长，因此这可能并不值得。

最有效的解决方案可能是将狗与猫的关系编码在一个 [][]bool 矩阵中。无需修改矩阵，因为只需交换列和行进行迭代（实际上是转置矩阵）即可。

运行示例：

goplay.tools

Better Go Playground

Better Go Playground with syntax highlight support

 dogs := [3]string{"dog1", "dog2", "dog3"}
cats := [4]string{"cat1", "cat2", "cat3", "cat4"}
                                                                           
dogm := [3][4]bool{
	[4]bool{true, true, true, true},    // dog1 has cat1, cat2, cat3, cat4
	[4]bool{true, false, true, false},  // dog2 has cat1, cat3
	[4]bool{true, false, false, false}, // dog3 has cat1
}
                                                                           
// print source data
printmatrix(dogs[:], cats[:], dogm)

目前我仍在尝试编写一个（或许是泛型的）printmatrix 函数，以替代那两个独立的函数，从而避免将矩阵（具有硬编码的维度）复制到切片中。

在Go中实现map[string][]string到反向映射的高效转换，可以通过以下方式实现：

func invertMap(original map[string][]string) map[string][]string {
    inverted := make(map[string][]string)
    
    for dog, cats := range original {
        for _, cat := range cats {
            // 检查这只猫是否已经在反向映射中
            if dogs, exists := inverted[cat]; exists {
                // 检查这只狗是否已经属于这只猫
                found := false
                for _, d := range dogs {
                    if d == dog {
                        found = true
                        break
                    }
                }
                if !found {
                    inverted[cat] = append(dogs, dog)
                }
            } else {
                inverted[cat] = []string{dog}
            }
        }
    }
    
    return inverted
}

对于大数据集，可以使用更优化的方法，通过辅助映射来避免线性搜索：

func invertMapOptimized(original map[string][]string) map[string][]string {
    inverted := make(map[string][]string)
    // 使用map[string]map[string]bool作为中间结构来快速去重
    temp := make(map[string]map[string]bool)
    
    for dog, cats := range original {
        for _, cat := range cats {
            if temp[cat] == nil {
                temp[cat] = make(map[string]bool)
            }
            temp[cat][dog] = true
        }
    }
    
    // 将临时结构转换为最终结果
    for cat, dogsMap := range temp {
        dogs := make([]string, 0, len(dogsMap))
        for dog := range dogsMap {
            dogs = append(dogs, dog)
        }
        inverted[cat] = dogs
    }
    
    return inverted
}

Go标准库没有专门针对这种转换的直接支持，但可以使用map[string]map[string]bool作为中间数据结构来提高性能。对于非常大的数据集，可以考虑并行处理：

func invertMapParallel(original map[string][]string) map[string][]string {
    type pair struct {
        cat string
        dog string
    }
    
    ch := make(chan pair, len(original)*10)
    done := make(chan bool)
    inverted := make(map[string][]string)
    
    // 生产者goroutine
    go func() {
        for dog, cats := range original {
            for _, cat := range cats {
                ch <- pair{cat, dog}
            }
        }
        close(ch)
    }()
    
    // 消费者goroutine
    go func() {
        temp := make(map[string]map[string]bool)
        for p := range ch {
            if temp[p.cat] == nil {
                temp[p.cat] = make(map[string]bool)
            }
            temp[p.cat][p.dog] = true
        }
        
        for cat, dogsMap := range temp {
            dogs := make([]string, 0, len(dogsMap))
            for dog := range dogsMap {
                dogs = append(dogs, dog)
            }
            inverted[cat] = dogs
        }
        done <- true
    }()
    
    <-done
    return inverted
}

示例使用：

func main() {
    original := map[string][]string{
        "Rex":   {"Whiskers", "Fluffy"},
        "Buddy": {"Fluffy", "Mittens"},
        "Max":   {"Whiskers"},
    }
    
    inverted := invertMapOptimized(original)
    
    for cat, dogs := range inverted {
        fmt.Printf("%s: %v\n", cat, dogs)
    }
    // 输出:
    // Whiskers: [Rex Max]
    // Fluffy: [Rex Buddy]
    // Mittens: [Buddy]
}

这种转换的惯用方法是使用辅助映射来确保唯一性，时间复杂度为O(n)，其中n是所有狗-猫关系的总数。对于极大数据集，并行处理可以进一步提高性能。

回到顶部