Thread Doppelte Dateien erkennen (6 answers)
Opened by Strat at 2005-06-19 01:27

Strat
 2005-06-19 01:27
#55539 #55539
User since
2003-08-04
5246 Artikel
ModeratorIn
[Homepage] [default_avatar]
Hallo Leute,

ich stehe gerade vor dem Problem, doppelte Dateien moeglichst effizient zu finden. Ich glaube, ich habe einen recht effizienten Algorithmus gefunden; faellt euch vielleicht was effizienteres ein?

Mir ist dabei folgender Algorithmus eingefallen:
Quote
Lese alle Dateien und speichere sie in einem Hash mit der folgenden Struktur:
Code: (dl )
1
2
3
%hash = ( -s $file1_0 => [ $file1_0, $file1_1, $file1_2, ...],
           -s $file2_0 => [ $file2_0, $file2_1, ...],
           ...);

und dann den hash durchlaufen und wenn irgendwo mehr als ein Element im Value ist, dann auf doppelte vergleichen.

Es handelt sich um etwa 400000 Dateien, alle so zwischen 10kb und 300kb gross, und es ist sehr unwahrscheinlich, dass eine Datei oefter als 2x vorkommt... Falls sehr viele Dubletten vorkommen koennen, waere vielleicht das hashing mit Digest::MD5 eine interessante Alternative.



Habe mal auf die Schnelle den folgenden Code zusammengebastelt. wegen der Fortschrittsanzeige verwende ich einen thread... (war da nicht gerade mal ein RDW?); da da die Festplatte das Nadeloehr ist, duerfte der thread kaum ins Gewicht fallen...
Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#! /usr/bin/perl
use warnings;
use strict;
use threads;
use threads::shared;

use File::Find ();
use File::Compare ();

use vars qw(@RootDirs %Files);

@RootDirs = ('H:\test\');

print STDERR "Reading Files and sorting them...\n";
my $filesCount = 0;
File::Find::find(sub {
    if (-f $_) {
    push (@{ $Files{-s _} }, $File::Find::name);
    if ($filesCount and $filesCount % 5000 == 0) {
        print STDERR "$filesCount files read\n";
    } # if
    $filesCount++;
    } # if
}, @RootDirs);
print STDERR "$filesCount files read and sorted\n\n";

my $compareCount : shared = 0;
my $doubleCount : shared = 0;
my $finished : shared = 0;

print STDERR "Comparing files...\n";
my $thread = threads->create(\&CompareFiles);
while ($finished == 0) {
    sleep(5);
    printf STDERR "%2d%%\t$compareCount/$filesCount => $doubleCount\n", $compareCount*100/$filesCount;
} # while

$thread->join();
# ------------------------------------------------------------
sub CompareFiles {

    foreach (keys %Files) {
    my @items = @{ $Files{$_} };
    my $count = $#items;
    $compareCount += $count+1;

    next if $count == 0;
    for my $i (0..$#items-1) {
        for my $j ($i+1..$#items) {
        my $cmp = File::Compare::compare($items[$i], $items[$j]);
        if ($cmp == 0) {
            $doubleCount++;
            print "$doubleCount\tA:\t$items[$i]\n";
            print "$doubleCount\tB:\t$items[$j]\n\n";
        } # if
        } # for
    } # for
    } # foreach

    print STDERR "Compared: $compareCount files: 2*$doubleCount Duplicates\n";

    $finished = 1;
} # CompareFiles
# ------------------------------------------------------------
\n\n

<!--EDIT|Strat|1119130106-->
perl -le "s::*erlco'unaty.'.dk':e,y;*kn:ai;penmic;;print"
http://www.fabiani.net/

View full thread Doppelte Dateien erkennen