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

Question

Erik Johannes Loo 2022-2-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1649495-how-does-unique-work-under-the-hood-in-general-terms

回答： Walter Roberson 2022-2-14

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(...), ...)?

3 个评论
显示 1更早的评论隐藏 1更早的评论

Rik 2022-2-14

在 MATLAB Online 中打开

unique_array.m

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

Reading the documentation
Executing several examples

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

Two notes:

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.
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 2022-2-14

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 2022-2-14

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 2022-2-14

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1649495-how-does-unique-work-under-the-hood-in-general-terms#answer_895685

编辑：Bruno Luong 2022-2-14

在 MATLAB Online 中打开

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Erik Johannes Loo 2022-2-14

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).

请先登录，再进行评论。