2015-08-01 13 views
6

Ich musste ein Bash-Skript schreiben, um doppelte Dateien heute zu löschen, mit ihren MD5-Hashes. Ich diese Hashes als Dateien in einem temporären Verzeichnis gespeichert:Zeit Komplexität der Suche nach doppelten Dateien in Bash

for i in * ; do 
    hash=$(md5sum /tmp/msg | cut -d " " -f1) ; 
    if [ -f /tmp/hashes/$hash ] ; 
    then 
     echo "Deleted $i" ; 
     mv $i /tmp/deleted ; 
    else 
     touch /tmp/hashes/$hash ; 
    fi ; 
done 

Es funktionierte perfekt, aber führte mich zu fragen: ist es eine zeiteffiziente Art und Weise, dies zu tun? Ich dachte ursprünglich daran, die MD5-Hashes in einer Datei zu speichern, aber dann dachte ich "nein, weil die Überprüfung, ob ein bestimmtes MD5 in dieser Datei ist, es jedes Mal komplett neu lesen muss". Jetzt frage ich mich: ist es das gleiche bei der Methode "create files in a directory"? Hat die Bash [-f] eine lineare oder quasi-konstante Komplexität, wenn sich viele Dateien im selben Verzeichnis befinden?

Wenn es auf das Dateisystem ankommt, was ist die Komplexität von tmpfs?

+1

Verwenden Sie Awk mit einem assoziativen Array, wenn das Dateisystem zu langsam wird. – tripleee

+1

Ich hoffe, dass es für jedes anständige Dateisystem grob logarithmisch ist (in der Anzahl der Dateien), aber Sie werden immer noch viel schneller die Hashes in einer In-Memory-Hash-Tabelle speichern. Wenn Sie beispielsweise Python verwenden können, wäre das eine triviale Angelegenheit. – 5gon12eder

+1

Oder einfach 'md5sum *' und vergleichen Sie die beiden Textdateien, die Sie erhalten. – tripleee

Antwort

1

löschen Ich werde versuchen, um qualitativ zu beantworten, wie schnell Datei Existenz Tests auf tmpfs sind, und dann kann ich vorschlagen, wie Sie Ihre gesamte Programmablauf machen können schneller.

Zuerst, tmpfs Verzeichnis-Lookups verlassen (im Kernel) auf Verzeichnis-Cache-Hash-Tabellen-Lookups, die nicht so empfindlich auf die Anzahl der Dateien in Ihrem Verzeichnis sind. Sie sind betroffen, aber sublinear. Es hat mit der Tatsache zu tun, dass korrekt durchgeführte Hash-Tabellen-Lookups eine konstante Zeit benötigen, O(1), unabhängig von der Anzahl der Elemente in der Hash-Tabelle.

Um zu erklären, wir an der Arbeit sehen können, die von test -f geschehen ist, oder [ -f X ], von coreutils (gitweb):

case 'e': 
    unary_advance(); 
    return stat (argv[pos - 1], &stat_buf) == 0; 
... 
case 'f':     /* File is a file? */ 
    unary_advance(); 
    /* Under POSIX, -f is true if the given file exists 
     and is a regular file. */ 
    return (stat (argv[pos - 1], &stat_buf) == 0 
      && S_ISREG (stat_buf.st_mode)); 

So verwendet er stat() auf den Dateinamen direkt. Kein Verzeichniseintrag wird explizit von test durchgeführt, aber die Laufzeit von stat kann durch die Anzahl der Dateien im Verzeichnis beeinflusst werden. Die Ausführungszeit für den Aufruf stat hängt von der Implementierung des untergeordneten Dateisystems ab.

Für jedes Dateisystem teilt stat den Pfad in Verzeichniskomponenten auf und führt sie durch. Zum Beispiel für den Pfad /tmp/hashes/the_md5: zuerst /, bekommt seinen Inode, dann sieht tmp darin nach, ruft diesen Inode (es ist ein neuer Mountpoint), dann wird hashes Inode, und schließlich dann der Test Dateiname und seine Inode. Sie können erwarten, dass die Inodes bis /tmp/hashes/ zwischengespeichert werden, da sie bei jeder Iteration wiederholt werden, sodass diese Suchvorgänge schnell sind und wahrscheinlich keinen Festplattenzugriff erfordern. Jede Suche hängt von dem Dateisystem ab, in dem sich das übergeordnete Verzeichnis befindet. Nach dem /tmp/ Teil, Nachforschungen geschehen auf Tmpfs (die alle im Speicher ist, außer wenn Sie nicht genügend Arbeitsspeicher und müssen Swap verwenden).

tmpfs in Linux setzt auf simple_lookup, um den Inode einer Datei in einem Verzeichnis zu erhalten. tmpfs befindet sich unter dem alten Namen im Baum linux mm/shmem.c. tmpfs, ähnlich wie ramfs, scheint keine eigenen Datenstrukturen zu implementieren, um virtuelle Daten zu verfolgen, sondern stützt sich einfach auf VFS-Verzeichnis-Caches (unter Directory Entry Caches).

Daher vermute ich, dass die Suche nach dem Inode einer Datei in einem Verzeichnis so einfach ist wie ein Hashtabellen-Lookup. Ich würde sagen, solange alle Ihre temporären Dateien in Ihren Speicher passen, und Sie tmpfs/ramfs verwenden, ist es egal, wie viele Dateien es gibt - es ist O (1) jedes Mal nachschlagen.

Andere Dateisysteme wie Ext2/3 werden jedoch linear mit der Anzahl der Dateien im Verzeichnis belastet.

sie in Speicher

Wie andere vorgeschlagen haben, können Sie auch speichern MD5s im Speicher, indem sie in bash Variablen speichern, und vermeiden Sie das Dateisystem (und die damit verbundene syscall) Strafen. Das Speichern in einem Dateisystem hat den Vorteil, dass Sie von dort wieder fortfahren könnten, wenn Sie Ihre Schleife unterbrechen würden (Ihr MD5 könnte ein Symlink zu der Datei sein, deren Digest übereinstimmt, auf die Sie sich verlassen könnten) Langsamer.

MD5=d41d8cd98f00b204e9800998ecf8427e 
let SEEN_${MD5}=1 
... 
digest=$(md5hash_of <filename>) 
let exists=SEEN_$digest 
if [[ "$exists" == 1 ]]; then 
    # already seen this file 
fi 

schnellere Tests

Und Sie können [[ -f my_file ]] statt [ -f my_file ] verwenden. Der Befehl [[ ist eine integrierte Bash und ist viel schneller als ein neuer Prozess (/usr/bin/[) für jeden Vergleich zu erzeugen. Es wird einen noch größeren Unterschied machen.

was ist/usr/bin/[

/usr/bin/test und /usr/bin/[ sind zwei verschiedene Programme, aber der Quellcode für [ (lbracket.c) ist die gleiche wie test.c (wieder in coreutils):

#define LBRACKET 1 
#include "test.c" 

so sind sie austauschbar.

0

Die Wahl zwischen dem Lesen des Inhalts einer Datei, die Hashes enthält, und dem Finden eines Hashs in einem Verzeichnis von Dateinamen, die die Hashes sind, kommt im Grunde auf "ist der Kernel schneller beim Lesen eines Verzeichnisses oder Ihres Programms beim Lesen einer Datei". Beide werden eine lineare Suche für jeden Hash beinhalten, so dass Sie mit dem gleichen Verhalten enden. Sie können wahrscheinlich argumentieren, dass der Kernel ein wenig schneller sein sollte, aber die Marge wird nicht groß sein. Beachten Sie, dass die lineare Suche am häufigsten erschöpfend ist, da der Hash nicht existiert (es sei denn, Sie haben viele doppelte Dateien). Wenn Sie also ein paar tausend Dateien verarbeiten, werden die Suchvorgänge insgesamt einige Millionen Einträge verarbeiten - es handelt sich um ein quadratisches Verhalten.

Wenn Sie viele Hunderte oder Tausende von Dateien haben, würden Sie wahrscheinlich besser mit einer zweistufigen Hierarchie - zum Beispiel ein Verzeichnis mit zwei Zeichen Unterverzeichnis 00 .. FF, und dann speichern den Rest von der Name (oder der vollständige Name) im Unterverzeichnis. Eine geringfügige Variation dieser Technik wird beispielsweise in den Verzeichnissen terminfo verwendet. Der Vorteil ist, dass der Kernel nur relativ kleine Verzeichnisse lesen muss, um festzustellen, ob die Datei vorhanden ist oder nicht.

0

Ich habe das nicht "hashed", aber ich würde versuchen, Ihre md5sums in einem Bash Hash zu speichern.

Siehe How to define hash tables in Bash?

Speichern Sie die MD5-Summe als Schlüssel, und wenn Sie möchten, die Dateinamen als Wert. Prüfen Sie für jede Datei, ob der Schlüssel in der Hash-Tabelle bereits existiert. Wenn dies der Fall ist, interessiert Sie der Wert nicht, aber Sie können ihn verwenden, um den Namen der ursprünglichen doppelten Datei auszudrucken. Löschen Sie dann die aktuelle Datei (mit dem doppelten Schlüssel). Da ich kein Bash-Experte bin, würde ich anfangen, nachzusehen.

2

Ich bin ein Fan des richtigen Tools für den Job. In diesem Fall möchten Sie nur doppelte Dateien sehen. Ich habe dies mit mehreren tausend Dateien getestet, die mir zur Verfügung standen, und das erneute Lesen der Datei schien keine Probleme zu haben. Außerdem habe ich festgestellt, dass ich Hunderte von doppelten Dateien habe. Wenn ich Hashes in separaten Dateien speichere und dann diese große Menge an Dateien verarbeite, schleicht sich mein System langsam nach etwa 10.000 Hash-Dateien in einem Verzeichnis ein. Wenn alle Hashes in einer einzigen Datei enthalten waren, beschleunigte sich dies erheblich.

# This uses md5deep. An alternate is presented later. 
md5deep -r some_folder > hashes.txt 

# If you do not have md5deep 
find . -type f -exec md5sum \{\} \; 

Dies gibt Ihnen Hashes von allem.

cut -b -32 hashes.txt | sort | uniq -d > dupe_hashes.txt 

Das cut verwenden den Hash für jede Datei, sortieren Sie die Hashes zu erhalten, dann alle dupliziert Hashes finden. Diese werden ohne die angehängten Dateinamen in dupe_hashes.txt geschrieben. Jetzt müssen wir Hashes zurück zu den Dateien zuordnen.

(for hash in $(cat dupe_hashes.txt); do 
    grep "^$hash" hashes.txt | tail -n +2 | cut -b 35- 
done) > dupe_files.txt 

Dies scheint nicht langsam für mich zu laufen.Der Linux-Kernel leistet sehr gute Arbeit, Dateien wie diese im Speicher zu behalten, anstatt sie häufig von der Festplatte zu lesen. Wenn Sie dies im Speicher erzwingen möchten, können Sie einfach /dev/shm/hashes.txt statt hashes.txt verwenden. Ich habe festgestellt, dass es in meinen Tests unnötig war.

Das gibt Ihnen jede Datei, die ein Duplikat ist. So weit, ist es gut. Wahrscheinlich möchten Sie diese Liste überprüfen. Wenn Sie auch das Original auflisten möchten, entfernen Sie das Bit tail -n +2 | aus dem Befehl.

Wenn Sie sich sicher sind, dass Sie alle aufgelisteten Dateien löschen können, können Sie Dinge an xargs weiterleiten. Dadurch werden die Dateien in Gruppen von 50.

xargs -L 50 rm < dupe_files.txt 
+0

Warum würden Sie die md5sum einer Datei berechnen, wenn nichts anderes genau die gleiche Größe hat? Es gibt kein mögliches Duplikat. Werkzeuge wie 'fdupes' wissen das bereits. –

+0

Und wenn es nur zwei Dateien mit einer bestimmten Größe gibt, ist es besser, sie in Chunks zu vergleichen, damit Sie aufhören können, ohne es vollständig zu lesen, sollten Sie einen Ort finden, wo sie sich früh unterscheiden. Es gibt * viele * Optimierungen, die der naive let's-just-md5sum-alles-Ansatz ablehnt. –

+0

(Überprüfen, dass zwei Verzeichniseinträge, für die stat eine identische Größe zurückgibt, nicht auf dieselbe Inode zeigen, bevor sie zweimal hashed sind, ist eine andere solche einfache, billige Optimierung). –

Verwandte Themen