3

値を格納する (固定の) キーのセットがあります。私はよくキーの値を調べて、それを増減します。典型的な dict の使用法。

x = {'a': 1, 'b': 4, 'c': 3}
x['a'] += 1

さらに、値を増減するのと同じくらい頻繁に、i 番目に大きい (または小さい) 値のキーも知る必要があります。もちろん、私はソートを行うことができます：

s = sorted(x, key=lambda k:(x[k],k))
s[1] == 'c'

問題は、毎回の並べ替えがかなり高価に見えることです。特に、並べ替えの間に 1 つの項目のみをインクリメントするためです。これにより適した別のデータ構造を使用できると思います。もしかして木？

4

5 に答える 5

2

blist の sorteddict を使用して、値を順番に保つことができます。これは、繰り返し処理されると、値の順にキーを返す辞書の簡単な実装です (実際には集中的にテストされていません)。

import collections
from blist import sorteddict

class ValueSortedDict(collections.MutableMapping):
    def __init__(self, data):
        self._dict = {}
        self._sorted = sorteddict()
        self.update(data)

    def __getitem__(self, key):
        return self._dict[key]

    def __setitem__(self, key, value):
        # remove old value from sorted dictionary
        if key in self._dict:
            self.__delitem__(key)
        # update structure with new value
        self._dict[key] = value
        try:
            keys = self._sorted[value]
        except KeyError:
            self._sorted[value] = set([key])
        else:
            keys.add(key)            

    def __delitem__(self, key):
        value = self._dict.pop(key)
        keys = self._sorted[value]
        keys.remove(key)
        if not keys:
            del self._sorted[value]

    def __iter__(self):
        for value, keys in self._sorted.items():
            for key in keys:
                yield key

    def __len__(self):
        return len(self._dict)

x = ValueSortedDict(dict(a=1, b=4, c=3))
x['a'] += 1
print list(x.items())
x['a'] += 10
print list(x.items())
x['d'] = 4
print list(x.items())

これは与える：

[('a', 2), ('c', 3), ('b', 4)]
[('c', 3), ('b', 4), ('a', 12)]
[('c', 3), ('b', 4), ('d', 4), ('a', 12)]
于 2013-10-17T15:43:01.140 に答える
0

ほとんどの python 構造は、例で行ったことと同様のことを行うと思います。もう少し効率的にするために私が考えることができる唯一のことは、キーのソートされたリストを保持することです. そうすれば、挿入するたびにソートするだけで済みます。メソッドでは、インデックスで値にアクセスするたびに並べ替える必要があります。次に例を示します。

x = {'a': 1, 'b': 4, 'c': 3}
x['a'] += 1

keyList = sorted(x.keys())

print x[keyList[1]]
4

x['e'] = 7
x['j'] = 11
x['d'] = 6
x['h'] = 8

keyList = sorted(x.keys())

print x[keyList[3]]
6
print x[keyList[4]]
7

それが役立つことを願っています。

于 2013-10-17T18:19:24.310 に答える
0

演算子を使用:

import operator

max(x.iteritems(), key=operator.itemgetter(1))[0]

ドキュメントから:

operator.itemgetter(*アイテム)

オペランドのgetitem () メソッドを使用して、オペランドから項目を取得する呼び出し可能なオブジェクトを返します。複数の項目が指定されている場合は、ルックアップ値のタプルを返します。例えば：

それが最善の解決策かどうかはわかりませんが、うまくいきます。

于 2013-10-17T14:49:41.460 に答える
0

Counterfrom を使用しないのはなぜcollectionsですか？次にCounter.most_common()、ソートされたリストを取得するために使用できます。

>>> from collections import Counter
>>> x = Counter({'a': 1, 'b': 4, 'c': 3})
>>> x['a'] += 1
>>> x.most_common()
[('b', 4), ('c', 3), ('a', 2)]
于 2013-10-17T14:50:32.420 に答える