How does 'unique' work under the hood (in general terms)

I am just curious as to how this function works by default, under the hood.

I know that a couple of ways of implementing unique manually is to copy over the elements from one array into a hash table or a binary search tree.

Given that the default implementation of 'unique' also sorts the elements, I would guess that it maybe copies over the elements into a binary search tree.

As a result, if I need to both sort and remove duplicate elements/rows from an array I would only need to call 'unique' instead of sort(unique(...)) or sortrows(unique(...), ...)?

[Rik]

Without opening up the function, there are only two ways to tell:

1. Reading the documentation
2. Executing several examples

What you describe seems to be correct, so I don't really understand what your question is.

Two notes:

1. The unique function didn't always sort the output. I don't have local installs old enough right now. The online R2017a doc mentions sorting as the default.
2. Unique doesn't accept all data types. I created a wrapper for unique that does accept all datatypes (or at least, most of them). It uses ComputeNonCryptHash to hash all elements and then calls unique on that cellstr. It's not nearly as polished as the things I would normally publish, but I attached it just in case you need something like this.

help unique_array

 Extend unique to work on most array types. By default it takes a shortcut by comparing hashes.
 It is equivalent to [C,ia]=unique(A,'stable') for supported datatypes.
 
 syntax:
  [C,ia]=unique(A)
  [C,ia]=unique(A,exact)
      where C=A(ia)
 
  If exact is false (the default), a hash of the element is used to take a shortcut. If computation
  of the hash fails, the exact comparison will be performed as a fallback.

[Erik Johannes Loo]

Thank you for the file - it could come in handy. I was asking in case someone did in fact know how TheMathWorks implemented the function, out of curiosity. It seems that for the 'sorted' case they probably use sort followed by diff.

What is interesting is that using hash should in theory have a smaller run-time complexity, of O(n) instead of O(n log n), and it would also preserve the order which might be the expected default behaviour by most MATLAB users.

[Rik]

Those who know can't tell, those who can tell don't know. You could try to dig in the source code, but you can't do anything with that knowledge.

I would be very hesitant to apply a big O notation on my function. I rolled my own hashing algorithm. You should be deeply, DEEPLY, mistrustful of me. It works for what I do with it: confirm my test functions return the same output. I only use this unique_array function if I'm there to catch any strange errors.

I suspect the unique function will run different code when it is called with the 'stable' flag. Mathworks employs smart people, who're probably aware of this trade-off.

Answer 1

[Bruno Luong]

If I have to implement unique, I would implemented by sorting the find the difference similar to this

a=randi(10,1,100);
% u is unique of a
s=sort(a);
j=[true,diff(s)~=0];
u=s(j)

Working with contiguous array if much more efficient than binary search and hash function. But TMW doesn't not document how unique works.

[Erik Johannes Loo]

Thanks for your reply. The fact that TMW does not disclose how 'unique' works explains why I wasn't able to find anything before.

In my mind I can see that the runtime complexity would be the same for your approach and the binary search approach O(n log n) - dominated by either the sort function or the BST insert function, but I have in fact noticed that working with arrays is much faster and can be done allocating minimal additional memory (the boolean j array).

Answer 2

[Walter Roberson]

unique() does a sort() and then checks where adjacent elements are different.

You can read the code; it is a .m file.