Speeding up mass value comparison?

[Quinch]

I've got a small problem I could use some help with. I've put together a script that downloads a lot of small files, then compares them against a list to see which ones to keep. The list is simple enough, a twodimensional array consisting of a MD5 hash and filenames that match that hash. The script basically goes through an for-to loop comparing each value, but since the array will grow into tens or hundreds of thousands of entries, the one-by-one kind of approach is likely to turn into something that runs at a snail's pace. With that in mind, are there ways, preferably simple, to speed it up? Would loading the entire index as a single string variable and using stringinstr and similar commands to check for and edit values be faster?

Edited January 23, 2012 by Quinch

[water]

Are the lists sorted by name?

[Quinch]

Nope... although... if I sort the list by hash value, maybe I could go by a "by half" route - start looking at the middle, if the hash to be compared against is greater/smaller than the midpoint, split the remains, etc until the un-eliminated section to be searched is something reasonable.

That still leaves me looking for filenames, though - each hash has one or more filenames attached to it, and if a match is found, return the first filename associated with that hash, so the sort-and-split approach wouldn't work there.

I've attached both the script and an example of the list - the index is the result of a single page backup, and since the script is intended as a mid-to-long term solution, it's going to grow - a lot.

archiver.au3

MD5_index.txt

[DicatoroftheUSA]

I found filelisttoarray to be very slow, I prefer to use string based file searches such as FileFindFirstFile() etc...

Edited January 23, 2012 by DicatoroftheUSA

[Melba23]

DicatoroftheUSA,

Have you looked inside the _FilelistToArray function?

Probably not or you would have seen:

Func _FileListToArray($sPath, $sFilter = "*", $iFlag = 0)
    Local $hSearch, $sFile, $sFileList, $sDelim = "|"
    $sPath = StringRegExpReplace($sPath, "[/]+z", "") & "" ; ensure single trailing backslash
    If Not FileExists($sPath) Then Return SetError(1, 1, "")
    If StringRegExp($sFilter, "[/:><|]|(?s)As*z") Then Return SetError(2, 2, "")
    If Not ($iFlag = 0 Or $iFlag = 1 Or $iFlag = 2) Then Return SetError(3, 3, "")
    $hSearch = FileFindFirstFile($sPath & $sFilter) ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    If @error Then Return SetError(4, 4, "")
    While 1
        $sFile = FileFindNextFile($hSearch) ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        If @error Then ExitLoop
        If ($iFlag + @extended = 2) Then ContinueLoop
        $sFileList &= $sDelim & $sFile
    WEnd
    FileClose($hSearch)
    If Not $sFileList Then Return SetError(4, 4, "")
    Return StringSplit(StringTrimLeft($sFileList, 1), "|")
EndFunc   ;==>_FileListToArray

How else did you think it worked?

M23

[Mikeman27294]

That works similarly to something I have been doing recently - I was using the pipe as a delimiter and splitting at that to make my arrays.

I would suggest something like that. It doesn't really matter if it doesn't look nice in the archive, does it? You could just have "FileName|MD5|AnotherFileName|MD5"

Then you could create the array based on stringsplitting by the pipe ( | - that is a pipe, if you dont know.)

[DicatoroftheUSA]

@Melba23

Yes, but what I mean is I personally tend to avoid using arrays entirely.

I am not the best at using Autoit, but whenever I use arrays, rather than strings only it seems rather slow. Especially if re-dim is required.

Edited January 23, 2012 by DicatoroftheUSA

[Spiff59]

Even though the MD5's are not unique, your filenames are, so sorting by name, as Water mentioned, would allow you to do binary searches. Beyond that, you could split your huge list into parts, for instance, 27 arrays, A-Z + non-alpha, and search the smaller arrays depending on the first character of the filename. Or, you could always go with using a database.

Come to think of it, you could probably also "cheat" and use Yashied's Assign/IsDeclared route which is lightning fast. Assign your filenames as the variable name (with some sort of appended prefix or suffix to avoid conflicts with "real" variables) and set the MD5 as the value of the dummy variable. Maybe something like:

Global $array[5][2] = [[4,0],["Acrobat.exe", 3333333333],["Explorer.exe", 7777777777],["Windows.exe", 1234567890],["Winzip.exe", 99999999999]]
Global $filename, $filehash

For $x = 1 to $array[0][0] ; load array to variables
    Assign("__" & $array[$x][0], $array[$x][1])
Next

$filename = "Explorer.exe"
$filehash = 6666666666
MsgBox(0,"","Found = " & Search())

$filename = "Windows.exe"
$filehash = 1234567890
MsgBox(0,"","Found = " & Search())

Func Search()
    If IsDeclared("__" & $filename) And Eval("__" & $filename) = $filehash Then Return 1
EndFunc

[jchd]

Quinch,

Look around for ScriptingDictionary. It should do the job efficiently for your purpose. Of course, use the hash as key and filename as value.

Another option would be to use SQLite for that but it may be a bit slower and less easy to use for such a simple application if it's used once. The advantage of an SQLite database is that you can grow your database as much as you need without (essentially) any performance penalty until you reach an undecent number of hash/filename couples.

[Melba23]

DicatoroftheUSA,

Especially if re-dim is required

Now there you are quite correct!

But arrays are very useful and there are ways to reduce the number of ReDims you need - even if you do not know how big your array will become. Take a look at the final example in the Recursion tutorial in the Wiki.

M23

[KaFu]

Look around for ScriptingDictionary. It should do the job efficiently for your purpose. Of course, use the hash as key and filename as value.

[Quinch]

Well... crap. That's one step forward and two steps back. I've been looking at some of these filenames and it's pretty obvious that they can't be the one and the same file. You're right - MD5 hashes are't unique - or unique enough, at least - to reliably use as a check if two files are identical in content.

Which brings me to a new question - short of comparing file contents outright, what would be? Would a layered approach work? For example, check for filesize matches, then check those for MD5 if a match is found? When dealing with thousands of files mostly under 10Kb, what would the reliability rate be between those two, offhand?

[BrewManNH]

If you're using a 2D array, you could sort the array on the "column" that you want to search in and use the _Array.au3 file in my signature, which includes a 2D version of _ArrayBinarySearch which would greatly speed up the searching process.

[jchd]

I beg your pardon. Do any of you guys seriously expect MD5 collisions on random 10k files? I mean spurious MD5 collisions on non-cooked data/executable, real-world files?

Can you exhibit one non_cooked example (just curious)?

Hint: that would be a world record!

[MvGulik]

Yes, but what I mean is I personally tend to avoid using arrays entirely.

Learn when, and when not, to use them and they will serve you well, young ... erm.

[Quinch]

I beg your pardon. Do any of you guys seriously expect MD5 collisions on random 10k files? I mean spurious MD5 collisions on non-cooked data/executable, real-world files?

Not sure if sarcastic {of if I'm not awake enough to read this right} but check the MD5 index file attached a few posts up - there's a couple of MD5 entries that contain files in both gif, jog and png format, so... I guess yes?

[jchd]

No sarcastic at all. To be honest, I didn't look at your index file before.

Now it's just plain impossible to collect as many _spurious_ MD5 collision on distinct _non-cooked_ binary files as your index file shows.

What that suggests is that there must be something wrong in the MD5s you obtain.

Can you post a couple of distinct binary files colliding (please no cheating here)?

Please get me right: I'm not saying that MD5 collisions can't be computed, but that requires very (and I mean VERY) special conditions on both input files (and then you're not free to choose the resulting MD5).

The odds of random (or so, like jpg, png) 10kb binary files colliding spuriously while being internally completely distinct are unchanged and still much, much less than the odds of having a neutrino interact with your PC and changing a single bit somewhere. And the latter odds are so small that you can bet you life safely on it.

What is commonly known is that given an input file A with MD5 hash M[A], it only takes seconds to compute another distinct file B with M[A] = M[A].

That's what makes MD5 unsecure for any cryptographic purposes: an opponent may _compute_ a distinct file and exhibit it, claiming it's the original. Turning the counterfeit file with same MD5 into a meaningful file is quite another task which hasn't yet be fully addressed unless we talk 5 to (say) 20 letters passwords or allow for unlimited special characters in text files, for instance. Short inputs like passwords are being more and more tabulated by rainbow tables.

What most people don't get is that the odds of a "natural" collision between two _meaningful_ distinct, real-world files (say images) A and B is still extroardinary low. What I say implies we don't put ourselves in a context where we can expect determined opponents, which I understand isn't your case.

Files in 10kb range produce MD5 hashes that noone on Earth can distinguish from 10Mb files or greater. In practice, your result is a random MD5 byte sequence. Cryptanalysis of MD5 estimate the practical number of possible MD5 to be somewhere in the 2¹²⁰ to 2¹²⁷ range. Let's be overly conservative and only estimate the possible number of hashes to be 2¹⁰⁰.

Comparing 100 billion of random files isn't likely to cause a single collision in any reasonable time framework. 2¹⁰⁰ is nothing less than 1,267,650,600,228,229,401,496,703,205,376 which means we still have a very safe margin before the odds of a natural collision occuring tomorrow exceed the odds of the Sun going nova in the same time.

Your situation (comparing contents of image files) boils down to the above, which is called a "birthday attack": accumulate enough real-world data hashes to find a match.

Note that no hash standard is 100% immune to such "spurious collide" event, but the longer the hash is bitwise, the smaller the odds are. Anyway, the 128-bit MD5 hash is still perfectly useable for routine file compare with excellent safety, of course unless a malicious hand can get in the process.

Edit: I fought a long time against unwanted bold type, sorry!

Edited January 24, 2012 by jchd

[Quinch]

Well, that was definitely an educational post. Anyway, I'll check and send again when I get the chance - I'm at work right now, so it's not an option. If it's of consequence, I'm using the built-in _Crypt_HashData UFD for the hashing.