Why is my program faster than the one using a python built in function?

Question

Ok so, I was doing a puzzle on coderbyte, and here is what the puzzle stated:

Have the function SimpleMode(arr) take the array of numbers stored in arr and return the number that appears most frequently (the mode). For example: if arr contains [10, 4, 5, 2, 4] the output should be 4. If there is more than one mode return the one that appeared in the array first (ie. [5, 10, 10, 6, 5] should return 5 because it appeared first). If there is no mode return -1. The array will not be empty.

So here is my program:

import time
from random import randrange

def SimpleMode(arr): 
  bestMode=0
  numTimes=0
  for x in range(len(arr)):
    if len(arr)>0:
      currentNum=arr[0]
      currentMode=0
      while currentNum in arr:
        currentMode+=1
        arr.remove(currentNum)
      if currentMode>numTimes:
        numTimes=currentMode
        bestMode=currentNum
    else: break
  if numTimes==1: bestMode=-1
  return bestMode

start_time = time.time()
numbers = [randrange(1,10) for x in range(0, 1000)]
print(SimpleMode(numbers))
print("--- %s seconds ---" % (time.time() - start_time))

And here is a much simpler program which someone else wrote:

import time
from random import randrange

def SimpleMode(arr): 

  best = -1
  best_count = 1

  for c in arr:
    if arr.count(c) > best_count:
      best = c
      best_count = arr.count(c)

  return best

start_time = time.time()
numbers = [randrange(1,10) for x in range(0, 1000)]
print(SimpleMode(numbers))
print("--- %s seconds ---" % (time.time() - start_time))

Now I know that using my method of timing this it depends on what my CPU is doing and whatnot so this is not the most accurate way, but leaving that aside what I found was that my computer took 0.012000 seconds to run my program, yet it took 0.025001 seconds to run the second program.

Now here is where I am puzzled. My program which I have written myself takes less than half the time the other program takes which uses a built-in python function and has only one for-loop whereas my program has a while loop inside a for-loop.

Can anyone provide any insight into this?

Just because something uses a built in function doesn't mean it'll be faster if it uses a poorer algorithm. — Amber
– Amber, Commented Jul 9, 2015 at 4:00
As a first guess, your loop takes less iterations, because you remove the elements that are already counted, thus len(arr) > 0 will likely be true before you've iterated through the complete array. The second algorithm iterates through the full array no matter what, so depending on the array, one algorithm can beat the other way. Have you tried with an array like [1, 2, 3, 4, 5, 6, ...]? — user707650
– user707650, Commented Jul 9, 2015 at 4:03
@Evert Yes, the original list I used was numbers = [x for x in range(0, 1000)] and the result was the same. — ChillBruh
– ChillBruh, Commented Jul 9, 2015 at 4:05

Max Noel · Accepted Answer · 2015-07-09 04:15:08Z

4

The second program calls count twice each iteration, and since count is O(n) (that is, it has to walk through the entire array, just like a for loop would), the time quickly adds up.

That said, your program can be reduced even further:

import collections

def SimpleMode(arr):
    if not arr:
        return -1
    counts = collections.Counter(arr)
    return max(counts, key=lambda k: (counts[k], -arr.index(k)))

In addition, note that your initial program mutates its input (it effectively destroys the list you pass it because of the .remove calls, which will suck if you wanted to do anything with arr after calling SimpleMode).

And finally, in Python the [1, 2, 3, 4] construct is called a list, not an array. There exists something called an array in Python, and it's not this (most of the time it's a NumPy array, but it can also be an array from the array module in the stdlib).

edited Jul 9, 2015 at 4:15

answered Jul 9, 2015 at 4:05

Max Noel

8,9301 gold badge29 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ChillBruh Over a year ago

Oh I see. He could have just calculated count(c) once in the for-loop, set it to a variable, and then used the variable. Thanks! Also not sure how lambda works but I will look into it.

Max Noel Over a year ago

Lambdas are just anonymous functions. The trick to my program is in how the key argument to max works (which is the same as sort's -- look into docs.python.org/2/library/stdtypes.html#mutable-sequence-types)

ChillBruh Over a year ago

Yeah I know it is called a list, it is just that coderbyte.com offers the challenges in six different languages and in most of the languages it is called an array. Although it will probably be helpful to others.

dlask · Accepted Answer · 2015-07-09 04:03:07Z

0

Your code makes everything in a single pass.
The other code contains hidden nested loops in the arr.count().

answered Jul 9, 2015 at 4:03

dlask

9,0421 gold badge29 silver badges31 bronze badges

1 Comment

Simon Over a year ago

It seems to me that the OP's code also includes hidden loops in currentNum in arr and in arr.remove() but the arr.remove() is making the list about 100 items shorter each time through, which is perhaps having the greater effect.

Collectives™ on Stack Overflow

Why is my program faster than the one using a python built in function?

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related