3

辞書を値でランク付けし、一意でない値のランクを平均したい、よりPythonicで高速な方法はありますか。私のアプローチ：

d = {'a':5,'b':5,'c':5,'d':1,'e':6}
ordered_keys = sorted(d, key=d.get)
ordered_v = [d[k] for k in ordered_keys]
value_rank = [(ordered_v.index(v)+1)+(ordered_v.count(v)-1)/2 for v in ordered_v]
ranked_key_list = zip(ordered_keys,value_rank)
[('d', 1), ('a', 3), ('c', 3), ('b', 3), ('e', 5)]

辞書の並べ替えに関するこの広範な議論は非常に役に立ちました: python 辞書の値の並べ替え

4

3 に答える 3

3

あなたが持っているものはかなり良いです、私ははるかに短い解決策があるとは思えません。

効率に関しては、とを繰り返し使用するとlist.index()、list.count()大規模なデータセットの場合に速度が低下する可能性があります。

大量のデータに対してこれを行う場合に、より効率的な代替実装を次に示します。

from itertools import groupby

d = {'a':5,'b':5,'c':5,'d':1,'e':6}
ranked_key_list = []
i = 1
for k, g in groupby(sorted(d.keys(), key=d.get), key=d.get):
    g = list(g)
    rank = i + (len(g)-1) / 2
    ranked_key_list.extend((k, rank) for k in g)
    i += len(g)
于 2012-12-07T21:14:22.847 に答える
3

アルゴリズムのボトルネックは、.index と .count が O(n) であるため、ボトルネックは次の行です。

value_rank = [(ordered_v.index(v)+1)+(ordered_v.count(v)-1)/2 for v in ordered_v]

全体的なパフォーマンスが O(n^2) になる原因

私はあなたのために O(n*log(n)) アルゴリズムを作成しました (ボトルネックはソートです):

import collections

d = {'a':5,'b':5,'c':5,'d':1,'e':6}
my_d = collections.defaultdict(list)
for key, val in d.items():
    my_d[val].append(key)

ranked_key_list = [] 
n = v = 1
for _, my_list in sorted(my_d.items()):
    v = n + (len(my_list)-1)/2 
    for e in my_list:
        n += 1
        ranked_key_list.append((e, v))
于 2012-12-07T21:40:49.193 に答える
0 
key_list = zip(dict.keys(), dict.values())
ranked_key_list = sorted(key_list, key=lambda x: x[1])

編集：私が平均値のことをしなかったことに気づきました....もう少し明確にできますか？35秒の平均はどうですか=3??

于 2012-12-07T20:35:04.590 に答える