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.
Verwenden Sie Awk mit einem assoziativen Array, wenn das Dateisystem zu langsam wird. – tripleee
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
Oder einfach 'md5sum *' und vergleichen Sie die beiden Textdateien, die Sie erhalten. – tripleee