How to avoid AppendTo when computing similarities

Question

I need to make the calculation of the HammingDistance for strings faster. The background is that I want to be able to compare the similarity of images of a textual database. (The similarity of two images can be calculated as nicely explained in Efficient way to compare animated images to tell if they are the same). In any event, the database consists of a list of image-names and the corresponding hash-values. While it is possible to store a binary version of the data in the database, I prefer a textual representation e.g. in a text file using IntegerString with a base of 36 to get the shortest textual representation (in terms of digits) of a numeric integer value.

Of course for calculating the HammingDistance I could convert the hashstrings back to numeric values and implement the methods described in Fastest way to measure Hamming distance of integers. However, there are two issues:

• Since a Mathematica-compiled function cannot act on Strings, I need to convert the String to a numeric value. On average the hash-values have around 250 digits in their decimal representation, so I would need to combine the approaches described in Faster binary Hamming weight for big integers? and Fastest way to measure Hamming distance of integers, while
• I am a total newbie regarding compiling and calling external C-functions from Mathematica, so I understand less than half of what Oleksandr R. is doing in both threads, and unfortunately I have not enough reputation to comment in those threads directly.

Therefore, since HammingDistance as it is implemented in Mathematica can evaluate directly Strings I am really wondering if there is not a faster way using some fast C compiled code from within Mathematica. If not I would be also happy with some step-by-step explanation on how to implement the C-code of Oleksandr. R. inside Mathematica.

(I got gcc and Visual Studio 2015 installed and succeeded also with getting Mathematica to recognize the VS compiler as described in C compilation not working with Visual Studio 2013)

Thank you for any suggestions or solutions!

@Marius: For approximately 16000 image-name/hashvalue-pairs the comparison takes on average 36 min. I would like to get the time down to less than a minute, as everything longer is not practicable.

For the comparison process I use a While-Loop I am using for comparing a single image hash with the 16000 hashes from the textual database. Inside the while loop is only the code

    While[j <= Length[FileHashTab], {
      AppendTo[
       vec, {FileHashTab[[j, 1]], 
        If[StringLength@ImgHash == StringLength@FileHashTab[[j, 2]], 
         HammingDistance[ImgHash, FileHashTab[[j, 2]]], 
         Infinity]}];
      j = j + 1;
      }]

with FileHashTab={{ImgName,ImgHash},{...,...},...} vec={}; so vec is used for collecting the filenames with the corresponding hashdistance to the ImgHash of the image I want to compare.

The interesting point is that the memory usage is really small and the CPU (i5 - 4 cores) is only loaded only with about 20%...

Answer 1

Thanks to all of the above comments I finally arrived at a solution for me which is probably not yet the fastest possible but suitable for me. Where I got it wrong was the While posted above that integrated in outer While-loop as I wanted to compare every element of the database with all other elements:

While[i <=Length[FileHashTab], {
j=i+1;
    While[j <= Length[FileHashTab], {
      AppendTo[
      vec, {FileHashTab[[j, 1]], 
        If[StringLength@ImgHash == StringLength@FileHashTab[[j, 2]], 
        HammingDistance[ImgHash, FileHashTab[[j, 2]]], 
         Infinity]}];
      j = j + 1;
      }]
i=i+1;
}]

I found out that the first runs for i are really fast (even for 16000 elements) but as i progresses further the calculation starts to continuously slow down (although it should rather speed up due to decreasing number of elements that are being compared with each other). (Probably due to the Complexity of AppendTo as pointed out by Marius which I wasn't aware of)

Anyway I tried to get rid of the inner While-loop in a way that I make an array of two lists where one contains the all elements of the database (which is a 2dim-Array) from a starting element to the end and the other is a ConstantArray of the hashvalue I want to compare with the rest of the elements. To get everything sorted out properly I defined first some functions:

compIfHammingDist[hashTwoElememtsForDist_List] := 
If[StringLength@hashTwoElememtsForDist[[1]] == StringLength@hashTwoElememtsForDist[[2]], 
HammingDistance[hashTwoElememtsForDist[[1]], hashTwoElememtsForDist[[2]]], Infinity]

ConstructComparisonList[Liste_List, AbElementBisEnde_]:=
Module[{RunningList, ConstantList},
RunningList = Take[Liste, (AbElementBisEnde) - Length[Liste]];
ConstantList =  ConstantArray[Liste[[AbElementBisEnde]], Length[RunningList]];
Transpose[{ConstantList, RunningList}]]

(*remember the FileNameHashTabelle is structured as {{fileName,hashValue},{...,...},...}*)
FileNamesWithHashDist[FileNameHashTabelle_,AbElementBisEnde_] := {       
FileNameHashTabelle[[AbElementBisEnde, 1]],  
    Transpose[{
        Take[Transpose[FileNameHashTabelle][[1]], AbElementBisEnde - Length[FileNameHashTabelle]], 
        compIfHammingDist[#]& /@ ConstructComparisonList[Transpose[FileNameHashTabelle][[2]], AbElementBisEnde]
     }]}

SelectBelowThreshold[MeasuredFileDistValues_, SimilarityThreshold_]:= 
Module[{messung},
   messung = Select[MeasuredFileDistValues[[2]], #[[2]] < SimilarityThreshold &];
   If[Length[messung] != 0, Flatten[{MeasuredFileDistValues[[1]], Transpose[messung][[1]]}],Nothing]
]

The main happens in here where I still use While and AppendTo but not any more in a double loop. Furthermore I apply also at this point the Threshold to keep only sufficiently similar images in order to keep the Memory usage down:

measureImgFileDistanceAndApplyThreshold[FileHashTab_,SimilarityThreshold_]:= 
Module[{ImgNames, HashValues, vec = {}, i = 1},
   PrintTemporary[Monitor[
     While[i <= Length[FileHashTab] - 1, {
       AppendTo[vec, 
       SelectBelowThreshold[FileNamesWithHashDist[FileHashTab, i], SimilarityThreshold]];
     ++i;
     }],
 Row[{ProgressIndicator[i, {1, Length[FileHashTab]}], i}, " "]]];
vec
];

This way it the first calculation take 0.25 s for the whole hashtable on my machine and the further it progresses the faster it gets, so HammingDistance was obviously in spite of the large numbers not at all the limiting factor.