gpt4 book ai didi

c++ - O(log n) 索引更新和搜索

转载 作者:塔克拉玛干 更新时间:2023-11-03 07:31:50 26 4
gpt4 key购买 nike

我需要跟踪大型文本文件中的索引。我一直在保留索引和随附数据的 std::map 作为快速破解。如果用户位于文本中的字符 230,400,我可以显示文本的任何元数据。

现在我的 map 越来越大,我遇到了一些速度问题(正如预期的那样)。

例如,如果在开头修改了文本,我需要将 map 中该位置之后的索引递增一个,这是一个 O(N) 操作。

将其更改为 O(log N) 复杂度的好方法是什么?我一直在看AVL Arrays , 这很接近。

我希望 O(log n) 时间用于更新和搜索。例如,如果用户在文本数组中的字符 500,000 上,我想非常快速地找到该字符是否有任何元数据。

(忘了补充:用户可以随时添加元数据)

最佳答案

简单。制作偏移量的二叉树。

任何偏移量的值都是通过从叶节点遍历树到根节点来计算的,只要节点是右子节点就添加偏移量。

然后,如果您在文件的早期添加文本,您只需要更新节点的偏移量,这些节点是发生变化的偏移量的父节点。也就是说,您在第一个偏移量之前添加了文本,您添加了添加到根节点的字符数。现在您的偏移量的一半已得到纠正。现在遍历到左 child 并再次添加偏移量。现在 3/4 的偏移量已经更新。继续遍历左 child 添加偏移量,直到所有偏移量都更新。

@OP:

假设您有一个包含 8 个字符的文本缓冲区,奇数字节有 4 个偏移量:

the tree:              5
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 5 7

现在假设您在偏移量 4 处插入了 2 个字节。缓冲区是:

01234567

现在是

0123xx4567

因此,您只修改支配数组中已更改部分的节点。在这种情况下需要修改根节点。

the tree:              7
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 7 9

求和规则是从叶子走到根我自己求和,如果我是 parent 的右 child ,我 parent 的值(value)。

为了查找我当前位置是否有索引,我从根开始并询问此偏移量是否大于我的位置。如果是,我向左遍历并且不添加任何内容。如果不是,我向右遍历并将该值添加到我的索引中。如果在遍历结束时我的值等于我的索引那么是的有一个注释。您可以使用最小和最大索引进行类似的遍历,以找到主导该范围内所有索引的节点,找到我正在显示的文本的所有索引。

哦..这只是一个玩具示例。实际上,您需要定期重新平衡树,否则如果您继续在文件的一部分中添加新索引,您将得到一棵失去平衡的树,最坏情况下的性能将不再是 O( log2 n) 但会是 O(n)。为了保持树的平衡,您需要实现像“红/黑树”这样的平衡二叉树。这将保证 O(log2 n) 性能,其中 N 是元数据的数量。

关于c++ - O(log n) 索引更新和搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11161858/

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