gpt4 book ai didi

algorithm - 关于向量数据结构设计的问题?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:36:04 25 4
gpt4 key购买 nike

作者在阅读一些关于稀疏向量数据结构设计的资料时,作如下陈述。

A hash table could be used to implement a simple index-to-value mapping. Accessing an index value is slower than with direct array access, but not by much.

为什么在使用哈希表时评估索引值比较慢?

此外,作者指出

The problem with a hash-backed implementation is that it becomes relatively slow to iterate through all values in order by index. An ordered mapping based on a tree structure or similar can address this problem, since it maintains keys in order. The price of this feature is longer access time.

为什么基于散列的实现在遍历所有值时表现不佳?这是因为评估指数的操作速度较慢吗?

树结构如何帮助解决此类问题?

最佳答案

由于计算开销,访问哈希表索引会慢一点。
在哈希表中,如果您请求项目 452345435,并不意味着它在单元格 452345435 中......哈希表执行一系列计算以找到正确的单元格。这取决于实现。
<强> Hash table Performance analysis

哈希表不存储排序后的数据。所以如果你想以正确的顺序获取项目,则需要调用排序算法。

要解决这个问题,您可以使用树或任何其他排序数据结构。
但这会增加插入复杂度,从 O(1)(哈希表)到 O(logn)(插入树,排序数据库)。
那是因为每个索引都会被添加到两个数据结构中,复杂度将是 O(1) + O(logn) = O(logn)

检索数据仍然只需要 O(1),因为从哈希表中请求它就足够了。

关于algorithm - 关于向量数据结构设计的问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6310697/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com