У меня есть два набора целых чисел A и B (размер A меньше или равен B), и я хочу ответить на вопрос: "Насколько близко A к * 1006?" *?». Я хочу ответить на этот вопрос, измерив, как далеко вы должны пройти от заданного 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, но проблема более или менее независима от языка.
Сначала я создаю хеш с одной клавишей для каждого числа, которое появляется в объединении A и B, и значениями, указывающими, появляется ли каждое число в A, B или обоих, например $hash{5} = {a=>1, b=>1}, если число 5 появляется в обоих наборах данных. (Если бы оно появилось только в A, вы бы получили $hash{5} = {a=>1}.)
Далее я перебираю A, чтобы найти все элементы хеша, которые появляются в A и 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, которые появляются позже, чем a; Я не могу сказать, есть ли разумный способ решить, лучше ли позже, чем раньше (лучше с точки зрения сближения пар). Основная оптимизация, которая меня интересует - это время обработки.