Python代碼優化性能

Question

假設歌曲i已播放f_我倍但齊普夫定律預言，它將 已播放z_我倍。然後你去網絡連接NE歌曲i的質量要q_我 = f_我/z_我 。你的軟件應與q_我最高值選擇歌曲。

輸入的第一個行包含兩個整數n和m（1 <= n < 50 000，1 <= m <= n），對專輯歌曲的數量，和歌曲選擇數字。然後按照n行。所述i「日這些線包含一個整數f_我和串s_我，其中0 <= f_我< 10^12 是次數i」個歌曲被收聽，和s_我是名稱這首歌。 每首歌曲名稱長度不超過30個字符，僅由字符a-z，0-9和下劃線（_）組成。

以質量遞減的順序輸出最高質量的m首歌曲的列表q _i。如果兩首歌曲具有相同的質量，優先考慮專輯中第一首出現的歌曲（推測製片人有理由將該歌曲放在另一首歌曲之前）。

sample input 
4 2 
30 one 
30 two 
15 three 
25 four 


sample output 
four 
two 

我很新的蟒蛇，我試圖解決這個難題，我認爲我得到正確的答案，但我必須做得更快，任何建議？

from __future__ import division 

def main(): 
    import sys 
    from operator import itemgetter 

    data = sys.stdin.readlines() 
    line1 = data[0].split(" ") 
    numberofselect = line1[1] 

    qualitydict = {}; 
    songdict = {}; 
    a = 0 

    for x in range(1, len(data)): 
     item = data[x].split(" "); 
     item1 = item[1].split("\n"); 
     f = float(item[0]) 
     z = float(1/x) 
     qualitydict[item1[0]] = (f/z) 
     if ((f/z) in songdict.keys()): 
      songdict[(f/z)].append(item1[0]) 
     else: 
      songdict[(f/z)] = [item1[0]] 

    items = songdict.items() 
    items.sort(key = itemgetter(0), reverse=True) 

    for key, value in items: 
      for element in value: 
       if (a < int(numberofselect)): 
        print element 
        a = a + 1 

main(); 

Answer 1

你可以做很多的改進，無論是在可讀性和性能[沒有測試過]：

from __future__ import division 
import sys 
from operator import itemgetter 
from collections import defaultdict 

def main(): 

    line1 = sys.stdin.readline().split(" ") 
    numberofselect = int(line1[1]) 

    qualitydict = {} 
    songdict = defaultdict(list) 

    for x, line in enumerate(sys.stdin, start=1): 
     tokens = line.split() 
     val = float(tokens[0]) * x 
     qualitydict[tokens[1]] = val 
     songdict[val].append(tokens[1]) 

    items = songdict.items() 
    items.sort(key=itemgetter(0), reverse=True) 
    a = 0 
    for key, value in items: 
      for element in value: 
       if a < numberofselect: 
        print element 
        a += 1 

main() 

特別是：

• 使用songdict一個defaultdict。如果密鑰不存在，它將自動創建一個新的list值。另外：請勿使用key in your_dict.keys()來查看密鑰是否在字典中，因爲該校驗是O(n)。使用key in your_dict這需要O(1)時間。請注意，使用defaultdict您根本不必進行檢查，它已經爲您完成了。

• 您正在定義z爲1/x，然後你做f/z，但這是一樣的做f * x，唯一的區別是，後者會更精確（x是一個整數，這樣1/x會損失一些精度）。

• 我想知道是否有必要使用op.itemgetter(0)對物品進行分類。我的意思是，這些元素是元組，所以它們將首先按第一個鍵排序，然後再按第二個鍵排序，結果將是按照質量和按字母順序排列的歌曲（當質量相同時，多於一個歌曲）。請注意，儘管您可能認爲使用op.itemgetter(0)進行排序會更快，但我認爲這不一定是正確的，因爲您爲每個元素添加了函數調用，並且python必須使用一些空間來保留鍵值。

事實上，如果我們檢查的時機：

>>> timeit.timeit('L.sort()', 'import random;L = [(random.randint(0, 100), i) for i in range(3000)]', number=10000) 
1.3252038955688477 
>>> timeit.timeit('L.sort(key=operator.itemgetter(0))', 'import random;import operator;L = [(random.randint(0, 100), i) for i in range(3000)]', number=10000) 
2.926893949508667 

增加對itemgetter版本的性能提高了尺寸，但你必須仔細檢查此時它變得更好，因爲即使與50000元素：

>>> timeit.timeit('L.sort()', 'import random;L = [(random.randint(0, 1000), i) for i in range(50000)]', number=1000) 
13.771193027496338 
>>> timeit.timeit('L.sort(key=operator.itemgetter(0))', 'import random;import operator;L = [(random.randint(0, 1000), i) for i in range(50000)]', number=1000) 
21.419496059417725 

• line.split()不帶參數的小號在任何空白處切分。

例如：

>>> 'A string with some space,\ttabs and \n\n newlines'.split() 
['A', 'string', 'with', 'some', 'space,', 'tabs', 'and', 'newlines'] 

這是相當不同：

>>> 'A string with some space,\ttabs and \n\n newlines'.split(' ') 
['A', 'string', 'with', '', '', 'some', '', '', '', 'space,\ttabs', 'and', '\n\n', 'newlines']