python - 优化 python 代码以提高性能

Question

假设那首歌 i已播放f _i 次，但 Zipf 定律预测它会玩过z _i 次。然后定义歌曲的质量 i成为q _我 = f _我/z <子>我 .你的软件应该选择最高值为q的歌曲_我。

第一行输入包含两个整数n和 m ( 1 <= n < 50 000 , 1 <= m <= n )，专辑中歌曲的数量，以及要选择的歌曲数量。然后关注n线。 i第 'th 这些行包含一个整数 f _i 和字符串 s _i，其中0 <= f _我 < 10^12是 i 的次数听了这首歌，s _i 是歌曲的名称。每首歌曲名称最多 30 个字符，且仅由字符 a-z 组成, 0-9 , 和下划线 ( _ )。

输出质量最高的m首歌曲列表q _i，按质量降序排列。如果两首歌的质量相同，则优先考虑专辑中首先出现的歌曲(大概是制作人将这首歌放在另一首之前的原因)。

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


sample output
four
two

我是 python 的新手，我正在尝试解决这个难题，我认为我得到了正确的答案，但我必须更快地完成，有什么建议吗？

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']