Сопоставить один список с другим с минимальной ошибкой

Question

У меня есть два списка, A и B. A будет максимум ~ 1000 элементов, а B будет максимум ~ 100 элементов.Я хочу сопоставить каждый элемент B с элементом A так, чтобы сумма абсолютных разностей пар была минимизирована.

т.е. я хочу выбрать | B |отделяйте индексы от A и назначайте их индексам B, так что следующая сумма минимизируется: сумма (abs (A [j] - B [i]) для i в | B |, j = index_mapping (i))

Мой первый подход:

1. Для каждого элемента B, чтобы вычислить | B |Ближайшие элементы A.
2. Жадно выбирайте пары (т.е. сначала с минимальной ошибкой)

Играя на нескольких простых примерах, ясно, что мой подход не лучший.Это должно работать нормально для моей цели, но мне было интересно, кто-нибудь может предложить лучший подход?

Answer 1

Я закончил сортировку обоих списков и перебрал их для соответствия. Это сработало достаточно для того, что я делал.

Answer 2

Хмм ... Впервые на ум приходит мысль, что если вы можете отсортировать A и B, то, как только вы найдете первое отображение A [j] в B [i], то для B [i + 1], вы можете начать тестирование с A [j] вместо A [0].

Например:

A = [ 23, 34, 38, 52, 67, 68, 77, 80, 84, 95 ]
B = [ 31, 33, 64, 65, 99 ]

Вы начинаете с B [0] = 31 и проходите через A, пока не найдете самое близкое соответствие, A [1]. Поскольку списки упорядочены, вы знаете , что B [1] не будет совпадать с чем-либо меньшим, чем A [1], поэтому вы можете начать сравнение оттуда. Оказывается, A [1] по-прежнему ближайший матч. В B [2] самое близкое совпадение - A [4], поэтому вы знаете, что B [3] не будет совпадать с чем-либо ниже, чем A [4], нет необходимости искать от A [0] до A [3].