2
$\begingroup$

Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so there are no two arrays that have the same sequence of bytes). What would be the best option to check this condition?

From my point of view, there are several approaches available for this problem (the examples provided below are relevant for Go programming language ecosystem):

Compare hash sums

Take some fast non-cryptographic hash (like murmur3) and compute hash sum from the every array. Store every sum in a set and find duplicates. Provided that hash is O(N), the whole operation should be O(M*N):

func unique(arrays [][]byte) bool {
   set := newSet()
   for _, array := range arrays {
       sum := hash(array)
       dump := hex(sum)
       if set.contains(dump) {
            return false
       }
       set.add(dump)
   }
   return true
}

Compare arrays bytewise

In Go there is [bytes.Equal][2] function written in pure assembly which can utilize platform-dependent optimizations. So it's possible to iterate over the arrays and check equality pairwise for O(M^2*N):

func unique(arrays [][]byte) bool {
    for i := 0; i < len(arrays); i++ {
        for j := i + 1; j < len(arrays); j++ {
            if result := bytes.Equal(arrays[i], arrays[j]); result {
                return false
            }
        }
    }
    return true
}

Despite the fact that this algorithm has worse computational complexity, it may run faster due to above-mentioned optimizations.

String(?) algorithm

  1. Take ith byte from every array
  2. Compare bytes;
  3. If all are unique, return true;
  4. If there are repeating values, repeat step #1 for (i+1)th bytes for only those arrays which had equal ith bytes.

This should be also O(M*N), because in the worst case one would have to completely compare all arrays. But it seems like this approach will bring too much overhead (I mean state of algorithm between iterations etc.)

Please share your opinion about the optimal way to solve this problem.

$\endgroup$
  • 1
    $\begingroup$ Have you considered sorting array? Time is N log N, and checking for duplicated entry could be done in comparator or in linear time afterwards. $\endgroup$ – Evil Oct 26 '18 at 11:51
  • 1
    $\begingroup$ @Evil: M log M comparisons for M arrays. But a comparison of two arrays can take N steps in the worst case, so worst case MNlog M $\endgroup$ – gnasher729 Oct 26 '18 at 21:24
2
$\begingroup$

You need to read all items in the worst case. Assume you have written some algorithm which reads items in any order and processes them with any amount of cleverness. And I'm your opponent and try to make you read as many items as possible.

Here's what I do: Whenever your algorithm reads an item I store an "X" just before you read it. I do that except when you have read one array completely, which consists of all X, and you are reading the last item of another array, in which case I store a value that makes this row different from all other rows that were read completely. When you read the very last item, I can decide to store a value that makes all arrays unique, or I store another X and you have two arrays that are identical.

Whatever you do, until you read the very last item you don't know whether two arrays are identical or all arrays are unique.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.