What is the fastest way to check that 2 collection...

# getting-started

[Konstantin Petrukhnov]

What is the fastest way to check that 2 collections (lists with possible duplicates) have same content?
1. two containsAll calls
2. intersect and check size to each set
3. union and check size to each set
4. union size same as intersect size
5. anything else?

[Konstantin Petrukhnov]

Lists are 1-10 elements big.

[Konstantin Petrukhnov]

Currently doing two containsAll calls. Is there way to make it at least 10% faster?

[marstran]

Only 10 elements? Then this seems like premature optimization.

[marstran]

Anyway, do they also need to contain the same amount of copies of a duplicate?

[Sergey Morgunov]

Time for JMH 😂

[Konstantin Petrukhnov]

yes, same amount of copies for duplicates

[Konstantin Petrukhnov]

performance important on ios only, and number of calls to that part of code could be 10K/s (after the hash)

[Konstantin Petrukhnov]

if there is something similar to jmh on ios, i would be glad to know 🙂

[Konstantin Petrukhnov]

actually there is kotlinx-benchmark

[Konstantin Petrukhnov]

i'll try it

[spand]

Do they need to have the same amount of duplicates ?

[spand]

If yes: You can do it in O(n log(n)) by sorting both and comparing the lists

[Konstantin Petrukhnov]

You are absolutely correct. Sorting and comparing one by one from both lists would be faster. Thank you!

[bezrukov]

Fyi two containsAll even don't work - false positive for [a,b,b] and [a,a,b]

[marstran]

In fact, none of the options work except for the sort/compare option, due to duplicate handling.

[karelpeeters]

Another option to maybe is try is convert both to a bag, a Map<T, Int> and compare those for equality, which should be O(n) in total I think. Probably not worth it for 10 elements.

[vinny2020]

I don’t undertand the use case, are you trying to remove duplicates for each list or both lists combined ?

[Konstantin Petrukhnov]

It is part of .equals(). I'm not trying to modify collections.