当前位置: 首页 > 面试题库 >

戈朗地图的O表现如何?

鄢子平
2023-03-14
问题内容

Go语言规范的“地图类型”部分描述了地图类型的界面和常规用法,The
Go Blog上
的“ Go maps in
action”一文中
偶然提到了哈希表和“快速查找,添加和删除”。

的电流runtime/hashmap.go源代码描述了其作为散列表实施方案(其通常摊销O(1));
但是,在语言规范或其他材料中我看不到任何性能特征(例如Big O性能)的保证。

go语言是否为地图类型或仅 接口 保证了任何 性能 保证(例如,恒定时间插入/查找/删除?)?(与 接口实现
明显分开的Java语言相比。) __


问题答案:

语言参考并未明确保证地图的性能。映射的执行有一个隐含的期望,就像您期望哈希表执行一样。我看不到性能保证如何避免被模糊地指定或不准确。

Big-
O复杂度是描述地图运行时间的一种糟糕方法:实际上,实际时钟时间是相关的,而复杂度则无关紧要。从理论上讲,具有有限域键(例如ints)的映射在空间和时间上都是O(1),而具有无限域键(例如字符串)的映射需要散列,并且相等性测试的详细信息包括在成本中,这使得插入和查找的平均情况最好为O(N
log N)(因为键的平均大小必须至少为O(log N)才能构造具有N个条目的哈希表。除非您在规范将是不准确的,正确实现它的好处显然不值得。

要保证实际运行时间而不是复杂性,这也很困难:目标计算机种类繁多,还有缓存和垃圾回收的混杂问题。



 类似资料:
  • 问题内容: 我正在将算法从C移植到Go。我有些困惑。这是C函数: 在for循环中,将值s分配给元素cd数组x。这怎么可能?据我所知,长双精度数是float64(在Go上下文中)。因此,我不应该编译C代码,因为我正在向只包含uint64元素的数组分配一个long double。但是C代码可以正常工作。 那么有人可以解释为什么这行得通吗? 非常感谢你。 更新: 该函数的原始C代码可以在以下位置找到:h

  • 有什么方法可以重写panic功能来使用我们的记录器吗?

  • 用围棋的语言, 是一个字符串数组 我们还使用作为参数。 有什么区别? 功能定义: 我可以像下面那样调用这个函数吗?

  • 我想构建一个http反向代理,它检查http主体,然后向其上游服务器发送http请求。你怎么能在围棋中做到这一点? 初始尝试(随后)失败,因为ReverseProxy复制传入请求,修改并发送请求,但正文已被读取。 然后,我的下一个尝试是将整个正文读入字节。读卡器,并使用它检查正文内容,在发送到上游服务器之前查找开头部分。但是接下来我必须重新实现我想要避免的ReverseProxy。还有其他优雅的方

  • 我不能得到100%的代码覆盖率,因为我不能测试Golang的致命性。 我发现了一些问答,包括这一个,但我迷失了,因为帖子的答案是矛盾的。一方面,可以检查Golang中的代码覆盖率。另一方面,有些人主张忽略对等的测试,导致代码覆盖率低于。 尝试 根据这个定义,我的代码中有多个片段可能引发恐慌,而应该使用。