快速查找整数索引值使用排序的整数数组键

我正在寻找最快的解决方案来查找整数值使用排序的整数数组键。快速查找整数索引值使用排序的整数数组键

键是整型数组，固定长度为3，每个数组都被排序。
该值是一个整数。

我的数据保证只有一个或两个排序的数组具有相同的内容。每个数组都有一个唯一索引。我试图找到匹配的数组对数组。

我的想法是使用字典（我在原型C＃和将移动到C++）

对于每个阵列，我会看在字典，看看它是否已经存在。如果是这样，我将它从字典中删除。如果我没有在字典中找到它，那么它不是单例就是它是匹配对中的第一个，所以我将它添加到字典中。

我的问题是这样的 - 给予数据非常具体的保证，什么是最好的容器 - 考虑到速度是我最关心的问题？此外，任何关于适当（快速）哈希函数或排序整数数组比较函数的建议将不胜感激。

2013-04-12 scotsman60

如果你的代码最终需要C++，不要浪费时间在C＃上。你在C＃中发现的工作很快，并不意味着你在C++中得到了相同的结果。 – Kelmen

CRC32是一种无密码保证的快速哈希函数。此外，除非您希望获得大量具有相同第一个X条目的数组，否则您只能散列第一个X条目以节省时间。 – Patashu

当你到C++，迁移到这个

这是我碰到的最快速的HashMap实现之一。同时，对于C＃来说，等价物会是这样的：http://msdn.microsoft.com/en-us/library/xfhwa508.aspx我想有更快的字典实现可用，但由于C＃不是最终的容器，它应该做得很好。

您可能想要考虑在项目中包含berkeleydb。它非常快速并且可以在数据集增长时管理存储。它也支持各种平台。

2013-04-12 04:12:42

回答