Help with an algorithm!

[Ivan Kazmenko via Digitalmars-d-learn]

On Thursday, 15 June 2017 at 06:06:01 UTC, MGW wrote:
> There are two arrays of string [] mas1, mas2; Size of each 
> about 5M lines. By the size they different, but lines in both 
> match for 95%. It is necessary to find all lines in an array of 
> mas2 which differ from mas1. The principal criterion - speed. 
> There are the 8th core processor and it is good to involve a 
> multithreading.

The approaches which come to mind are:

1. Sort both arrays, then traverse them in sorted order, like in 
merge step of merge sort:

     sort (mas1);
     sort (mas2);

     size_t index1 = 0;
     foreach (str2; mas2)
     {
         while (index1 < mas1.length && mas1[index1] < str2)
             index1 += 1;
         if (mas1[index1] != str2)
             writeln (str2);
     }

Sorting takes O (n log n * c) time, where n is the size of the 
arrays, and c is the expected time of two strings comparison when 
sorting.  The subsequent step is O (n * c) which is faster than 
sorting.

2. Hashing.  Just put the contents of the first array into a bool 
[string], and then, for each string from the second array, check 
whether it is contained in the associative array.  The time will 
be O (total length of all strings) multiplied by a moderate 
constant, unless the strings are designed specifically to 
generate hash collisions, in which case it will be slower.

3. Trie.  Similar to hashing, but the constant multipliers will 
be much higher unless the strings have large common prefixes.

Whether we can do faster depends on context.  For example, if the 
strings tend to all have long common prefixes, any string 
comparison will be slow, but otherwise it can be thought of as 
taking constant time.

Ivan Kazmenko.