https://kotlinlang.org logo
Title
k

Konstantin Petrukhnov

11/08/2019, 12:03 PM
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?
Lists are 1-10 elements big.
Currently doing two containsAll calls. Is there way to make it at least 10% faster?
m

marstran

11/08/2019, 12:05 PM
Only 10 elements? Then this seems like premature optimization.
👍 1
Anyway, do they also need to contain the same amount of copies of a duplicate?
s

Sergey Morgunov

11/08/2019, 12:07 PM
Time for JMH 😂
k

Konstantin Petrukhnov

11/08/2019, 12:11 PM
yes, same amount of copies for duplicates
performance important on ios only, and number of calls to that part of code could be 10K/s (after the hash)
if there is something similar to jmh on ios, i would be glad to know 🙂
actually there is kotlinx-benchmark
i'll try it
s

spand

11/08/2019, 12:17 PM
Do they need to have the same amount of duplicates ?
If yes: You can do it in O(n log(n)) by sorting both and comparing the lists
👍 4
k

Konstantin Petrukhnov

11/08/2019, 12:55 PM
You are absolutely correct. Sorting and comparing one by one from both lists would be faster. Thank you!
b

bezrukov

11/08/2019, 2:51 PM
Fyi two containsAll even don't work - false positive for [a,b,b] and [a,a,b]
m

marstran

11/08/2019, 3:19 PM
In fact, none of the options work except for the sort/compare option, due to duplicate handling.
k

karelpeeters

11/08/2019, 4:06 PM
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.
v

vinny2020

11/18/2019, 5:53 PM
I don’t undertand the use case, are you trying to remove duplicates for each list or both lists combined ?
k

Konstantin Petrukhnov

11/19/2019, 5:03 AM
It is part of .equals(). I'm not trying to modify collections.