Сравните два списка: найдите обычные элементы, уникальные элементы и дубликаты

Инженер по поддержке однажды спросил меня, почему сорок клиентов получили электронное письмо о продлении дважды. На поиск ответа ушёл час, и он был совершенно обыденным: список кампании был собран путем вставки одного экспорта под другой, и сорок адресов существовало в обоих Никто не проверял, потому что проверка означала либо присматриваться к двум тысячам строк, либо писать a VLOOKUP эта половина команды 't доверяет. Итак, никто не проверял, и тем же сорока людям дважды сказали, что с их карты вот-вот будет снята плата.

Такова форма этой проблемы. Согласование двух списков - одна из наиболее распространенных вещей, которые кто-либо делает с данными, и это & #39; настолько скучно, что люди либо пропускают это, либо делают это плохо. Инстинкт обычно заключается в том, чтобы обратиться к инструменту различий, вставить оба списка и щуриться на цветной вывод - что немедленно не удается, потому что разница отвечает на вопрос, который вы задали, и # 39;t задать. Или вы заходите в электронную таблицу и начинаете собирать MATCH/COUNTIF формулы, которые работают, но занимают десять минут и создают артефакт you' никогда не будет использоваться повторно.

Операция, которую вы действительно хотите, имеет имя и it's старше любого из инструментов: установить арифметику. Пересечение, разница, объединение. я строю [Toolz.dev](/и ставлю на основе браузера инструмент сравнения списков вот, но это руководство посвящено понятиям, лежащим в основе: почему порядок следует игнорировать, какой случай тихо ломается и как выбирать между этим и различием.

TL;DR: Чтобы сравнить два списка, рассматривайте каждый как неупорядоченный набор и вычисляйте пересечение (элементы в обоих), два различия (элементы только в A, элементы только в B), и дубликаты в каждом списке. полностью игнорируйте порядок - линейный разряд - это неправильный инструмент, потому что it's позиционный, поэтому переупорядочение списка делает почти каждую строку измененной. Сложите регистр для идентификаторов, таких как электронные письма, но сохраните исходный текст в выводе, обрежьте пробелы перед сравнением и сделайте это в браузере, поскольку списки, которые люди согласовывают, обычно являются данными о клиентах.

На какие вопросы на самом деле отвечает сравнение двух списков?

Как только вы увидите названные операции, формы станут очевидными. задан список А и список Б:

• Пересечение- что's в обоих? Какие подписчики также платят клиентам. Какие из SKU прошлого месяца и #39;s все еще находятся в этом месяце и каталоге #39;s.
• Минус Б- что's только в A? Какие пользователи в CRM так и не попали в биллинг Какие файлы существуют локально, но не на сервере.
• Б минус А- что's только в B? Тот же вопрос в другую сторону, и это's а необычайный вопрос. Отсутствуют счета и отсутствуют CRM - это две отдельные ошибки, имеющие две разные причины.
• Симметричная разница- что's ровно в одном списке? Объединение обоих различий: все, что не совпало, независимо от направления. Это "what's не синхронизировано?" вопрос.
• Союз- все из любого списка, удалено. Слияние, сделано правильно.
• Дубликаты в списке- что 's повторяется внутри A в одиночку? Это вообще сравнение 't, но это 's всегда тот вопрос, который вам, как оказывается, был нужен, потому что это 's, что вызывает двойные отправки и двойное выставление счетов.

Последний стоит выделить. Сопоставление перекрестных списков и дублирование внутри списков независимы: адрес может появляться дважды в A а также появляются в B. Инструменты, которые сообщают только результаты перекрестного списка, пропускают сбой, который стоит денег.

Здесь все отображается непосредственно на операции, которые вы уже знаете из SQL - INTERSECT, EXCEPT, UNION- и на формулы электронных таблиц. Значение выделенного инструмента 't, что он делает что-то, что вы можете't; it's что все шесть ответов отображаются из одной пасты, вместо шести различных формул.

Почему инструмент различий - неправильный выбор для сравнения списков?

Это ошибка, которую я вижу больше всего, и в этом 's стоит быть точным, потому что & quot; сравнить два списка & quot; и & quot;diff два файла & quot; звучат как синонимы.

Разница позиционная. Алгоритмы Diff вычисляют минимальный сценарий редактирования - кратчайшую последовательность вставок и удалений, которая превращает одну последовательность в другую. That's правильная модель для исходного кода и прозы, где строка 40, следующая за строкой 39, есть значимый. Переместите функцию, и diff правильно сообщает, что вы переместили функцию.

Список не имеет значимого порядка. Строка 300 в вашем экспорте CRM не имеет никакого отношения к строке 300 в вашем экспорте счетов. Они & # 39; это два пакета элементов, которые записываются в любой последовательности, в которую возвращается база данных.

Подавайте неупорядоченные данные в позиционный алгоритм, и вы получаете шум. возьмите два списка с одинаковым содержимым, отсортируйте один из них и разделите их:

List A          List B
alice           bob
bob             alice
carol           carol

Об этом сообщает издание Diff alice был удален и повторно добавлен, или что bob сдвинуто - некоторый отток, пропорциональный тому, насколько по-разному сортируются. правильный ответ ничего не изменилось.Каждый элемент находится в обоих списках. Наборы равны. Разница может't сказать, что потому, что это 't спрашивать о членстве.

Таблица сравнения, поскольку инструменты действительно пересекаются в сознании людей, ищущих и то, и другое:

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

Как должна работать чувствительность к регистру?

Это вариант, который люди оставляют по умолчанию, а затем тихо ошибаются, поэтому стоит один раз продумать it's.

Нечувствительное к регистру сопоставление является правильным по умолчанию для данных, которые сравнивают большинство людей. адреса электронной почты, имена пользователей, доменные имена, коды продуктов, коды стран - на практике они традиционно не учитывают регистр, и [email protected] а [email protected] одни и те же люди в каждой системе, которая имеет значение.

Там's педантичная оговорка здесь, что's стоит знать, потому что это's иногда несущий: пер РФЦ 5321, доменная часть адреса электронной почты нечувствительна к регистру, но местный часть - все до @- формально чувствителен к регистру и оставлен на усмотрение принимающего почтового сервера для интерпретации. Итак [email protected] а [email protected] в принципе могут быть разные почтовые ящики. на практике, по сути, каждый крупный провайдер рассматривает их как идентичные, и если вы 're удаляете дубликат списка рассылки, вам следует полностью свернуть регистр. Но если вы 're отлаживаете, почему отскакивает один конкретный адрес, это 's такая деталь, которая оказывается важной.

Случайчувствительный сопоставление правильно для всего, где случай несет информацию: Linux пути к файлам, строки base64, хэши, JWT токены, API ключи, Git SHAs, большинство идентификаторов программирования. складывание случая в списке хэшей паролей объединит различные значения и даст вам уверенно неправильный ответ.

Детали реализации, которые имеют большее значение, чем сам вариант: сложите футляр для сопоставления, но покажите исходный текст. Если вставить [email protected] и инструмент сообщает вам, что 's в обоих списках следует вернуть обратно [email protected]- нет [email protected]. Опускание вывода бесшумно искажает ваши данные на пути к работе, и поскольку обычным следующим шагом является вставка результата куда-то еще, это повреждение распространяется. Инструмент сохраняет первую видимую форму каждого элемента и совпадает со сложенным ключом за кулисами, поэтому выходит то, что вы вставляете.

Пробелы заслуживают такого же отношения и меньше думают. Скопируйте столбец из электронной таблицы или разделите строку, например a, b, c на запятых, и вы получаете предметы, несущие ведущие пробелы. [email protected] а [email protected] являются различными строками и идентичными адресами. обрезка включена по умолчанию по этой причине, и it's опция you'd замечание отсутствует в течение примерно тридцати секунд реального использования.

Какой сепаратор мне использовать?

По умолчанию используется один элемент в строке, который вы вставляете в столбец электронной таблицы - буфер обмена передает значения, разделенные новыми строками, поэтому столбец электронных писем из Excel, Google Sheets или экспорта CSV попадает без переформатирования.

Другие разделители охватывают данные, которые поступают уже в строке Запятая для одной строки CSV или скопированного массива. точка с запятой для Outlook и более старое соглашение Windows для списков адресов. Пространство для вывода оболочки - ls, git diff --name-only проложенный трубопроводом tr, что-либо разделенное пространством. вкладка для строки, вставленной из электронной таблицы горизонтально, а не вертикально.

Следует отметить одно: разделение на запятые не синтаксический анализ CSV. Настоящее поле CSV может содержать запятую внутри кавычек, и наивный сплит порвется "Smith, Jane" в два пункта. Если вы 'вытащите один столбец из подлинного файла CSV с указанными полями, запустите его через CSV-просмотр сначала - он реализует фактические правила цитирования RFC 4180 - затем скопируйте нужный вам столбец. для плоского списка электронных писем или идентификаторов без встроенных запятых разделение нормально, и это не 't всплывает.

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

Как масштабируется сравнение?

Наивный подход к сравнению двух списков - это вложенный цикл: для каждого элемента в A сканируйте все B. That's O (n×m), и it's штраф для ста элементов и непригодный для использования для пятидесяти тысяч, где вы're делаете 2,5 миллиарда строковых сравнений.

Правильный подход индексирует каждый список в хеш-карту, на которую наносится ключ сравнения - сложенная, обрезанная форма элемента - со значением, являющимся первым увиденным оригиналом. построение каждого индекса - это один линейный проход. Тогда каждый вопрос становится поиском по каждому элементу в постоянное время: является ли этот ключ в карте B's? Все сравнение - O (n+m), что означает, что двадцать тысяч элементов с каждой стороны - это сорок тысяч хеш-операций и завершается быстрее, чем браузер может перекрасить.

Тот же индекс даёт дубликаты бесплатно.Count вхождения на ключ при его построении; любой ключ с числом выше единицы дублируется внутри этого списка.No second pass, no extra structure.

На практике потолок равен 't сравнение - it's браузер отображает группу результатов с пятьюдесятью тысячами строк в текстовую область. Арифметика заканчивается за миллисекунды независимо. Если вы ' регулярно сверяете большие списки, вам, вероятно, нужно это в сценарии, а не на вкладке, а приведенный выше алгоритм состоит примерно из десяти строк на любом языке.

Сортировка стоит примечания Результаты отсортированы естественным образом по умолчанию, что означает числовой учет: item2 перед item10, а не после него. проста лексикографическая сортировка ставит item10 сначала потому 1 < 2 символ за символом, что правильно по букве сравнения строк и неправильно по каждому человеческому ожиданию при сканировании идентификаторов или версионированных имен. Выключите сортировку и получите порядок вставки - элементы в последовательности, которые они впервые появились в A, затем B - что иногда является тем, что вы хотите, когда исходный порядок кодирует что-то вроде новизны.

Как это выглядит на практике?

Четыре сценария, в которых I've фактически использовал это, каждый из которых сопоставляется с отдельной группой результатов.

Очистка списка рассылки перед отправкой. Вставьте новый список и ранее отправленный список. Только в А кто имеет't связались - это's ваш список отправки. В обоих кто'd получит дубликат. Дубликаты в А сорок человек из истории вверху этой страницы. Эта проверка занимает пятнадцать секунд, и это & # 39;s тот, который спас бы инженера поддержки на час.

Согласование двух систем. Экспортируйте электронные письма пользователей из CRM в A и из биллинга в B. Только в А зарегистрирован, но никогда не выставляется; только в Б выставляется счет-но отсутствует-от-CRM. Это две разные ошибки. Первый может быть сломанный веб-крюк, второй может быть ручным счетом-фактурой, выставленным кем-то вне потока. Один "эти списки различаются " ответ полностью затеняет это, и именно поэтому оба направления сообщаются отдельно.

Дрейф запасов и каталогов. Экспорт SKU в прошлом месяце и #39;s против этого месяца и #39;s. Только в А прекращено, только в Б является новым, в обоих переносится. здесь сортировка вопросов - экспорт осуществляется из разных систем в разных порядках, и разница сообщает, что весь файл изменен.

Проверка вменяемости развертывания. Файлы на стадии и файлы на производстве, из двух ls выходы вставлены с разделителем пространства. Только в А это то, что еще не отправлено 't.

Шаблон по всем четырем: полезный ответ - почти никогда & quot; списки разные. & quot; It& #39;s какой предметы, в какой направление - именно это задают вам заданные операции и что дает показатель сходства или сводка различий 't.

Мои списки где-нибудь загружены?

Нет, и подумайте на секунду о том, что вы 'd вставить в инструмент, как этот.

Это's экспорт подписчика. список электронных писем клиентов. удостоверения личности сотрудников. номера лицензий. номера счетов. списки, которые люди сверяют, по своей природе близки к самым конфиденциальным данным, которые хранится в организации - вы не согласуете 't не согласовываете списки ничего, вы сверяете списки люди. И & quot;позвольте мне просто вставить эти две тысячи писем клиентов на случайный веб-сайт, чтобы проверить совпадение & quot; это предложение, которое должно остановить вас холод, потому что во многих юрисдикциях, которые & # 39;s отношения процессора, которые вы только что создали без контракта.

Там's нет причин для этого вычисления касаться сети. It's хеш-карты по строкам - несколько сотен строк TypeScript без зависимостей. Инструмент на Toolz.dev полностью работает на вашей вкладке; списки представляют собой строки JavaScript в вашем браузере и #39;s памяти, и они никогда ее не покидают. Ничего не загружается, не регистрируется и не сохраняется. Проверьте это так, как вы'd проверьте любое такое утверждение: откройте вкладку сети и нажмите "Сравнить", или выключите свой Wi-Fi и посмотрите, как он продолжает работать. I've написал больше о том, почему эта архитектура важна именно для этого класса данных Почему инструменты на основе браузера превосходят серверные, йо-

часто задаваемые вопросы

Как сравнить два списка, чтобы найти то, что у них общего?

Вставить один список в список А, другой в список В, и нажать Сравнить.The & quot;In Both" group is the crection - каждый элемент, присутствующий в обоих списках. можно скопировать эту группу самостоятельно, скачать как текстовый файл или экспортировать каждую группу сразу с помощью Copy Report.Order dis't everient, так что списки don't нужно сортировать одинаково.

Как найти элементы, которые находятся в одном списке, но не в другом?

"Только в A & quot; и & quot;Только в B & quot; группы отвечают на это, и они & #39; намеренно разделены. Только в A удерживаются элементы, отсутствующие в списке B; Только в B хранятся элементы, отсутствующие в списке A. Обычно это разные проблемы с разными причинами - отсутствие выставления счетов и отсутствие CRM aren & # 39;t одна и та же ошибка - поэтому объединение их в один ответ теряет необходимую информацию. & quot;Unique & quot; группа объединяет оба, если вам нужна симметричная разница.

Может ли он найти дубликаты внутри одного списка?

Да. Дубликаты в A и дубликаты в B перечисляют каждый отдельный элемент, появляющийся более одного раза в этом списке. Это не зависит от сопоставления перекрестных списков, поэтому элемент может быть как продублирован в A, так и присутствовать в B. It's обычно проверка, которая имеет наибольшее значение на практике, поскольку дубликаты внутри списка являются причиной дублирования электронных писем и двойного выставления счетов.

Влияет ли капитализация на сравнение?

Только если вы хотите, чтобы. Case-specific сопоставление выключено по умолчанию, так что [email protected] а [email protected] рассматриваются как один элемент - и вывод сохраняет любую форму, которую вы вставили, а не понижает размер ваших данных. Включите его для значений, в которых случай имеет значение: пути Linux, строки base64, хэши, ключи API, Git SHA.

Чем 's отличается от этого инструмента текстового различия?

Диф является позиционным: он сравнивает строку 1 со строкой 1 и вычисляет правки, необходимые для превращения одной последовательности в другую, поэтому переупорядочение списка делает почти каждую строку измененной. Этот инструмент полностью игнорирует порядок и спрашивает только, существует ли элемент на каждой стороне. Используйте diff для кода и прозы, где позиция имеет значение; используйте сравнение списков для сверки экспорта, где порядок сортировки произволен.

Могу ли я сравнивать списки, разделенные запятыми, а не новыми строками?

Да - переключите разделитель на запятую, точку с запятой, пробел или вкладку. пробел вокруг каждого элемента по умолчанию обрезается, так что a, b, c разделяется на три чистых элемента. одно предостережение: разделение на запятые isn't реальный анализ CSV, поэтому, если ваши данные имеют поля кавычек, содержащие запятые, сначала извлеките столбец с помощью соответствующего инструмента CSV.

Сколько предметов он может обрабатывать?

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

Мои списки где-нибудь загружены?

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

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