大きな入力を処理し、実行時の複雑さを改善する方法は？

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

@galaxymanで示されているnumpyarrayまたはpandasdataframeに入ることなく、多くの基本的な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ブロックで囲み、最初の初期化を行います。私はあなたにこれらすべてのものをGoogleに提案します。 GL。その最終行はジェネレータですが、リスト内包表記もチェックする必要があります。

Answer 2

改善する方法はありますか？あなたが喜んで尋ねました。ほとんどの場合、適切なデータ型を使用することで、ループ内のO（N）操作を回避できます。そうすれば、誤って二次O（N^2）コードを書くことを避けることができます。ここでは、array/listからdictに移動することを意味します。

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は動的に型指定されているので、ループが変数を反復処理するたびに、返される変数の型（int、stringなど）を判断する必要があります。 cythonを使用して変数の型を設定すると、速度が大幅に向上します。