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

Question

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

Answer 1

Порядочный алгоритм может быть:

нагрузки все из множества А в HashMap, О (а)

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

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

Answer 2

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

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

3. список Navigate а и В вместе таким образом, что:

   а. Приращивание указателя на A и указателя на B, когда элементы соответствуют

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

   гр. Соответствие было найдено при добавлении в соответствии с этими правилами, так что следующий элемент b в B не соответствует следующему элементу a в A.

---

Это может быть на самом деле интересное место, чтобы применить Bloom filters: построить Bloom фильтр для множества В, то для каждого URL в множестве А определить, если он находится в множестве B. С diminishingly малой вероятностью ошибки вы должен быть в состоянии найти все URL-адреса в A, а не B. B.

Answer 3

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