Если ограничения на память нет, вы можете сначала прочитать все URL-адреса из файла a в памяти и поместить их в HashSet, а затем прочитать URL-адреса из файла b. При каждом чтении URL-адреса оценивается, существует ли этот URL-адрес. в HashSet. Если он существует, то этот URL-адрес является общим URL-адресом этих двух файлов, в противном случае это не так.

Поскольку вопрос требует, чтобы объем памяти был всего 4 ГБ, а размер каждого файла составлял 5 миллиардов * 64Б = 5 * 64 ГБ = 320 ГБ, что намного превышает лимит памяти, поэтому невозможно прочитать все URL-адреса в память при один раз. В это время вы можете использовать метод разделенного пакетного чтения. Ниже представлены два часто используемых метода:

Метод 1: Хэш-метод

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

Сначала просмотрите файл a и найдите хэш для каждого ul. значение и хешируется в 1000 файлов. Метод решения: h=hash(url)%1000, а затем в соответствии с. Hash Результаты этих url Хранятся в файле fa, посредством хеширования, все URL будет распределен между 1000 файлами (fa0, fa2, fa3,..., fa999). Размер каждого файла примерно 300Мб. Аналогично изменяем. url также хэшируются в файл с использованием того же метода расчета, все URL будет распределен среди 1000 (fb0, fb1, fb2,..., fb999) в файле. Очевидно, с fa0 в том же u1 может существовать только в fb0 середина,поэтому,Просто найдите файлы отдельноfaiиfbi(0<i<999)в том жеurl Вот и все.

Кроме того, если после хеш-обработки все еще остаются небольшие файлы, занимающие более 4 ГБ памяти, тот же метод можно использовать для разделения файлов на более мелкие файлы для обработки.

Метод 2: метод фильтра Блума

Подобные проблемы встречаются во многих местах в повседневной жизни. Например, при разработке компьютерных программных систем часто необходимо определить, находится ли элемент в наборе программного обеспечения для обработки текста; Английское слово написано правильно ; В ФБР — указано ли имя подозреваемого в списке подозреваемых в веб-сканерах, был ли посещен URL-адрес и т. д.

Для решения этих проблем,Самое прямое решение — хранить все элементы набора в компьютере.,Всякий раз, когда встречается новый элемент,Просто объедините это ссередина Элементы Вот и все. Хотя этот метод может выполнить задачу точно, существует проблема: слишком много сравнений и эффективность относительно низкая. Когда объем данных невелик, эта проблема низкой эффективности не является существенной, но когда. Когда объем данных огромен, например, при обработке больших объемов данных, проблема низкой эффективности хранения становится очевидной. Например, почтовым ящикам всегда необходимо фильтровать спам. Один из способов сделать это — записывать электронные письма, рассылающие спам. адрес, но поскольку эти отправители будут продолжать регистрировать новые адреса, если используется хеш-таблица, в ней будет храниться 100 миллионов. Email адрес, вообще говоря, каждого Emal Адрес должен быть занят 16B, поэтому всего необходимо 100 миллионов * 16B, что составляет около 1,6 ГБ. Обычный сервер не может хранить такой большой объем информации, если это не суперкомпьютер.

Фильтр Блума — эффективный способ решения этой проблемы. Это эффективная по пространству и времени структура случайных данных, используемая для определения принадлежности элемента множеству. Но это также создает проблему: точность приносится в жертву. Фильтр Блума жертвует точностью в обмен на повышение эффективности использования пространства и времени. Когда он определяет, что элемент не принадлежит этому набору, элемент не должен принадлежать этому набору; когда он определяет, что элемент принадлежит этому набору, элемент не обязательно принадлежит этому набору. В частности, существует две возможности результатов запроса, а именно «не принадлежит этому набору (определенно правильно)» и «принадлежит этому набору (возможно, неправильно)». Таким образом, фильтр Блума подходит для приложений, в которых допускается низкий уровень ошибок.

Его основной принцип — комбинированное использование битовых массивов и хеш-функций. В частности, во-первых, фильтр Блума представляет собой битовый массив, содержащий m бит. Каждый бит массива инициализируется значением 0, а затем определяются k различных хеш-функций. Каждая функция может сопоставлять элементы набора с битовым массивом кого-либо. Когда элемент вставляется в коллекцию, k бит в битовом массиве могут быть получены в соответствии с k хэш-функциями, и эти биты устанавливаются в 1. Если вы запрашиваете, принадлежит ли элемент множеству, вы можете получить k битов в битовом массиве на основе k хеш-функций. Если некоторые биты не равны 1, то элемента определенно нет. this set ; Если все эти k бит равны 1, то элемент может находиться в этом наборе (при вставке других элементов эти позиции могут быть установлены в 1, что генерирует ошибку).

Следовательно, сложность использования фильтра Блума заключается в том, как определить размер битового массива m и хэш-функции на основе количества входных элементов n. Когда количество хеш-функций k=(In2)*(m/n), частота ошибок является наименьшей. Когда частота ошибок не превышает E, m должно быть как минимум равно n*lg(1/E). для представления любых n элементов. Но m должно быть больше, поскольку по крайней мере половина битового массива должна быть равна 0, тогда m должно быть больше или равно n*lg(1/E)*lge, что примерно в 1,44 раза больше n*lg(1E). (lg означает логарифм по основанию 2).

Например, если предположить, что E равно 0,01, то есть частота ошибок равна 0,01, то m должно быть примерно в 13 раз больше n, поэтому k равно примерно 8 (примечание: единицы измерения m и n разные, единицей измерения m является бит). , а n — в единицах количества элементов). Обычно длина одного элемента составляет много бит, поэтому использование фильтра Блума обычно экономит память.

Преимущество фильтра Блума в том, что он имеет хорошую экономию пространства и времени. Время его вставки и запроса постоянно, и сам элемент не сохраняется, поэтому он имеет хорошую безопасность. Однако эти преимущества достигаются за счет точности. Когда вставлено больше элементов, вероятность ошибочного решения о том, что «элемент принадлежит этому набору», увеличивается. Кроме того, фильтр Блума может только вставлять элементы, но не может удалять элементы, поскольку результаты хэширования нескольких элементов могут использовать один и тот же бит в структуре фильтра Блума. Удаление элемента может повлиять на обнаружение нескольких элементов. Следовательно, фильтр Блума можно использовать для реализации словаря данных, определения веса данных или поиска пересечения наборов.

По этому вопросу: 4 ГБ памяти могут представлять 34 миллиарда бит. Используйте метод фильтра Блума, чтобы сопоставить URL-адрес в файле a с этими 34 миллиардами бит, а затем просмотрите файл b, чтобы определить, существует ли он. Однако при использовании этого метода будет определенная доля ошибок.

Этот метод можно использовать только в том случае, если допускается определенная частота ошибок.