优化bin-placement算法

Question

好吧,我有两个集合,我需要将collection1中的元素放入collection2的bin(元素)中,这取决于它们的值是否在给定bin的范围内.

举一个具体的例子,假设我有一个排序的集合对象(bin),它们有一个int范围([1 ... 4],[5..10]等).我需要确定int落入的范围,并将其放在适当的bin中.

foreach(element n in collection1) {
 foreach(bin m in collection2) {
  if (m.inRange(n)) {
   m.add(n);
   break;
  }
 }
}

所以有明显的NxM复杂度算法,但我真的很想看到Nxlog(M).为此,我想使用BinarySearch代替内部foreach循环.要使用BinarySearch,我需要实现一个IComparer类来搜索我.我遇到的问题是这种方法需要我制作一个IComparer.Compare函数来比较两种不同类型的对象(一个元素到它的bin),这似乎不可能或不正确.所以我问,我该怎么写这个算法？

Answer 1

让我们重申一下这个问题.你想写

foreach(int item in items)
    bins[GetBinIndex(item)].Add(item);

这样,GetBinIndex的性能优于O(n)的bin数.

这取决于箱的拓扑结构.

如果垃圾箱只是连续的非负整数范围,比如0..4,5..9,10..14等等,那么只需将项目除以5即可.那是O(1).

如果垃圾箱是不同大小的连续整数范围,比如0..4,5..14,15..16,17..17,18..32,......那么:

• 制作一个List<int>存储每个范围的顶部.所以在这种情况下,{4,14,16,17,32,...}
• 二进制搜索项目列表.
• 如果结果是非负数,那么这是bin的索引,并且您有一个位于其bin顶部的项.
• 如果结果是负数,那么这是其顶部元素大于项目的最佳仓的补充.取索引的补码,这就是垃圾箱.

这是要搜索的O(lg n),而O(n)首先构建列表.

如果bin是非连续的整数范围 - 也就是说,如果范围有空洞,或者它们是重叠的 - 那么要构建以有效地找到最佳范围的数据结构是间隔树.区间树通常是在非病态情况下搜索的O(lg n),并且O(n lg n)首先构建树.