0

好的，我有两个集合，我需要将 collection1 中的元素放入 collection2 的 bin（元素）中，具体取决于它们的值是否在给定 bin 的范围内。

举一个具体的例子，假设我有一个排序的集合对象（bins），它有一个 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），这似乎不可能或不正确。所以我在问，我应该如何编写这个算法？

4

4 回答 4

6

让我们重述这个问题。你想写

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

使得 GetBinIndex 的性能在 bin 数量上优于 O(n)。

这取决于垃圾箱的拓扑。

如果 bin 只是简单的连续非负整数范围，例如 0..4、5..9、10..14 等等，那么只需将 item 除以 5，就完成了。那是 O(1)。

如果 bin 是不同大小的连续整数范围，例如 0..4、5..14、15..16、17..17、18..32...，则：

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

这是 O(lg n) 来搜索，而 O(n) 来构建列表。

如果 bin 是不连续的整数范围——也就是说，如果范围有空洞，或者如果它们重叠——那么您想要构建以有效地找到最佳范围的数据结构是区间树。区间树通常是 O(lg n) 来在非病理情况下搜索，而 O(n lg n) 来首先构建树。

于 2010-03-11T17:08:46.957 回答
1

我不确定我是否完全理解这个问题，因为我并没有真正理解这部分：

我遇到的问题是这种方法需要我创建一个 IComparer.Compare 函数来比较两种不同类型的对象（一个元素到它的 bin）

尽管如此，我会尽力做到最好：

IComparer 用于对集合进行排序，以便您可以执行二进制搜索。看看 MSDN 文章：http: //msdn.microsoft.com/en-us/library/system.collections.icomparer.aspx

所以基本上，你要确保你首先使用你的 IComparer 对 Collection2 进行排序，它基本上只是从最低到最高范围对 Bins 进行排序。从您在第二个 foreach 中休息的事实来看，您似乎没有任何重叠，所以这不应该成为问题。

您不会使用 Array.BinarySearch ( http://msdn.microsoft.com/en-us/library/system.array.binarysearch.aspx ) 方法，因为它会搜索数组中的特定对象（也许这是您在上面引用的那个引用吗？），但是您可以毫不费力地实现自己的二进制搜索。

于 2010-03-11T15:31:06.733 回答
0

只有对 Bin2 中的元素进行了排序，二进制搜索才会起作用。因此，将 Bin2 集合更改为排序集合（例如数组）。及时排序m*logm，然后使用二分查找及时放置新项目logm。总而言之：m*logm + n*logm。这可以进一步优化 - 但这是一个开始。

于 2010-03-11T15:15:57.997 回答
0

如果（如果）您的垃圾箱具有可计算的上限和下限索引，那么您的问题将转化为相对简单且高效的一种，即设计散列算法并运行一次要分箱的项目集合。如果你的垃圾箱没有可计算的索引，为什么不转换你的问题，让它们有？

OP的评论进一步：

与其说你的 bin 是否有固定的界限，不如说是否有规则来计算给定 bin 编号的界限。因此，如果您的垃圾箱的边界为 1..5、6..10、11..15 等，则规则是

bin_bounds = (bin_number-1)*5+1..(bin_number*5)

散列函数只是这个函数的逆函数，即给定一个整数，计算 bin 的索引号。

但是，如果您的垃圾箱上的边界基本上是任意的，那么基本上不可能找到这样的哈希函数。根据我的经验，垃圾箱具有任意大小是相对不寻常的。当然，我不知道你的问题的任何细节，所以所有这些可能对你一点帮助都没有。

于 2010-03-11T15:31:09.837 回答