Comparaison de tres grandes listes

Bonjour,

Je me demande quelle est la meilleure solution pour le probleme ci-dessous:

Nous avons deux tres grandes listes de fichiers. Chaque liste est sous forme de fichier texte, chaque ligne du fichier representant le chemin d'acces a un fichier.
Il s'agit de trouver les lignes qui apparaissent dans chaque fichier, autrement dit, trouver les doublons. Le probleme serait trivial si ce n'est le grand nombre fichiers: Chaque liste possede environ 35 millions de fichiers, soit un nombre total de plus de 70 millions de fichiers et chaque liste pese environ 12Go.

Mettre tout ca dans une liste et faire une comparaison bete et simple prendra des jours et des jours....

Quelqu'un a un idee ?

Merci d'avance

Salut,

Citation:

---

Envoyé par JacekB

Quelqu'un a un idee ?

---

Ce n'est pas une question de programmation mais de construction d'une solution ou l'essentiel sera dans la représentation des données et/ou du choix d'un modèle de données (et d'une base de données) qui répondait au besoin.
Imaginez 2 tables avec un schéma comme (path, linenb, md5sum, content) i.e. pour chaque fichier (dont on a le path) et chacune des lignes on stocke le numéro de ligne, son checksum MD5 et son contenu. Ce que vous voulez c'est l'ensemble des lignes des deux tables qui ont même checksum et même contenu.
Ce n'est peut être pas ce qu'il faut faire, c'est juste pour vous suggérer que Python n'est pas le bon forum pour trouver avec quel BDD, modèle de données construire la solution...

- W

Salut,

En python sur une machine perso : passer par un arbre lexicographique (un genre de BST). Pour chaque ligne du fichier on l'insert dans l'arbre. Le temps d'insertion/recherche y est en O(log(n)) contrairement à une recherche naïve dans une liste O(n).
Il y a peut être encore moyen d’accélérer le parcours de l'arbre en manipulant un hash de la ligne et non la ligne complète.
Si le parcours du 2e fichier consiste juste à regarder dans l'arbre du 1er fichier il y a moyen de rajouter du parallélisme.
Passer par un langage compiler feras gagner du temps (python est certes rapide mais bien moins que du compiler).

Je suis pas certain qu'un bdd externe sur une machine perso accélère vraiment le process.

Pour traiter des gros volumes de données le temps d'exécution dépendra dans un premiers temps de l'algorithme utilisé ensuite interviendra la puissance de la machine.

Ensuite pour gagner en efficacité il est toujours possible de paralléliser les tâches en python et éventuellement si tu es équipée d'une carte NVIDIA utiliser la librairie CUDA qui permet d'utiliser les processeurs de la carte graphique.