CODEWITHSUNDEEP
pythonpython-3.xoptimization
noobi
noobi

Reputation: 97

How to optimize python loop for 100000 iterations?

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)

Upvotes: 2

Views: 3864

Answers (6)

kutschkem
kutschkem

Reputation: 8163

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

Upvotes: 3

Sayandip Dutta
Sayandip Dutta

Reputation: 15872

What about this?:

max(ar.count(i) for i in ar)

Or this?:

max(map(ar.count,ar))

Upvotes: 0

Amadan
Amadan

Reputation: 198324

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

Upvotes: 4

AnswerSeeker
AnswerSeeker

Reputation: 298

Returns most frequently occurring value in list

max(set(ar), key=ar.count)

Upvotes: 1

sam
sam

Reputation: 1896

Hope this helps!

We are using Python's High-Performance container datatypes(Counter)

from collections import Counter

def returnMaxFrequency(ar):
    return max(Counter(t).values())

Counter does a frequency mapping of your number and created a dict, once dict is created you are using a max to get max-freq of the list.

Using Dict is an efficient way of generating a frequency count, unless your are going for distributed compute solutions

Note: collections is a python in-built package i.e. comes with setup. Not an external library.

Upvotes: 3

Aryerez
Aryerez

Reputation: 3495

The second implement is nice, but inside the dict-comprehension change ar to set(ar), and it will check every item only once:

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

Upvotes: 0

Related Questions