How to optimize python loop for 100000 iterations?

Question

I'm new to python and I'm trying to write a function whose description is as follows: I have a list of integers. From this list I have to find the item with max frequency and print that. This seems pretty straight forward unless I have a limitation that the function must complete the execution within 10 sec and should consume memory < 512 MB. For shorter list length my function works fine but for a list of length 100000 it tanks. I'm not able to optimize the code. I have 2 implementations for the same:

Implementation #1

def returnMaxFrequency(ar):
    freqList = []
    for val in ar:
        freq = ar.count(val)
        freqList.append(freq)
    return(max(freqList))

Implementation #2

def returnMaxFrequency(ar):   
    freqDict = {x:ar.count(x) for x in ar}   
    maxFreq = max(freqDict.values())
    return maxFreq

Eg

if ar = [3 2 1 3]
o/p: 2

Using NumPy is not an option here. (Can't use external package)

Answer 1

Easiest (and reasonably fast) is likely the built-in Counter:

from collections import Counter
winner = Counter(ar).most_common(1)[0]

An even faster method (and using no extra memory, but destroying the original array) is given in this article, replicated here:

# Python program to find the maximum repeating number 

# Returns maximum repeating element in arr[0..n-1]. 
# The array elements are in range from 0 to k-1 
def maxRepeating(arr, n,  k): 

    # Iterate though input array, for every element 
    # arr[i], increment arr[arr[i]%k] by k 
    for i in range(0,  n): 
        arr[arr[i]%k] += k 

    # Find index of the maximum repeating element 
    max = arr[0] 
    result = 0
    for i in range(1, n): 

        if arr[i] > max: 
            max = arr[i] 
            result = i 

    # Uncomment this code to get the original array back 
    #for i in range(0, n): 
    #    arr[i] = arr[i]%k 

    # Return index of the maximum element 
    return result 

(Parts of this code could be replaced by more performant alternates, in particular using the max function instead of the second loop.)

Answer 2

Both of your implementations are basically the same, the second one only uses a list comprehension instead of the for loop. Both algorithms are in O(n^2) because count is in O(n) and you are calling it n times (once for each value).

If you want to optimize, reduce the complexity (to O(n)):

def returnMaxFrequency(ar):   
    freqDict = {x:0 for x in ar}
    for val in ar:
        freqDict[val] = freqDict[val] + 1
    maxFreq = max(freqDict.values())
    return maxFreq