Это много записей ;-) порядка 1 000 000 000. лучше быть умным об этом ...
Природа записей не определена: мы просто обнаруживаем их по одному, последовательно читая их, или есть какой-то индекс, или они хранятся в виде файлов в различных каталогах? В вопросе также не указывается наличие базы данных, которую мы можем использовать для данных, подобных индексам (вместо того, чтобы сортировать их по собственному коду). Кроме того, [даже приблизительное] представление о количестве дубликатов поможет направить некоторые варианты выбора на эффективный процесс.
Если индекса нет, мы можем / должны его создать; это можно сделать как первый проход через данные. Этот же проход будет использоваться для создания дайджеста сообщений (хеша) для каждой записи (или, возможно, в целях эффективности, для первых нескольких сотен байтов записи).
Общая идея состоит в том, чтобы быстро создать индекс, который можно использовать для идентификации возможных дубликатов, и завершить список фактических дубликатов, возможно, путем параллельной обработки .
Информация, полезная в индексе, будет:
- длина записи
- первые несколько байтов текста
- хеш-код (подробнее об этом ниже)
- также смещение в файле или любой другой указатель на данные, но, конечно, в отличие от трех вышеперечисленных элементов, его нельзя использовать для определения потенциальных совпадений.
Выбор хеша имеет решающее значение: следует отдавать предпочтение быстрому алгоритму за счет одного, который идеально распределен; количество байтов, хэшированных для каждой записи, также является компромиссом, возможно, от 100 до 200 байтов (т. е. примерно от 10 до 20% среднего размера записи) является хорошим значением, в зависимости от ожидаемого соотношения дубликатов и в зависимости от экономии времени. это обеспечивает (по сравнению с хешированием всю запись). (см. правку ниже)
Как только такой индекс будет доступен, мы можем [относительно быстро / без усилий] получить количество возможных дубликатов; на основе этого результата может быть выполнен второй проход, направленный на улучшение качества индекса, если он не считается достаточно избирательным (исключая записи, которые легко считаются уникальными). Этот второй проход может вычислить другой хеш на всю запись (исключая первые x байтов первого хеша) или на еще одном подмножестве записи. Обратите внимание, что благодаря индексу, этот второй проход может быть многопоточным, если это возможно.
Второй или последний проход требует сортировки записей в группе возможных совпадений (одинаковой длины, одинакового хеш-кода (-ов), одинаковых первых х байтов). Это может быть достигнуто, как описано Pax Diablo, преимущество индекса в том, что такая операция, опять же, может быть многопоточной и включает в себя гораздо меньшие наборы (многие из них). Добавлено : Здесь снова Ник Джонсон замечает, что второй проход может быть ненужным, если мы используем длинный хэш-код (он предлагает SHA1 длиной 128 байт). Предполагая, что нет никакой выгоды в частичном хешировании записей, это очень правдоподобное решение, так как индекс может находиться на диске и все же быстрее сортироваться и храниться, чем если бы мы сортировали / сохраняли целые записи.
Редактировать : Ник Джонсон замечательно показывает, что задержка поиска в дисковом хранилище может быть такой, что простое последовательное чтение будет быстрее, а узким местом является дисковый ввод-вывод ограниченная, функция быстрого хеширования, выполняемая одновременно, может эффективно быть быстрее, чем последовательное чтение, и, следовательно, не добавлять к общему процессу. Это вероятная возможность (особенно если последовательное чтение, если эффективно требуется для определения начала / конца каждой записи и т. Д.), И именно поэтому я «откорректировал свою ставку», написав «1040 * в зависимости от экономии времени, это обеспечивает ... ". Это говорит о том, что фактическая структура записей на диске является одним из открытых параметров вопроса (например, если мы просто читаем из отдельных файлов в каталогах, следовательно, вводим непоследовательное чтение), а также хранилище размером с TeraByte, вероятно, поддерживается причудливым RAID, где задержка поиска, оставаясь проблемой, как правило, значительно улучшена.
Я поддерживаю мое предложение о том, что двухпроходный подход может быть более эффективным, чем тот, в котором каждая запись полностью хэшируется, но я бы хотел подчеркнуть возможность и преимущества однопроходной подход. Как и во многих вопросах интервью, некоторые характеристики ситуации были не определены; идея заключается не столько в том, чтобы заявитель предоставил абсолютно правильный ответ (хотя некоторые ответы могут быть совершенно неправильными!), а в том, чтобы получить представление о его / ее мыслительном процессе и способности определять варианты и точки принятия решений.