2

I just wanted to check whether there contains any duplicates in my array. I searched on Google and see some approaches:

  • Double for-loop loops though the array and comparing each item
  • Creating a dictionary that stores the number of occurrences of each item

But these methods require a lot of loops and I'm kind of lazy to write a large amount of code just for this functionality. xD.

So I thought of this creative way:

let containsDuplicates = Set(array).count != array.count

However, is this method faster or slower than the other two? I'm not sure because it seems to create a set which I think needs to loop through the array. And I don't know whether accessing the count also loops through the whole array.

If I only have at most 50 items in the array, will this even matter?

Sweeper
  • 213,210
  • 22
  • 193
  • 313
  • 1
    Just try it and measure the time ... – Martin R May 10 '16 at 13:47
  • Try what? I don't know how to measure code execution time. @MartinR And I also want to know _why_, which I don't know how to find the answer of. – Sweeper May 10 '16 at 13:48
  • This is the first Google hit that I found for "Swift measure execution time": http://stackoverflow.com/questions/24755558/measure-elapsed-time-in-swift. Also the answer depends on the array contents, eg How many duplicates does it contain. – Martin R May 10 '16 at 13:55
  • It probably also depends on the element type: how costly is it to compare two array elements? – Martin R May 10 '16 at 14:18

2 Answers2

1

That's pretty much the best way. Dictionary storage is constant time, and each item only needs to be stored once, so it's an O(n) solution, vs the O(n^2) for the double for-loop approach. The space efficiency is lower, but that's usually not a concern these days.

If you're doing this often, I would suggest using some kind of hybrid data structure, so that you're not constantly generating these Sets from scratch.

Alexander
  • 59,041
  • 12
  • 98
  • 151
  • Can you elaborate more on the "hybrid data structure"? It sounds vague. – Sweeper May 10 '16 at 14:02
  • Make your own `struct`/`class` that has `Array` and `Set` properties. Implement the `add`/`remove`/etc. methods to simultaneously `add`/`remove`/etc. from both the `Array` and the `Set`. This way, calling `contains` can just use the existing set, without wasting `O(n)` time to recreate it on every call. – Alexander May 10 '16 at 14:11
0

My first thought was to create a set and to see if the number of elements was different than the array, just like you. Apple will probably have optimized this conversion fairly well and doing it this way makes the code compact and easy to understand.

You don't mention what the array is for and how it's used but could you just use a set instead of the array so that duplicates don't get added in the first place? Or if you need to keep track of how many but still need to know the unique values easily then create a new class that uses a dictionary for the storage. The key is what you are storing in the array but would be unique and the value would be the count.

CanadianMacFan
  • 146
  • 4