我的任务是通过某些对象的字段在巨大的内存对象数组中执行快速搜索。我需要选择满足某些条件的对象子集。
可以将标准指定为浮点值或此类值的范围（例如2.5..10）。
问题是要搜索的 float 属性分布不是很均匀；它可能包含几个具有值范围的对象10-20（例如）和另外一百万个具有值的对象0-1，以及另外一百万个具有值的对象100-150。
那么，建立索引以有效搜索这些对象的可能性有多大？欢迎使用代码示例。
问问题
107 次
4 回答
2
如果内存中的数组是有序的，那么二进制搜索将是我的第一次尝试。维基百科条目也有示例代码。
于 2012-07-16T18:51:58.163 回答
1
如果您只进行查找，则单一排序后跟多个二进制搜索是好的。
如果您想要最终的查找速度等等，您也可以尝试一个完美的哈希算法。
如果您需要的不仅仅是查找，请查看 treaps 和红黑树。前者平均速度快，而后者表现不错，操作持续时间可变性低。
于 2012-07-17T00:21:13.580 回答
1
您可以尝试使用范围树来满足范围要求。
于 2012-07-17T04:39:37.077 回答
0
我看不出值的分布与建立索引有什么关系（可能完全重复的例外）。由于数据适合内存，只需提取所有具有原始位置的字段，对它们进行排序，然后按照@MattiLyra 的建议使用二进制搜索。
我们错过了什么吗？
于 2012-07-16T21:38:07.853 回答