Snelste manier om mdsum output te doorzoeken

[Spider.007]

Ik heb een database met daarin ongeveer 650.000 md5sums erin. Ik wil deze gebruiken als basis om dubbele bestanden uit een andere directory te vissen. Momenteel grep ik op de md5sum; dit gaat verbazingwekkend snel [0.05s]. Het geeft mij echter slechts het idee dat het sneller kan

De lijst met md5sums is al gesorteerd dus zou ik een index aan kunnen leggen en die gebruiken als offset voor een willekeurige applicatie; het vervelende is echter dat ik die applicatie niet kan vinden Met behulp van `grep --byte-offset` kan ik perfect de offset bepalen van bijvoorbeeld de 1e twee karakters van een hash. Ik kan ook bijhouden hoeveel regels er beginnen met die karakters. Ik heb naar een aantal manieren gekeken; logisch zouden head of tail zijn maar deze kunnen niet eens een offset combineren met een limiet op aantal regels dus valt 1 van de 2 voordelen van de index weg. `sed` krijg ik ook niet zo gek om deze wens te voldoen.

Heeft er iemand anders wellicht een idee of er een applicatie is die dit standaard wel kan; of moet ik gewoon zelf wat schrijven?

[BarthezZ]

Naar mijn gevoel zou het efficienter zijn om naar de filesizes te kijken, en indien dat overeenkomt even de md5sum te vergelijken.
Een sum berekenen is naar mijn gevoel toch intensiever dan een ls -(s|l)

en mischien:

bart@bartpc:~$ apt-cache search dupe
fdupes - Identifies duplicate files within given directories
findimagedupes - Finds visually similar or duplicate images

[Paul]

Je noemt het een database. Houdt dat ook in dat je er een SQL-statement op los kunt laten?

select md5, count(md5) as aantal from md5hashes group by md5 where aantal <> 1

[Sprite_tm]

De beste manier is om het natuurlijk in een echte database te gooien. Als je het alsnog met shell-klussen op wilt lossen: bouw je databeest om naar verschillende bestanden. Gooi alle hashes die beginnen met 00 in bestandje md5.00, alle die beginnen met 01 naar md5.01, etc. Als je daarna een hash wilt zoeken, weet je al in welk bestand 'ie staat: gemiddeld versnelt het het zaakje met een factor 256.

[Spider.007]

BarthezZ schreef op zaterdag 18 augustus 2007 @ 14:47:
Naar mijn gevoel zou het efficienter zijn om naar de filesizes te kijken, en indien dat overeenkomt even de md5sum te vergelijken.
Een sum berekenen is naar mijn gevoel toch intensiever dan een ls -(s|l)

en mischien:

bart@bartpc:~$ apt-cache search dupe
fdupes - Identifies duplicate files within given directories
findimagedupes - Finds visually similar or duplicate images

Dat is inderdaad een alternatieve manier om snel aan dubbelen te komen. Ik ben nog geen applicaties tegengekomen die een directory kunnen vergelijken met een bestaande database; als ik 100k bestanden wil vergelijken tegen 650k bestanden die dan nog moeten worden gesummed duurt dat helemaal lang

Ik heb het zooitje zowel in een mysql als in een sqlite database gestopt. De querytijden waren velen malen langzamer dan de huidige grep oplossing. De meerdere files had ik ook aan gedacht als laatste oplossing; wellicht dat dat het toch maar moet gaan worden

edit:

Nou ik heb zelf ff snel wat in PHP geschreven; en het verschil bewijst iig dat het idee goed is. Ik gok dat ik ook gewoon verder ga met wat zelf geschreven scripts tenzij er nog iemand met een util op de proppen komt.

code:

[sjon@spider008 php]$ time grep ^ec .clonespyDB|wc -l
2554

real    0m0.152s
user    0m0.140s
sys     0m0.017s
[sjon@spider008 php]$ time php ./clonespy-index.php |wc -l
2554

real    0m0.023s
user    0m0.013s
sys     0m0.007s

[ Voor 18% gewijzigd door Spider.007 op 18-08-2007 15:39 ]

[Spider.007]

nou; nog even voor het idee dan; fear mijn allereerste c-applicatie

C:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
        if (argc != 4)
        {
                fprintf(stderr, "Usage: body FILE OFFSET LENGTH\n");
                exit(1);
        }

        char *filename = argv[1];
        unsigned int offset = atoi(argv[2]);
        unsigned int length = atoi(argv[3]);

        FILE *fp;
        if (NULL == (fp = fopen(filename, "r")))
        {
                fprintf(stderr, "body: %s: No such file\n", filename);
                exit(-1);
        }

        fseek(fp, 0 , SEEK_END);
        long filesize = ftell(fp);
        rewind(fp);

        if (filesize < offset+length)
        {
                fprintf(stderr, "body: Offset [%d] plus length [%d] exceeds filesize [%d]\n", offset, length, filesize);
                exit(-1);
        }

        fseek(fp, offset, SEEK_SET);

        char *buffer = (char*) malloc (length);
        size_t result = fread (buffer, 1, length, fp);

        printf("%s", buffer);

        free(buffer);

        fclose(fp);
}

code:

real    0m0.003s
user    0m0.000s
sys     0m0.000s

[deadinspace]

Als je nog meer snelheid wil, dan zou je er goed aan doen een programma te maken dat blijft draaien en niet iedere keer aangeroepen hoeft te worden. Als iets vaak moet gebeuren, dan kan de overhead van het starten van losse programmaatjes significant zijn. (maar als de nieuwe files nog gemd5sumd moeten worden, dan valt de opstarttijd van je C progje waarschijnlijk in het niet bij het md5summen)

Spider.007 schreef op zondag 19 augustus 2007 @ 15:26:

C:

        char *buffer = (char*) malloc (length);
        size_t result = fread (buffer, 1, length, fp);

        printf("%s", buffer);

Dat is niet veilig. C strings zijn NUL-terminated, dus printf zal karakters uit je buffer printen tot hij een NUL karakter tegenkomt. Als je ingelezen buffer geen NUL bevat (en die bevatten tekstfiles doorgaans niet), dan zal printf dus uit je buffer lopen.

Om dezelfde reden is je progje ook niet binary-safe

Je kan voorkomen dat printf uit je buffer loopt door de string zelf te NUL-termineren:

C:

        char *buffer = (char*) malloc (length + 1);
        size_t result = fread (buffer, 1, length, fp);
        buffer[length] = '\0';

Maar dat geeft nog geen binary safety.

Ikzelf zou in plaats van de ANSI C fopen/fseek/fread en vrienden liever de POSIX open/lseek/read en dergelijke gebruiken, en dan in plaats van printf() write() naar stdout doen. Dat voorkomt het printf-buffer probleem en geeft binary safety

edit:
Nou ik erover nadenk, je kan natuurlijk ook een fwrite() naar stdio doen om beide problemen op te lossen. Ondanks dat zou ik nog steeds de voorkeur geven aan de POSIX API, maar dat is meer persoonlijke voorkeur dan iets anders

[ Voor 7% gewijzigd door deadinspace op 19-08-2007 17:51 ]

[frim]

Spider.007 schreef op zaterdag 18 augustus 2007 @ 15:22:
[...]

Ik heb het zooitje zowel in een mysql als in een sqlite database gestopt. De querytijden waren velen malen langzamer dan de huidige grep oplossing. De meerdere files had ik ook aan gedacht als laatste oplossing; wellicht dat dat het toch maar moet gaan worden

Heb je wel een goede index gemaakt op de database? Ik zou denken dat een echte database toch wel lekker snel zou moeten zijn.

[Spider.007]

deadinspace schreef op zondag 19 augustus 2007 @ 17:47:
Als je nog meer snelheid wil, dan zou je er goed aan doen een programma te maken dat blijft draaien en niet iedere keer aangeroepen hoeft te worden. Als iets vaak moet gebeuren, dan kan de overhead van het starten van losse programmaatjes significant zijn. (maar als de nieuwe files nog gemd5sumd moeten worden, dan valt de opstarttijd van je C progje waarschijnlijk in het niet bij het md5summen)

Yup, dat weet ik ook wel vrij zeker; daarnaast denk ik dat de opstarttijd redelijk laag zal zijn gezien de eenvoud

[...]

Dat is niet veilig. C strings zijn NUL-terminated, dus printf zal karakters uit je buffer printen tot hij een NUL karakter tegenkomt. Als je ingelezen buffer geen NUL bevat (en die bevatten tekstfiles doorgaans niet), dan zal printf dus uit je buffer lopen.

Om dezelfde reden is je progje ook niet binary-safe

Je kan voorkomen dat printf uit je buffer loopt door de string zelf te NUL-termineren:

C:

        char *buffer = (char*) malloc (length + 1);
        size_t result = fread (buffer, 1, length, fp);
        buffer[length] = '\0';

Maar dat geeft nog geen binary safety.

Ikzelf zou in plaats van de ANSI C fopen/fseek/fread en vrienden liever de POSIX open/lseek/read en dergelijke gebruiken, en dan in plaats van printf() write() naar stdout doen. Dat voorkomt het printf-buffer probleem en geeft binary safety

edit:
Nou ik erover nadenk, je kan natuurlijk ook een fwrite() naar stdio doen om beide problemen op te lossen. Ondanks dat zou ik nog steeds de voorkeur geven aan de POSIX API, maar dat is meer persoonlijke voorkeur dan iets anders

Ik ga even op zoek naar een goed boek; maar ik zal iig het voorgestelde 0-character erbij zetten om evt. problemen te voorkomen. Thanks voor de tips iig

[ATS]

Hou je er ook rekening mee dat je, zelfs als de MD5 sums hetzelfde zijn, je nog steeds niet zeker weet dat de bestanden ook hetzelfde zijn? Die moet je dan natuurlijk ook nog vergelijken... Twee verschillende bestanden kunnen nog steeds dezelfde MD5 opleveren. Het is dus een goede 2e stap zullen we maar zeggen (na vergelijken van de bestandsgrootte, en voor het vergelijken van het hele bestand).

[CyBeR]

ATS schreef op maandag 20 augustus 2007 @ 13:02:
Hou je er ook rekening mee dat je, zelfs als de MD5 sums hetzelfde zijn, je nog steeds niet zeker weet dat de bestanden ook hetzelfde zijn? Die moet je dan natuurlijk ook nog vergelijken... Twee verschillende bestanden kunnen nog steeds dezelfde MD5 opleveren. Het is dus een goede 2e stap zullen we maar zeggen (na vergelijken van de bestandsgrootte, en voor het vergelijken van het hele bestand).

Als je zo gaat werken kun je beter die md5sum overslaan en meteen de files vergelijken.

[Spider.007]

ATS schreef op maandag 20 augustus 2007 @ 13:02:
Hou je er ook rekening mee dat je, zelfs als de MD5 sums hetzelfde zijn, je nog steeds niet zeker weet dat de bestanden ook hetzelfde zijn? Die moet je dan natuurlijk ook nog vergelijken... Twee verschillende bestanden kunnen nog steeds dezelfde MD5 opleveren. Het is dus een goede 2e stap zullen we maar zeggen (na vergelijken van de bestandsgrootte, en voor het vergelijken van het hele bestand).

quote: http://www.unixwiz.net/te...to-hashes.html#collisions

This astonishing fact is due to the astonishingly large number of possible hashes available: a 128-bit hash can have 3.4 x 1038 possible values, which is:
340,282,366,920,938,463,463,374,607,431,768,211,456 possible hashes
If the hash algorithm is properly designed and distributes the hashes uniformly over the output space, "finding a hash collision" by random guessing is exceedingly unlikely (it's more likely that a million people will correctly guess all the California Lottery numbers every day for a billion trillion years)

Ik durf het risico te nemen

[ATS]

Laten we het er op houden dat het er aan ligt waar je het voor wil gebruiken. Als het uit kan om je systeem om te tuin te willen leiden, dan is het een goed idee om eens verder te kijken dan alleen je MD5 hash.
Overigens ben ik het er niet mee eens dat je als je de files zelf nog controleert, het vergelijken van de hashes waardeloos is. Het vergelijken van een 128 bit hash is heel wat sneller dan het vergelijken van een 4GB bestand (als je de hashes al hebt).

[killercow]

ATS schreef op maandag 20 augustus 2007 @ 14:00:
Laten we het er op houden dat het er aan ligt waar je het voor wil gebruiken. Als het uit kan om je systeem om te tuin te willen leiden, dan is het een goed idee om eens verder te kijken dan alleen je MD5 hash.
Overigens ben ik het er niet mee eens dat je als je de files zelf nog controleert, het vergelijken van de hashes waardeloos is. Het vergelijken van een 128 bit hash is heel wat sneller dan het vergelijken van een 4GB bestand (als je de hashes al hebt).

De kans dat zowel de md5 als de size van een bestand het zelfde is En de inhoudt niet het zelfde is is vrijwel nihil, de size kun je ook in werkelijk een miliseconde testen, dus dan heb je er weer een factoor 1000 aan zekerheid bij zonder idd 2x 4gb te moeten controlleren.