[gull] Petit problème de maths, pour créer de liens

[Félix Hauri]

Bonjour la liste,

On Thu, May 22, 2008 at 10:30:03AM +0200, cedric briner wrote:
> http://pmatch.rubyforge.org
...

> http://pmatch.rubyforge.org/competition.html
> 
> en esperant que ca puisse t'aider.

Oui!
Merci, j'ai pu constater en lisant ceci que TOUTES les solutions
utilisent plus-ou-moins la solution que j'avais initiallement
implémentée: 
 1. repérer les fichiers de tailles identiques
 2. calcules des hash (md5 et/ou sha) pour repérer les identiques
 3. cmp (ou similaire) par pair de fichiers pour confirmer les identiques
 4. suppression de l'un pour le lier à l'autre.
 5. boucle sur .2 pour toutes les tailles identiques...

Quel que soit la version/implémentation de ce qui précède, le travail
à faire pour la machine est relativement le même.

En discutant avec Daniel, il m'a demandé pourquoi je fais d'abord
un hash pour ensuite faire un cmp par pair de fichier. Cette
attitude me force à lire au moins 2 fois chaque fichiers et doublon
avant de pouvoir agir.

L'idée qu'il m'a donnée est de ne me baser que sur la taille des fichiers
(1 par inodes, bien sur et pas de symlinks) pour les ouvrir TOUS EN 
MEME TEMPS et les comparer simultanément.

Cela semble un peu fous à priori, mais dans les faits:
Soit un disque de 80Go contenant 4mio d'entrées,
 dont 3mio de fichiers, utilisant 72Go de disque et 1mio d'inodes.

Un premier test en utilisant les md5 et cmp à tourné 3 jours
pour parvenir à libérer 40Go.

Un deuxième test sur un disque relativement similaire, mais avec
un process qui
 1. repère les inodes de tailles identiques et les fichiers qui
    s'y rapportent.
 2. pour chaque taille, ouvre un fichier par inode de la taille
    donnée et compare bloc par bloc, tous les fichiers simultanément
    pour fermer et ignorer tous les fichier uniques et créer une
    liste de listes de fichiers identiques.
 3. Par liste de fichiers identiques, séléctionne comme référence
    l'inodes ayant le plus de fichiers pour supprimer les autres
    et les lier au premier (tant qu'il lier un fichier supplémentaire
    sur l'inode de référence, limite ext3: 32'000 limite de mon script:
    30'000 par une variable.).

Au final. pour libérer 40Go, mon script à du en lire ~58Go et à réalisé 
le job et 36heures.

Pour comparaison, la procédure passant par des hash aurrait du lire au
moins 64Go (lecture totale des fichier uniques) pour les md5, puis
comparer par pair de fichier, càd lire au moins 80Go pour en libérer
40, sans compter les fichiers à 3 exemplaires ou plus, pour lesquels
le fichiers en référence est lus autant de fois qu'il doit être comparé.
(Sauf pour les petits fichiers qui resteront en cache).

Mon script se trouve à ouvrir plusieur millier de fichiers simultanément,
mais les résultat est nettement plus rationnel.

Il demande encore un peu de nettoyage, mais sera très prochainement publié.

A+.

-- 
 Félix Hauri  -  <felix at f-hauri.ch>  -  http://www.f-hauri.ch