Mode Calculator

Question

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 (i.e. [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.

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))

I also realize I can use other programs, but I am just looking for a way to optimize this one.

Answer 1

You have many violations of PEP 8, which specifies four-space indentation, a preference for snake_case(), and a space before and after operators like >.

The loop…

for x in range(len(arr)):
  if len(arr)>0:
    # Code that does not involve x and removes some elements from arr
  else: break

… would be better written as…

while arr:
    # Code that removes some elements from arr

The function has a side-effect of trashing the array contents as it works, which is surprising and undesirable.

SimpleMode([]) returns 0. By my interpretation of the specs, it should return -1.

Your algorithm is approximately O(n³), which is rather slow. The nested loop makes it O(n²), and the .remove() calls slow it down by a factor of n, since removing elements from the middle of an array requires a lot of copying to fill in the gap.

---

If the problem had not specified that ties had to be resolved in favour of the element that appears first, the solution would be easy:

from collections import Counter

def simple_mode(arr):
    return Counter(arr).most_common(1)[0]

Alas, Counter.most_common() makes no guarantee of the order, so we have to write some more code. Fortunately, Python's sorted() function guarantees stable sorting.

def simple_mode(arr):
    if not arr:
        return -1
    count = Counter(arr)
    mode = sorted(arr, key=lambda a: -count[a])[0]
    return mode if count[mode] > 1 else -1

The call to sorted() dominates the processing time, making this implementation O(n log n).

Answer 2

Your code looks nice, but there's a few things that could be improved:

• arr: you shouldn't sacrifice readability for two characters: array.
• bestMode, numTimes: these and other similarly named variables should follow snake_case format instead of camelCase format.
• bestMode=0: you should have space between your binary operators: bestMode = 0.
• if len(arr)>0:: same as above: if len(array) > 0:

• if numTimes==1: bestMode=-1: that's not good formatting, they should be on individual lines and whitespace added inbetween the binary operators:

  if num_times == 1:
      best_mode = -1
  

• randrange(1,10): you should have a single space after commas: randrange(1, 10)

• for c in arr:: rather than calling the array item c; you should name it item instead.
  Made redundant by Edit Revision #3.

Answer 3

Your solution to the problem is about loops, indexes and array operations. It is very far from the actual definition of mode. I suggest that you use the built-in higher-order functions to achieve a clearer definition:

def mode(array):
    return max(array, key=array.count)

You can read the above as:

Define the mode of an array as the item that has the max count in the array (aka: the most common).

Answer 4

Style suggestions (based on PEP 8, the Python style guide):

• Use snake_case instead of camelCase;
• Four tabs per indentation level, not two;
• Spaces around binary operators (e.g. x = 1 instead of x=1);
• Your function doesn’t have any docstrings or comments;
• Spaces after commas (e.g. randrange(1, 10) instead of randrange(1,10)).

Some more general comments:

• Use more descriptive variable names: don’t skimp on characters (e.g. array instead of arr), and use consistent naming schemes (e.g. best_mode/best_count /current_mode/current_count instead of the current selection. In particular, using a Mode suffix for two different concepts is just confusing).

• In Python, an underscore is often used to denote variables whose value is unused (for example, the index variable in a for loop). So instead of writing for x in range(len(array)): you could use for _ in range(len(array)) instead.

  You can do the same with the list comprehension at the end of the script.

  Also, you don’t say if you’re using Python 2 or 3, but if you’re using Python 2 then you should use xrange().

• if len(array) > 0 can be rewritten as if len(array) can be rewritten as if array:.

  The last one is the most idiomatic Python.

• We can actually go one better: rather than looping up to the array’s length, but checking on every step to see if the array still exists, we can use a while loop:

  while array:
      current_mode = array[0]
      # do some stuff
      # remove all instances of current_mode from array
  

  That will exit the loop as soon as the array is exhausted, saving you a check and indentation level.

• To save yourself a line, you could go straight to currentMode with count():

  current_mode = array[0]
  current_count = array.count(current_mode)
  for _ in range(current_count):
      array.remove(current_mode)
  

  Note that the new variable names also make the next block of code a little nicer (at least, I think so):

  if current_count > best_count:
      best_mode = current_mode
      best_count = current_count
  

  It’s a lot easier to see why you’re making that assignment.

• Indent the body of if num_times == 1 to make it easier to read.

  Also, I would make the body of this statement simply return -1. It achieves the same effect, but avoids a potentially confusing line. The best mode of this array isn’t –1; that’s just a special value we return to indicate that. So why are we sticking it in the best_mode variable?

  Perhaps it’s just semantics and I’m getting cranky, but that’s what I’d prefer.

• In the final line, you should use .format() instead of %-tokens, which is the preferred method for new Python code. That is:

  print("--- {} seconds —".format(time.time() - start_time))
  

Answer 5

Algorithm

The time complexity of your algorithm looks cubic:

• for each element...
• scan the array for a duplicate
  • if found one, remove a duplicate (+1 scan)
  • repeat search + remove

When in fact you could do this in linear time, though at the cost of the extra storage of a dictionary for the counts:

• for each element
• if in the dictionary, increment count, else set count to 1
• if the new count is greater than the current best, record the count and record the number

Although this algorithm needs extra storage for the dictionary, it has the advantage of not modifying the original array, which is cleaner.

Misused for-loop

The for loop is misused:

• when you don't need the loop index (variable x unused in your example), consider other alternatives
• the logic you implemented is not so much about the number of initial elements, but the key is to keep looping as long as the array is not empty

In other words, an equivalent but simpler way to write your main loop:

while arr:
    currentNum = arr[0]
    # ...

Unnecessary statement

There is an unnecessary statement in the while-loop here:

  currentNum=arr[0]
  currentMode=0
  while currentNum in arr:
    currentMode+=1
    arr.remove(currentNum)

The loop condition is always true for the first time. It would be better to redactor this part in a way that there are no unnecessary operations.