Как мне найти ближайших соседей для каждого элемента в списке?

У меня есть два набора целых чисел A и B (размер A ] меньше или равно B ), и я хочу ответить на вопрос: «Насколько близко A к B ?». Я хочу ответить на этот вопрос путем измерения того, как далеко вам нужно уйти от заданного a в A , чтобы найти b в B .

Конкретная мера, которую я хочу произвести, выполняет следующее: для каждого a найдите ближайший b , единственная загвоздка в том, что как только я сопоставлю b ] с a , я больше не могу использовать этот b для сопоставления с любыми другими a . (РЕДАКТИРОВАТЬ: алгоритм, который я пытаюсь реализовать, всегда будет отдавать предпочтение более короткому совпадению. Поэтому, если b является ближайшим соседом для более чем одного a , выберите a , ближайший к b . Я не знаю, что делать, если несколько a имеют одинаковое расстояние до b , сейчас я выбираю a , который предшествует b , но это довольно произвольно и не обязательно оптимально.Мера, которую я сделаю для этих наборов, конечный продукт, представляет собой гистограмму, показывающую количество пар по вертикальной оси и расстояние между парами по оси абсцисс.

Итак, если 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, предыдущая => 4, следующая => 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 ; Я не могу сказать, есть ли разумный способ решить, лучше ли более позднее, чем предыдущее (лучше с точки зрения сближения пар). Основная оптимизация, которая меня интересует, - это время обработки.