сортировка значений в словаре Python

Question

У меня есть 2 словаря, dict1 и dict2, которые содержат одинаковые ключи, но разные значения для ключей. Что я хочу сделать, так это для каждого словаря отсортировать значения от наибольшего к наименьшему, а затем присвоить каждому значению ранг 1-N, причем 1 является наибольшим значением. Отсюда я хочу получить разность рангов для значений в каждом словаре для одного и того же ключа. Например:

dict1 = {a:0.6, b:0.3, c:0.9, d:1.2, e:0.2}
dict2 = {a:1.4, b:7.7, c:9.0, d:2.5, e:2.0}

# sorting by values would look like this:
dict1 = {d:1.2, c:0.9, a:0.6, b:0.3, e:0.2}
dict2 = {c:9.0, b:7.7, d:2.5, e:2.0, a:1.4}

#ranking the values would produce this:
dict1 = {d:1, c:2, a:3, b:4, e:5}
dict2 = {c:1, b:2, d:3, e:4, a:5}

#computing the difference between ranks would be something like this:
diffs = {}
for x in dict1.keys():
    diffs[x] = (dict1[x] - dict2[x])

#diffs would look like this:
diffs[a] = -2
diffs[b] = 2
diffs[c] = 1
diffs[d] = -2
diffs[e] = 1

Я знаю, что словари должны быть случайными и не сортируемыми, но, может быть, есть способ поместить ключи и значения в список? Основные проблемы, с которыми я сталкиваюсь, - это сортировка ключей и значений по значению (от наибольшего к наименьшему), а затем изменение значения на соответствующий ранг в отсортированном списке.

Answer 1

Простое решение для маленьких диктов:

dict1 = {"a":0.6, "b":0.3, "c":0.9, "d":1.2, "e":0.2}
dict2 = {"a":1.4, "b":7.7, "c":9.0, "d":2.5, "e":2.0}
k1 = sorted(dict1, key=dict1.get)
k2 = sorted(dict2, key=dict2.get)
diffs = dict((k, k2.index(k) - k1.index(k)) for k in dict1)

Более эффективная, менее читаемая версия для больших диктов:

ranks1 = dict(map(reversed, enumerate(sorted(dict1, key=dict1.get))))
ranks2 = dict(map(reversed, enumerate(sorted(dict2, key=dict2.get))))
diffs = dict((k, ranks2[k] - ranks1[k]) for k in dict1)

Answer 2

Вас могут заинтересовать collection.OrderedDict

Вот пример, мое первоначальное мнение, что вы также искали словари с ключами, упорядоченными по значениям, то есть od1 и od2.

d1 = {"a":0.6, "b":0.3, "c":0.9, "d":1.2, "e":0.2}
d2 = {"a":1.4, "b":7.7, "c":9.0, "d":2.5, "e":2.0}

od1 = OrderedDict(sorted(d1.items(), key=lambda t: t[1]))
od2 = OrderedDict(sorted(d2.items(), key=lambda t: t[1]))

k1 = od1.keys()
k2 = od2.keys()

diff = dict((k, n - k2.index(k)) for n, k in enumerate(k1))

Если они вам не нужны, решение Sven возможно быстрее.

edit : не так быстро, если честно ... (sven.py - его вторая, более эффективная версия):

$ cat /tmp/mine.py | time python -m timeit
10000000 loops, best of 3: 0.0842 usec per loop
real    0m 3.69s
user    0m 3.38s
sys 0m 0.03s
$ cat /tmp/sven.py | time python -m timeit
10000000 loops, best of 3: 0.085 usec per loop
real    0m 3.86s
user    0m 3.42s
sys 0m 0.03s

Если кто-то захочет опубликовать отформатированные большие диктанты, я их тоже протестирую.

Answer 3

Какую версию python вы используете? Если 2.7, используйте OrderedDict.

В соответствии с Python 2.7 документы :

OrderedDict(sorted(d.items(), key=d.get))

Если вы используете Python 2.4-2.6, вы все равно можете использовать OrderedDict, установив его из pypi здесь или если у вас есть setuptools , запустите

easy_install ordereddict

Answer 4

Словарь не является правильной структурой данных для решения этой проблемы. Вы должны преобразовать в отсортированные списки как можно скорее и создать словарь только в качестве конечного результата. В следующем примере решения, где это возможно, используются итераторы и выражения генератора, чтобы избежать создания слишком большого (потенциально большого) списка помощников на этом пути:

def get_ranking(vals):
    '''Return a list of pairs: (key, ranking), sorted by key.'''
    ranking = sorted(((v, k) for k, v in vals.iteritems()), reverse=True)
    return sorted((k, i) for (i, (_v, k)) in enumerate(ranking))

def ranking_diff(rank1, rank2):
    return dict((k, v1 - v2) for (k, v1), (_, v2) in itertools.izip(rank1, rank2))

def get_diffs(dict1, dict2):
    r1 = get_ranking(dict1)
    r2 = get_ranking(dict2)
    return ranking_diff(r1, r2)

print get_diffs(dict1, dict2)
# prints: {'a': -2, 'c': 1, 'b': 2, 'e': 1, 'd': -2}

Обратите внимание, что в этом решении предполагается, что оба слова содержат одинаковые ключи.