Комфорт и автоматизация

Пересравниваем два столбца

Задача

Даны две колонки чисел: колонка A и колонка B. В одном столбце ~10 тысяч позиций, в другом ~40 тысяч. Найти в обеих колонках все совпадения.

Проблема

Первое что приходит в голову — организовать двойной перебор. Во внешнем цикле пройтись от начала до конца колонки A и для каждой её позиции во внутреннем цикле сравнить с каждой позицией из колонки B.

Проблема в том, что полный перебор в этой очень даже типовой практической задаче занимает неоправданное количество времени. Количество сравнений получится:

10 000 х 40 000 = 400 000 000

400 миллионов итераций. Тут даже Excelerate It! не поможет.

Как же быть?

Превратить 400 миллионов в 50 тысяч. А именно — соединить обе колонки в один общий столбец. Отсортировать. Пройтись разок по всем позициям и каждую сравнивать только со следующей (или предыдущей). Если равно, ура, да ведь это же совпадение!

Мелочи

При соединении столбцов нужно каким-то образом отметить из какой колонки взято каждое число. Для этого можно внести соответствующую информацию в соседний столбец, можно воспользоваться комментариями к ячейке. Скорее всего будет необходимо зафиксировать не только принадлежность к изначальной колонке. Возможно, потребуется запомнить порядковый номер позиции в ней.