python - 如何优化 100000 次迭代的 python 循环？

Question

我是 python 的新手，我正在尝试编写一个函数，其描述如下: 我有一个整数列表。从这个列表中，我必须找到频率最高的项目并将其打印出来。 这看起来很简单，除非我有一个限制，即函数必须在 10 秒内完成执行并且应该消耗内存<512 MB。对于较短的列表长度，我的函数工作正常，但对于长度为 100000 的列表，它会失败。我无法优化代码。 我有 2 个相同的实现:

实现#1

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

实现#2

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

例如

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

在这里不能使用 NumPy。 (不能使用外包)

Answer 1

最简单(并且相当快)的可能是内置的 Counter:

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

this article 中给出了一种更快的方法(不使用额外内存，但会破坏原始数组) ，复制在这里:

# 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 

(此代码的部分内容可以替换为性能更高的替代项，特别是使用 max 函数而不是第二个循环。)