我有两组整数A和B（大小A小于或等于B），我想回答这个问题，“离 有多近A？B”。我想回答这个问题的方法是衡量你必须从一个给定a的 in走多远A才能找到一个bin B。
我想产生的具体措施如下：对于每个a，找到最接近b的，唯一的问题是一旦我将 ab与 an匹配a，我就不能再用它b来匹配任何其他a的了。（编辑：我试图实现的算法总是更喜欢较短的匹配。因此，如果b最近的邻居不止一个a，请选择a最接近的b。如果不止一个a具有相同的距离，我不确定该怎么办to 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，但问题或多或少与语言无关。
首先我做一个散列，对于出现在 和 的联合中的每个数字都有一个键，
A并且B值指示每个数字是否出现在A、B或两者中，例如，$hash{5} = {a=>1, b=>1}如果数字 5 出现在两个数据集中。（如果它只出现在 中A，你就会有$hash{5} = {a=>1}。）接下来，我迭代
A查找出现在Aand中的所有哈希元素，B在度量中标记它们，然后将它们从哈希中删除。然后，我对所有散列键进行排序，并使散列的每个元素指向其最近的邻居，就像一个链表，其中给定的散列元素现在看起来像
$hash{6} = {b=>1, previous=>4, next=>8}. 链表不知道下一个和上一个元素是否在A或中B。然后我循环从 开始的对距离
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's 出现晚于a's; 的对。我不知道是否有一种明智的方法来决定以后是否比以前更好（在获得更接近的配对方面更好）。我感兴趣的主要优化是处理时间。