我需要一个存储元组的数据结构，并允许我进行如下查询：给定(x,y,z)整数元组，找到下一个（它的上限）。我的意思是考虑自然排序(a,b,c)<=(d,e,f) <=> a<=d and b<=e and c<=f。我尝试过 MSD 基数排序，它将项目分成桶并对它们进行排序（并对元组中的所有位置递归地执行此操作）。有人有其他建议吗？理想情况下，我希望上述查询发生在 O(log n) 内，其中 n 是元组的数量。
问问题
221 次
1 回答
2
两种选择。
对有序数组使用二分查找。如果您使用 (a<<64)|(b<<32)|c 构建键（假设 32 位 int）' 并将它们保存在一个简单的数组中，一个并排打包，您可以使用二进制搜索来定位该值您正在搜索（如果使用 C，甚至还有一个库函数可以执行此操作），而下一个只是一个位置。最坏情况的性能是 O(logN)，如果你可以做http://en.wikipedia.org/wiki/Interpolation_search那么你甚至可能接近 O(log log N)
二进制键的问题是添加新值可能很棘手，如果超出可用内存，可能需要旋转。但它很快，平均只有几次随机内存访问。
或者，您可以通过以某种形式生成带有 a|b|c 的键来构建哈希表，然后让哈希数据指向包含下一个值的结构，无论它可能是什么。一开始创建可能有点困难，因为在生成表时，您需要已经知道下一个值。
哈希方法的问题是它可能会比二进制搜索方法使用更多的内存，如果您没有遇到哈希冲突，性能会很好，但随后会开始下降，尽管在某些情况下该算法有一些变化会有所帮助。哈希方法可能更容易插入新值。
我还看到您在这些方面有类似的问题，所以我想我所说的内容是结合 A、b、c 来生成一个长键，并将其与二进制搜索、哈希甚至 b-tree 一起使用。如果密钥的长度是您的问题（什么语言），您可以将其视为字符串吗？
如果这个答案完全不符合标准，请告诉我，我会看看我是否可以删除这个答案，所以你的问题仍然没有答案，而不是无用的答案。
于 2013-03-21T08:05:30.083 回答