哪些链接的列表结构调整将使我快速随机查找？

Question

我目前正在使用双重链接列表（C ++ std::list）保存一堆记录，每个记录都有一个唯一的整数标识符。链接列表以排序顺序创建，以便在列表中，下一个项目始终具有比其前身更大的唯一标识符。

我面临的问题是，偶尔我需要能够快速将项目插入其相对排序的位置，并且使用普通的链接列表意味着此操作为$ O（n）$，这对我造成了绩效问题。通常，这意味着我想使用二进制树（C ++）之类的东西 std::map），但是，我也取决于双重链接列表的以下功能，以获得良好的性能：

• 能够将一个链接列表中的连续部分拼接到$ o（1）$时间中的另一个链接列表中。 （摊销$ O（1）$或$ O（ log log n）$就足够了。）

我想利用的数据的一个功能是，我经常有长期的连续记录范围，在这些记录中，每个人的独特整数都比其前身多。当搜索项目的相对排序位置时，由于没有重复的标识符，它将始终在此类连续记录之外。

我想找到一个替换数据结构或扩展到双链接列表，这将使我能够在恒定时间内将整个部分从一个列表中拼接到另一个列表，但允许我找到插入新记录的排序位置比$ O（n）$时间更好。

其他操作包括整个项目的前进和向后迭代。记录索引从零开始，并在64位上向上增长，通常是顺序的，并且在这种情况下，代码效果很好。有时，在后续记录之前，某些记录是不可用的，正是这些缺失记录的插入引起了性能问题。

我发生的一种可能的方法是缓存几个索引的位置。每当剪接删除可能与缓存条目重叠的项目时，缓存都会无效。使用此缓存，搜索可以从缓存点迭代器开始，其唯一索引最接近其位置正在搜索的索引，而不是进行线性搜索。但是，我想更全面地利用连续记录的功能。我还考虑了一个层次结构链接列表，其中我有一个顶级链接的连续区域列表，每个区域都是连续的记录列表，但我没有看到一种简洁的方法来调整链接列表来提供此信息功能。也许以前已经做过这样的事情？我发现跳过列表很近，但是看不到splice（）功能，加上通用的跳过列表不会利用插入在连续记录中永远不会发生的事实。

Answer 1

一种简单的方法可能是使用双关联列表，其中每个程度代表一系列连续记录。每个范围内的记录又可以用双重链接列表来表示。

这可以保留您执行$ o（1）$ time拼接的能力，现在插入操作需要$ o（k）$时间，其中$ k $是extents的数量（而不是$ o（n）$，其中$ n $是记录数）。如果您的范围比记录少得多，那么这可能是部分改进。

我不知道这会比简单的跳过列表或二进制树更好。

请注意，如果您使用二进制树，则仍然可以进行有效的剪接。剪接操作不再是$ o（1）$时间，但可以在$ o（ log ell）$时间中完成，其中$ ell $是剪接段中的记录数。这不如$ o（1）$ time拼接，但根据您不同操作的相对频率，它是您可以考虑的另一种数据结构（例如，在现实数据集上的基准）。

而且，当然，您可以将这些想法（例如，二进制树）结合起来，每个程度又是连续记录的双重连接列表。插入物将花费$ o（ lg k）$时间，并且可以在$ o（ lg ell）$ time中进行剪接（这两者都可能比通过$ o（ lg n）$更好简单的二进制树）。