2

假设这首歌i已经播放了fi次，但 Zipf 定律预测它会播放zi次。然后你定义歌曲的质量为ii q= i f/ i z。你的软件应该选择qi 值最高的歌曲。

输入的第一行包含两个整数n和m( 1 <= n < 50 000, 1 <= m <= n)，专辑中歌曲的数量，以及要选择的歌曲数量。然后按照n线路。这些行中的第i' 行包含一个整数fi和字符串si，其中0 <= fi< 10^12 是第i' 首歌曲被收听的次数，而si是歌曲的名称。每首歌曲名称最长为 30 个字符，并且仅包含字符a-z、0-9和下划线 ( _)。

输出质量最高的 m 首歌曲的列表qi，按质量降序排列。如果两首歌曲质量相同，则优先考虑专辑中最先出现的那首（大概制作人有理由将那首歌曲放在另一首之前）。

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();
4

1 回答 1

3

您可以在可读性和性能方面进行许多改进[未测试]：

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()

尤其：

  • 使用一个defaultdictfor songdict。list如果键不存在，它将自动创建一个新值。另外：不要key in your_dict.keys()用于查看键是否在字典中，因为该检查是O(n). 使用key in your_dict需要O(1)时间。请注意，使用 adefaultdict您根本不必进行检查，它已经为您完成了。

  • 你定义zas1/x然后你 do f/z，但这和 do 是一样的f * x，唯一的区别是后者会更精确（x是一个整数，所以do1/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']
于 2012-12-28T07:51:14.303 回答