英文:
Removing a slice of keys within a Map with time complexity better than O(n^2) in Go
问题
在Go语言中，从一个Map数组中删除多个键的基本方法是使用嵌套循环。即使用一个父循环来迭代Map数组，再使用一个内部循环来迭代要删除的键的切片。有没有一种方法可以不使用嵌套循环来实现呢？我正在尝试找到一种时间复杂度比O(n^2)更好的方法。
英文:
Basic approach to delete multiple keys from an array of Maps in Go, would be by using nested loops, that is with a parent loop for iterating over array of Maps and an inner loop of slice of Keys to be deleted. Is there a way to do this without using nested loops. Just trying to figure out a way to get better time complexity that O(n^2).
答案1
得分: 1
n是指键的数量，时间复杂度为O(n^2)是因为在给定的代码中，对于每个键，都需要遍历所有的映射进行删除操作，导致时间复杂度呈二次方增长。
在给定的代码中，键的数量的增长函数是线性的，即O(len(keys))。映射的数量在实践中可能相对较小，甚至是常数，因此可以认为映射的数量是常数级别的。因此，键的数量乘以映射的数量的增长函数为O(len(keys))。
每次迭代所花费的时间是否显著取决于具体情况。
在这种情况下，键表示要从映射中删除的特定键。映射表示包含键值对的数据结构。
在实际情况中，预计会遇到最坏情况的时间复杂度。
你运行过哪些Go基准测试？结果如何？
根据给定的代码，时间复杂度似乎是O(len(keys) × len(maps))，或者简写为O(k × m)。实际上，映射的数量（maps）相对于键的数量（keys）可能很小，甚至是常数级别的。因此，时间复杂度可能接近于O(len(keys))或O(n)。
英文:
> Removing a slice of keys within a Map with time complexity better than
> O(n^2) in Go
What is n? Why is time complexity O(n^2)?
Consider real code and real cases:
package main
func mapsDeleteUniqueKeys(maps []map[string]int, keys []string) {
// iterations = len(keys) × len(maps)
for _, k := range keys {
for _, m := range maps {
delete(m, k)
}
}
}
func mapsDeleteDuplicateKeys(maps []map[string]int, keys []string) {
// iterations = len(keys) + (len(unique) × len(maps))
unique := make(map[string]struct{}, len(keys))
for _, k := range keys {
unique[k] = struct{}{}
}
for k := range unique {
for _, m := range maps {
delete(m, k)
}
}
}
func main() {}
What is the growth function for the number of keys? What is the growth function for the number of maps? What is the growth function for the number of keys times the number of maps?
Is the time spent on each iteration significant?
In your case: What do the keys represent? In your case: What do the maps represent?
What worst-case time complexity do you expect to encounter in the real world?
What Go benchmarks have you run? What were the results?
Time complexity appears to be O(len(keys) × len(maps)), or O(k × m),.
In practice len(maps), the number of maps, is likely small relative to len(keys), the number of keys. The number of maps may also be constant. Therefore, the time complexity is likely near O(len(keys)) or O(n).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论