我应该如何找到列表中每个元素的最近邻居？

Question

我有两套整数的A和B(尺寸A小于或等于B),我想回答这个问题,"如何接近是A要B？".我想回答这个问题的方法是通过产生的你有多远,从给定去衡量a在A寻找b中B.

我想生产的具体措施将执行以下操作:对于每一个a,找到最近的b,唯一的缺点是,一旦我匹配b有a,我不能再使用b,以匹配任何其他a的.(编辑:我试图实现的算法总是更喜欢较短的匹配.所以,如果b是最近的邻居a,请选择a最近的b.我不知道如果不止一个a具有相同的距离该怎么办对b,现在我挑选a先于b,但这是很随意的,并不一定是最佳的.)的措施,我会为使这些套,最终的产品,是表示垂直轴的对数直方图和两对在x轴上的距离.

所以,如果A = {1, 3, 4}和B = {1, 5, 6, 7},我将得到以下a,b对:1,1,4,5,3,6.对于这些数据,直方图应显示一对距离为零,一对距离为1,一对距离为3.

(这些集合的实际大小有一个大约100,000个元素的上限,我从磁盘中读取它们已经从低到高排序.整数范围从1到~20,000,000.编辑:同样,元素的A和B是唯一的,即没有重复的元素.)

---

我提出的解决方案感觉有点笨重.我正在使用Perl,但问题或多或少与语言无关.

1. 首先是让一个哈希值,对每个出现在的联合头号键A和B以及指示每个号码是否出现在值A,B或这两者,例如,$hash{5} = {a=>1, b=>1}如果该号码5只出现在两个数据集.(如果它只出现在A你身上,你会有$hash{5} = {a=>1}.)

2. 接下来,我迭代A查找出现的所有哈希元素,A并B在度量中标记它们,并从哈希中删除它们.

3. 然后,我对所有哈希键进行排序,并将哈希点的每个元素设置为其最近的邻居,如链接列表,其中给定的哈希元素现在看起来像$hash{6} = {b=>1, previous=>4, next=>8}.链表不知道下一个和前一个元素是否在A或B.

4. 然后我循环开始对的距离d=1,找到所有带距离的对d,标记它们,从哈希中删除它们,直到没有更多A要匹配的元素.

循环看起来像这样:

for ($d=1; @a > 0; $d++) {
    @left = ();
    foreach $a in @a {
        $next = $a;
        # find closest b ahead of $a, stop searching if you pass $d
        while (exists $hash{$next}{next} && $next - $a < $d) {
            $next = $hash{$next}{next};
        }
        if ($next is in B && $next - $a == $d) {
            # found a pair at distance $d
            mark_in_measure($a, $next);
            remove_from_linked_list($next);
            remove_from_linked_list($a);
            next;
        }

        # do same thing looking behind $a
        $prev = $a;
        ...

        # you didn't find a match for $a
        push @left, $a;
    }
    @a = @left;
}

这个循环显然更喜欢匹配b后出现的匹配a; 我不知道是否有一种明智的方法来决定以后是否比先前更好(更接近成对).我感兴趣的主要优化是处理时间.

Answer 1

听起来您有分配问题的特殊情况（在加权二分图中找到最小匹配）。

解决分配问题的算法对于 O(N^3) 来说对你来说太慢了，但我很确定你可以通过利用你的特定权重函数或者你只想要直方图而不是直方图来削减一些复杂性。精确匹配。