Python中如何实现按值排序的字典？

3 投票

4 回答

3396 浏览

数据工程师

提问于 2025-04-17 11:53

我对Python中一种字典（dict）的实现很感兴趣，这种字典可以提供一个遍历已排序值的接口。也就是说，我想要一个带有"sortedvalues()"函数的字典。

简单来说，我可以用 sorted(dict.values()) 来实现，但这不是我想要的。因为每次插入或删除项目时，都需要重新进行一次完整的排序，这样效率就很低了。

需要注意的是，我并不是在询问关于按键排序的字典（如果你想了解这个问题，可以参考Python中的按键排序字典和Python 2.6的TreeMap/SortedDictionary?这两个链接，里面有很好的答案）。

数据结构效率优化接口设计编程技巧字典排序有序字典插入删除值排序

4 个回答

这里有一个更简单的想法：

你可以创建一个类，让它继承自 dict（字典）。
你可以使用缓存：在遍历字典时才对键进行排序，并且标记这个字典为已排序；插入新键时只需将它们添加到键的列表末尾。

kindall 在评论中提到，对几乎已经排序的列表进行排序是很快的，所以这种方法应该也会很快。

回答于 2025-04-17 由 Python大师

分享举报

一种解决方案是创建一个类，这个类不仅继承自 dict，还维护一个按值排序的键列表（sorted_keys），以及对应的（已排序的）值列表（sorted_values）。

接着，你可以定义一个 __setitem__() 方法，利用 bisect 模块快速找到新（键，值）对应该插入到两个列表中的位置 k。然后，你可以将新键和新值同时插入到字典中，以及你维护的两个列表中，使用 sorted_values[k:k] = [new_value] 和 sorted_keys[k:k] = [new_key]；不过，这种插入的时间复杂度是 O(n)（所以整个字典的时间复杂度是 O(n^2)）。

另一种有序元素插入的方法是使用 heapq 模块，将 (value, key) 对插入其中。这样做的时间复杂度是 O(log n)，比前面提到的基于列表的方法要快。

遍历字典时，可以简单地遍历你维护的键列表（sorted_keys）。

这种方法节省了每次想要遍历字典（带有排序值）时对键进行排序所需的时间，实际上是将这个时间成本转移到了构建已排序的键和值列表上，虽然这样做会增加一些时间开销。

回答于 2025-04-17 由 Python大师

分享举报

问题在于，你需要通过键来排序或哈希，以获得合理的插入和查找性能。一个简单的实现方法是使用一个按值排序的树结构来存储条目，同时用一个字典来查找某个键在树中的位置。不过，你需要深入了解如何更新这棵树，因为这个查找字典必须保持正确。基本上，这就像你要维护一个可更新的堆。

我觉得有太多的选择，使得很难从这样的结构中做出一个合理的标准库选项，而且这种需求也太少见了。

更新：一个可能对你有用的技巧是使用双重结构：

一个普通的dict，像往常一样存储键值对
任何一种排序列表，比如使用bisect

然后你需要在这两个结构上实现常见的操作：新的值要同时插入到这两个结构中。比较棘手的部分是更新和删除操作。你先用第一个结构查找旧值，然后从第二个结构中删除旧值，接着（在更新时）像之前那样重新插入。

如果你也需要知道键，可以在你的排序列表中存储（值，键）对。

更新 2：试试这个类：

import bisect
class dictvs(dict):
    def __init__(self):
        self._list = []

    def __setitem__(self, key, value):
        old = self.get(key)
        if old is None:
            bisect.insort(self._list, value)
            dict.__setitem__(self, key, value)
        else:
            oldpos = bisect.bisect_left(self._list, old)
            newpos = bisect.bisect_left(self._list, value)
            if newpos > oldpos:
                newpos -= 1
                for i in xrange(oldpos, newpos):
                    self._list[i] = self._list[i + 1]
            else:
                for i in xrange(oldpos, newpos, -1):
                    self._list[i] = self._list[i - 1]
            self._list[newpos] = value
            dict.__setitem__(self, key, value)

    def __delitem__(self, key):
        old = self.get(key)
        if old is not None:
            oldpos = bisect.bisect(self._list, old)
            del self._list[oldpos]
        dict.__delitem__(self, key)

    def values(self):
        return list(self._list)

我想这还不是一个完整的dict。我还没有测试删除操作，只做了一点小的更新。你应该为它做一个更大的单元测试，并将values()的返回值与sorted(dict.values(instance))的返回值进行比较。这只是为了展示如何用bisect更新排序列表。

回答于 2025-04-17 由 Python大师

分享举报

Python中如何实现按值排序的字典？

4 个回答

撰写回答