Newsgroup: it.comp.www.php
Titolo: sha, md5, crc32, quale è più veloce?

Vorrei usare il risultato di una di queste funzioni allo scopo di trovare 
delle immagini duplicate in una cartella.
Considerando che il numero di files da controllare č decisamente elevato e 
che se scappa qualche duplicato o c'č qualche falso positivo non ha molta 
importanza, secondo voi quale di queste funzioni potrebbe essere piů 
performante?
Grazie in anticipo 


wrote:

Io farei un controllo triplo:
function isSameImage($file1, $file2)
{
	// Questo costa pochissimo e mi evita il 99% dei check
	// (tranne che con file non compressi...)
	if (filesize($file1) != filesize($file2))
		return false;
	// Questo costa appena di piu', anche se elimina poca
	// roba
	$info1 = getImageSize($file1, $block1);
	$info2 = getImageSize($file2, $block2);
	if (serialize($info1) != serialize($info2))
		return false;
	if (serialize($block1) != $serialize($block2))
		return false;
	// A questo punto potrebbero essere fotogrammi non compressi
	// identici in dimensione e senza EXIF/IPTC a distinguerli.
	// Merita confrontarli a poco a poco.
	$fp1	= fopen($file1, "r");
	$fp2	= fopen($file2, "r");
	while(!feof($fp1))
	{
		$g1 = fread($fp1, 8192);
		$g2 = fread($fp2, 8192);
		if (md5($g1) != md5($g2))
		{
			fclose($fp1);
			fclose($fp2);
			return false;
		}
	}
	fclose($fp1);
	fclose($fp2);
	// In questo caso m'e' costato il doppio che a fare sha1_file
	// su tutti e due. Ma salvo sfighe termonucleari, qui non ci
	// arrivero' quasi mai, tranne che per duplicati veri.
	return true;
}
Leonardo
--
The stars have not dealt me the worst they could do:
My pleasures are plenty - my troubles are two.
But oh!, my two troubles, they reave me of rest:

 secondo voi quale di queste funzioni potrebbe essere più performante?
Da un test rapido:
$ find . -name "*.jpg" | wc -l
2346
$ ./make_hashes.php
Calculating md5sums... 65.461 seconds (2346 files).
Calculating SHA1sums... 16.830 seconds (2346 files).
Calculating CRC32s... 9.802 seconds (2346 files).
$ ./make_hashes.php 
Calculating md5sums... 14.843 seconds (2346 files).
Calculating SHA1sums... 18.008 seconds (2346 files).
Calculating CRC32s... 10.152 seconds (2346 files).
$ ./make_hashes.php 
Calculating md5sums... 12.658 seconds (2346 files).
Calculating SHA1sums... 16.055 seconds (2346 files).
Calculating CRC32s... 12.383 seconds (2346 files).
$
Ora, non so interpretare precisamente questi risultati... ma sembra quasi che
con md5_file() alla prima esecuzione ci metta un'infinità di più. Mi sentirei
di suggerire CRC32, ma non esiste una funzione per i file (come md5_file e
sha1_file). Io ho usato:
function crc_file($file) {
	$file_string = file_get_contents($file);
	$crc = crc32($file_string);
	return sprintf("%u", $crc);
}
Non credo sia il massimo delle prestazioni... però ha "battuto" md5_file() e
sha1_file(). Però non so neanche se gli hash sono unici con CRC32 :)
Ciao,
David
P.S.: ho fatto solo gli hash, nessun controllo sui duplicati...
-- 
 . ''`.  Debian maintainer | 
http://wiki.debian.org/DavidPaleino
 : :'  : Linuxer #334216 --|-- 
http://www.hanskalabs.net/
 `. `'`  GPG: 1392B174 ----|---- 
http://snipr.com/qa_page
   `-   2BAB C625 4E66 E7B8 450A C3E1 E6AA 9017 1392 B174

 		if (md5($g1) != md5($g2))
Perche' aggiungi l'overhead di fare l'MD5 e non confronti direttamente
$g1 e $g2?
-- 
Vuoi distribuire il tuo sito web su CD/DVD?
Prova 
http://www.dwebpro.com/
Vuoi diventare un esperto analista PHP/MySQL?
Vieni a fare uno stage con noi: 
http://www.creativepark.it/stage/

 {
...CUT.....
rigranzio entrambi e mi aggancio per rispondere ad entrambi.
Grazie a David per quei riferimenti sui tempi che mi hanno dato un 
riferimento in più, mentre a Leonardo devo chiedere scusa se non mi  sono 
dilunganto in particolari.
La mia idea è calcolare l'hash di ogni immagine e conservarlo in una tabella 
insieme ad altri dati.
In prima battuta eliminerò i files con lo stesso hash, in seguito userò la 
tabella per evitare di salvare nuove copie delle stesse immagini.
Putroppo il tuo suggerimento lo vedo più adatto ad una ricerca ricorsiva 
fatta a manina e non molto calzante alle mie necessità ovvero quelle di 
conservare anche tutta una serie di informazioni sulle foto.
Cmq di nuovo grazie ad entrambi per il tempo dedicatomi.

 per i file (come md5_file e sha1_file).
Puo usare 
http://www.php.net/hash_file
 per PHP 5 >= 5.1.2


	return true;
...e su un campione di 5286 immagini reali piuttosto grosse (JPG) il giro
del fumo per trovare i duplicati impiega circa 19 secondi.
Trovati 17 duplicati (di cui tre inattesi :-) ). Il tempo di MD5SUM sullo
stesso campione e' stato di 42 minuti circa, dato che sono immagini di un
centinaio di megabyte l'una; l'archivio complessivo e' di circa 0.8 Tera.
Il guadagno rispetto a MD5 non e' granche': 120 volte, ma con immagini di
un megabyte soltanto ciascuna, probabilmente va piu' veloce MD5.
Un sistema _molto_ veloce di accelerare le cose via script e' ottenere la
lista con 'find ... -printf "%s\t%p"' ed effettuare un distinct sul primo
campo. Nel mio caso, da 5286 immagini, mi ritrovo con 63 immagini sole da
esaminare -- in 0.03 secondi (o 10 secondi se deve esaminare l'albero con
la cache fredda). Queste poche immagini posso esaminarle con PHP o SHA1.
<?php
        function getFS(&$fxp)
        {
                if (!isset($fxp['f']))
                        $fxp['f'] = filesize($fxp['n']);
                return $fxp['f'];
        }
        function getIMG(&$fxp)
        {
                if (!isset($fxp['i']))
                {
                        $fxp['i'] = md5(serialize(getImageSize($fxp['n'],
$exif)));
                        $fxp['e'] = md5(serialize($exif));
                }
                return array($fxp['i'], $fxp['e']);
        }
        function getSHA(&$fxp)
        {
                if (!isset($fxp['s']))
                        $fxp['s'] = sha1_file($fxp['n']);
                return $fxp['s'];
        }
        function isSameImage(&$fxp1, &$fxp2)
        {
                if (getFS($fxp1) != getFS($fxp2))
                        return false;
                list($info1, $block1) = getIMG($fxp1);
                list($info2, $block2) = getIMG($fxp2);
                if ($info1 != $info2)   return false;
                if ($block1 != $block2) return false;
                if (getSHA($fxp1) != getSHA($fxp2))
                        return false;
                return true;
        $files  = file('files.txt');
        $fxps   = array();
        foreach($files as $file)
                $fxps[] = array('n' => trim($file));
        $n = count($fxps);
        print "Esame di $n files...\n";
        for($i = 0; $i < $n-1; $i++)
                for ($j = $i+1; $j < $n; $j++)
                        if (isSameImage($fxps[$i], $fxps[$j]))
                                print $fxps[$i]['n'] . " e' un duplicato
di " . $fxps[$j]['n'] . "\n";
?>


$g1 e $g2?
Vuoi la verita'? :-)
Perche' ormai stavo ragionando in termini di MD5...


fatta a manina
E' (piu' o meno) l'unico caso in cui ha senso guardare la velocita'. Non
penso che tu abbia molti upload al minuto, di file di svariati mega.
Se fai il controllo subito dopo l'upload, il file e' gia' in cache e SHA
ti tira fuori l'hash nel giro di frazioni di secondo (per file entro una
decina di megabyte). A quel punto - fra 0.1 e 0.9 secondi ci sara' quasi
un ordine di grandezza, si' - ma l'utente non se ne accorgera' mai.
E la differenza fra md5, sha e crc32, entro una decina di megabyte, mica
ci arriva a un intero ordine di grandezza - sicche', puoi usare quel che
ti pare, non fara' differenza.
Leonardo pratico


 Perche' ormai stavo ragionando in termini di MD5...
Ho fatto alcune prove. Con stringhe di 8Kb uguali, $g1 = $g2 e' piu'
veloce del confronto MD5 di circa 6 volte. Se le stringhe sono diverse,
arriva ad essere anche 120 volte piu' veloce.


arriva ad essere anche 120 volte piu' veloce.
Be', si', e' quello che mi sarei aspettato (avrei detto perfino di piu'
di 120 volte, addirittura).
Nel calcolo dei duplicati pero' il confronto diretto non ha molto senso
perche' dovresti ogni volta confrontare due file da zero. Con MD5 o SHA
invece c'e' il vantaggio di poter memorizzare gli hash, sostituendo (in
potenza) O(N^2) confronti file con N hash e O(N^2) confronti stringa.
Infatti nella versione 2 dell'algoritmo, il controllo "incrementale" l'
avevo abbandonato ritenendo che non valesse la candela.


 penso che tu abbia molti upload al minuto, di file di svariati mega.
Purtroppo č la situazione iniziale ad essere critica perchč ho un archivio 
con circa 80.000 files da cui eliminare gli eventuali duplicati.
E' in questa prima fase, ovvero scrematura e indicizzazione delle immagini 
che mi interessavano le perfomance.
Nel caso di un upload penso che tempi nell'ordine anche di qualche secondo 
possano essere tollerabili, e in questa situazione il tuo esempio invece č 
piů che azzeccato.

che mi interessavano le perfomance.
Ma se sei in una fase di "catch-up", tanto vale lavorare un po' per volta.
Leonardo


 Ma se sei in una fase di "catch-up", tanto vale lavorare un po' per volta.
mille grazie per i consigli e le dritte, ora farò un po' di prove su dei 
gruppi di immagini prese  campione e poi vediamo come comportarsi, anche 
perchè tutto il lavoro se lo smazzerà una macchina dedicata allo sviluppo, i 
risultati poi saranno  trasferiti in produzione.
Ancora grazie a tutti e alla prossima.
Buon Lavoro.
                                        Dante