如何处理大量输入并提高运行时复杂度？

Question

我有以下的功能，即旨在恢复最佳的平均成绩。 它需要输入等：

scores = [["bob",100],["bob",100],["toto",100],["frank",100]] 

如何改进它，因此它在设定的时间内处理大量的投入？那就是说如何让运行时更加复杂？

编辑：它应该处理负分数和分数空。

def maxavg(scores): 
    avs=[] 
    namelist=[] 
    for i in range(0,len(scores)): 
     name = scores[i][0] 
     if name not in namelist: 
      namelist.append(name) 
      note = scores[i][1] 
      nbnotes = 1 
      for j in range(i+1,len(scores)): 
       if scores[j][0]==name: 
        nbnotes+=1 
        note+=scores[j][1] 
      avs.append(note/nbnotes) 
    return max(avs) 

Answer 1

不用进入numpyarray或pandasdataframe由@galaxyman显示，你错过了许多基本的Python东西。你需要得到的东西像dictionaries熟悉。下面是使用分配给一个不存在的键时初始化为0 defaultdict一个例子：

from collections import defaultdict 
def maxavg(scores); 
    scoredict = defaultdict(int) 
    namecount = defaultdict(int) 
    for name,grade in scores: 
     scoredict[name] += grade 
     namecount[name] += 1 
    retrun max((scoredict[name]/namecount[name] for name in scoredict)) 

定期字典，mydict = {}将无法​​在指定mydict['somename'] += grade的第一次尝试，因为+=假设现有的密钥。所述defaultdict构建体包围这样的问题与tryexcept块，使第一初始化。我建议你谷歌所有这些东西。 GL。这最后一行是一台发电机，但你应该检查列表理解为好。

Answer 2

如何改进？很高兴你问。大多数情况下，这是使用适当的数据类型的问题，它可以避免循环中的O（N）操作。这样可以避免意外写入二次O（N^2）代码。在这里，它意味着从数组/列表移动到字典。

的for i in range(0,len(scores))环是非常好的Fortran语言，但我们必须使用Python的成语，而不是一个机会：

for name, score in scores: 

的if name not in namelist测试隐藏着一个线性扫描，O（N），你的循环中。通过使用字典，我们可以避免这种情况。此外，“这个名字是否已经存在？”的测试可埋在defaultdict：

total = collections.defaultdict(int) 
n = collections.defaultdict(int) 
for name, score in scores: 
    total[name] += score 
    n[name] += 1 
avg = {name, total[name]/n[name] 
     for name in scores} 
return max(avg.values()) 

Answer 3

它可能会快比你的代码和较少的代码行

scores = [["bob",100],["bob",90],["toto",70],["frank",100]] 
df = pd.DataFrame(scores,columns=['name', 'scores']) 
print df.groupby('name').mean().idxmax() 

输出：

scores frank 

Answer 4

您可以通过铸造您的变量改善你的运行使用cython的类型。 This link是一个很好的介绍。

因为Python是动态类型，每一次循环迭代变量应确定返回什么类型的变量（整型，字符串，等等）。使用cython设置变量类型可以显着提高速度。