Comment trouver une URL distincte uniquement dans l'ensemble A pas dans l'ensemble B

Question

Il existe deux ensembles d'URL, les deux contiennent des millions d'URL. Maintenant, comment puis-je obtenir une URL de A qui n'est pas dans B. Quelles sont les meilleures méthodes?
Remarque: vous pouvez utiliser n'importe quelle technique, utiliser des outils tels que base de données, mapreduce, hashcode, etc. Nous devrions considérer la mémoire efficace, efficace dans le temps. Vous devez considérer que chaque ensemble (A et B) a des millions d'URL. Nous devrions essayer de trouver les URL spécifiques en utilisant moins de mémoire et moins de temps.

Answer 1

Un algorithme convenable pourrait être:

charge tous ensemble A dans un hashmap, O (a)

traverse l'ensemble B, et pour chaque élément, supprimer la valeur identique de l'ensemble A (à partir de la hashmap) s'il existe, O (b)

Ensuite, votre hashmap a le résultat. Ce serait O (a + b) où a est la taille de l'ensemble A et b est la taille de l'ensemble B. (En pratique, cela serait multiplié par le temps de hachage, qui correspond idéalement à environ O (1) pour un bon hachage .)

Answer 2

Quelque chose peut-être un peu naïf peut-être une procédure comme

1. liste Trier a
2. liste Trier B

3. Naviguer la liste a et B ensemble tel que:

   a. Incrémenter le pointeur sur A et pointer sur B lorsque les éléments correspondent

   b. pointeur incrémenter B jusqu'à ce que l'élément correspond à l'élément suivant a ou jusqu'à ce que le dossier b dans B apparaîtrait après l'élément suivant a (cette règle défausse éléments B qui ne sont pas en A)

   c. Une correspondance a été trouvée lors de l'incrémentation de ces règles, de sorte que l'élément suivant b dans B ne correspond pas à l'élément suivant a dans A.

---

Cela pourrait effectivement être un endroit intéressant à appliquer Bloom filters: la construction d'un filtre Bloom pour voir B puis pour chaque URL dans l'ensemble A déterminer si elle est dans le jeu B. Avec diminishingly faible probabilité d'erreur que vous devrait être capable de trouver toutes les URL dans A pas dans B.

Answer 3

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