python - 找到一对值的最大值并且需要不断重建的最有效的数据结构是什么？

Question

我正在尝试找到解决这个简单问题的最快方法。现在我正在使用字典。

我有一堆 string - int 对，它们不断被丢弃以换取新的。我需要找到与 n 个最高整数(通常只有 1、2 或 3)匹配的字符串。

因此，我的数据结构的构建必须高效，但找到最大 int 及其配对字符串也很重要。

字典是否接近最佳数据结构？如果是这样，我的整数应该是键还是值？

如果重要的话，语言是 python3。

Answer 1

尝试 SortedList来自sortedcontainers module(“用纯 Python 编写，速度与 C 扩展一样快”)。

At the core of Sorted Containers is the mutable sequence data type SortedList. The SortedList maintains its values in ascending sort order. As with Python’s built-in list data type, SortedList supports duplicate elements and fast random-access indexing.

Values may be added to a SortedList using either SortedList.update() or SortedList.add(). When doing so, the list remains sorted.

由于 SortedList 是排序的，因此它支持按值或按索引进行高效查找。

如果没有该模块，请安装它:

$ pip install sortedcontainers

将您的值和字符串存储为元组对:

from sortedcontainers import SortedList

sorted_list = SortedList()

# Sample data.
sorted_list.update([
    (1, 'test'), 
    (1000, 'big number'), 
    (500, 'middle')])

>>> sorted_list[-1]
(1000, 'big number')

sorted_list.add((5000, 'even bigger'))
sorted_list.add((4000, 'big, but not biggest'))

# Get last two largest values.
>>> sorted_list[-2:]
[(4000, 'big, but not biggest'), (5000, 'even bigger')]