Why is the single cycle function slower than the double cycle?
This question was motivated from another Stack Overflow question - How to improve duplicate algorithm removal?
The requirement asked in the questions was:
we need to return the length of the array that removed the duplicates, but we can leave at most two duplicates.
Example - [1, 1, 1, 2, 2, 3]
, the new array will be [1, 1, 2, 2, 3]
. Thus, the new length will be 5.
The solution as given by the OP is
def removeDuplicates(nums):
if nums is None:
return 0
if len(nums) == 0:
return 0
if len(nums) == 1:
return 1
new_array = {}
for num in nums:
new_array[num] = new_array.get(num, 0) + 1
new_length = 0
for key in new_array:
if new_array[key] > 2:
new_length = new_length + 2
else:
new_length = new_length + new_array[key]
return new_length
I tried to come up with a solution that reduced the number of loops to one loop.
def removeDuplicates1(nums):
if nums is None:
return 0
if len(nums) == 0:
return 0
if len(nums) == 1:
return 1
new_array = {}
length = 0
for num in nums:
n = new_array.get(num, 0)
new_array[num] = n + 1
if n <= 1:
length += 1
return length
After that I tried to find a solution compared to the original solution, I thought my solution should have provided a slight improvement to the original solution, but the result timeit
showed that the original solution was always better (even when the array contains all unique elements). Time taken -
In [3]: l = list(range(1000))
In [4]: %timeit removeDuplicates(l)
1000 loops, best of 3: 390 s per loop
In [5]: %timeit removeDuplicates1(l)
1000 loops, best of 3: 412 s per loop
In [6]: l1 = [1] * 1000
In [7]: %timeit removeDuplicates(l1)
1000 loops, best of 3: 224 s per loop
In [9]: %timeit removeDuplicates1(l1)
1000 loops, best of 3: 304 s per loop
Can anyone please advice on why this is happening? Can I ignore something obvious?
source to share
If the input list is a list (range (x)), which means there are no duplicates, then your code will be faster, but if there are a significant number of duplicates in the input list, then your code will be slower.
I was constantly getting timing with
collections.defaultdict - fastest
original proposal - next fastest (if duplicates)
your single loop proposal - slower, if there are duplicates
collections.counter - slowest
They are all basically the same thing, so they were always close in time.
defaultdict is the fastest as the original sentence basically duplicates it, but defaultdict is part of the core libraries that come with python. I'm guessing "don't reinvent the wheel."
But why is your code slower when it uses one loop? Think that the original code is doing two loops, because there are two different things to iterate over. Iterate over the original list of data once, and then iterate over unique elements (which may be less since duplication is expected).
Your code does everything the original code does, but it does it for every item in the original data list. Think of it as two separate loops with one loop counter for both. You are still looping through all the elements in the original list as you should. But the second loop (which you are trying to get rid of by executing it in the original loop) now has to execute its code for every item in the original dataset.
What did you get from the fact that you lost one cycle from its execution more often, especially for duplicates of the original data.
source to share