Как найти отдельный URL только в наборе A, а не в наборе B

Question

Существует два набора URL, оба содержат миллионы URL.Теперь, как я могу получить URL от A, которого нет в B. Какие методы лучше?
Примечание: вы можете использовать любую технику, использовать любые инструменты, такие как база данных, mapreduce, hashcode и т. Д.Мы должны считать память эффективной, эффективной.Вы должны учитывать, что каждый набор (A и B) имеет миллионы URL.Мы должны попытаться найти конкретные URL-адреса, используя меньше памяти и меньше времени.

Answer 1

Достойным алгоритмом может быть:

загрузить весь набор A в хэш-карту, O (a)

пройти набор B, и для каждого элемента удалить идентичное значение из набора A(из hashmap), если он существует, O (b)

Тогда ваш hashmap имеет результат.Это будет O (a + b), где a - это размер набора A, а b - размер набора B. (На практике это будет умножаться на время хеширования, которое в идеале соответствует примерно O (1) для хорошего хеша.)

Answer 2

Что-то, возможно, немного наивное, может быть такой процедурой, как

1. Список сортировки A
2. Список сортировки B

3. Перемещение по спискам A и B вместе, напримерчто:

   а.Увеличивать указатель на A и указатель на B, когда элементы соответствуют

   b.Увеличивайте указатель на B до тех пор, пока элемент не будет соответствовать следующему элементу в a или пока запись b в B не появится после следующего элемента в a (это правило отбрасывает элементы в B, которых нет в A)

   c.Найдено совпадение при увеличении с учетом этих правил, так что следующий элемент b в B не соответствует следующему элементу a в A.

---

На самом деле это может быть интересное место для применения Фильтры Блума : создайте фильтр Блума для набора B, а затем для каждого URL-адреса в наборе A определите, находится ли он в наборе B. С малой вероятностью ошибки вам следуетбыть в состоянии найти все URL в A, а не в B.

Answer 3

(sort -u A; cat B B) | sort | uniq -u