2

その曲がii回再生されたが、Zipf の法則ではi回再生されたであろうと予測されているとします。次に、曲の品質をi = i / iと 定義します。ソフトウェアは、iの値が最も高い曲を選択する必要があります。fziqfzq

入力の最初の行には、2 つの整数nとm( 1 <= n < 50 000, 1 <= m <= n)、アルバムの曲数、および選択する曲数が含まれます。次に、n行に従います。これらの行のi'th には、整数fiと文字列siが含まれます。ここで、0 <= fiは'th の曲が聴かれ< 10^12 た回数であり、 iは曲の名前です。各曲名の長さは最大 30 文字で、文字、、およびアンダースコア ( ) のみで構成されます。isa-z0-9_

最高の品質qiを持つ m 曲のリストを、品質の降順で出力します。2 つの曲が同じ品質である場合は、アルバムの最初に表示されている曲を優先します (おそらく、プロデューサーがその曲を他の曲よりも前に置く理由があったと思われます)。

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

特に：

  • defaultdictに aを使用しsongdictます。listキーが存在しない場合、新しい値が自動的に作成されます。また、キーがディクショナリにあるかどうかを確認するために使用しないkey in your_dict.keys()でください。そのチェックはO(n). key in your_dict時間のかかる使い方O(1)。defaultdicta を使用すると、チェックをまったく行う必要がないことに注意してください。チェックはすでに行われています。

  • zasを定義して1/xから を実行しますがf/z、これは を実行するのと同じですがf * x、後者の方がより正確になるという唯一の違いがあります (xは整数であるため、実行1/xすると精度がいくらか失われます)。

  • を使ってアイテムをソートする必要があるのだろうかop.itemgetter(0)。つまり、要素はタプルなので、最初に最初のキーで、次に2番目のキーで並べ替えられます。結果は、品質とアルファベット順に並べ替えたい曲になります(品質が複数の曲で同じ場合) . での並べ替えの方が速いと思うかもしれ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 に答える