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

Question

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

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

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

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

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

Answer 1

尝试从sortedcontainers模块中SortedList("用纯Python编写，像C扩展一样快"(。

排序容器的核心是可变序列数据类型 SortedList。排序列表按升序排序维护其值。与Python的内置列表数据类型一样，SortedList支持重复元素和快速随机访问索引。

可以使用 SortedList.update(( 或 SortedList.add(( 将值添加到 SortedList 中。执行此操作时，列表将保持排序状态。

由于 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')]

Answer 2

我需要找到与n个最高整数匹配的字符串(通常 只有 1、2 或 3(。

您可以将heapq与字典一起使用。下面是提取与 3 个最高整数关联的字符串的示例。重复的数字仅在堆已满之前包含在内。

import heapq
from operator import itemgetter
L = [(1, 'test'), (1000, 'big number'), (500, 'middle'), (5000, 'even bigger'),
(4000, 'big, but not biggest'), (5000, 'another even bigger')]
d = {v: k for k, v in L}
heap = heapq.nlargest(3, d.items(), key=itemgetter(1))
res = list(map(itemgetter(0), heap))
print(res)
['even bigger', 'another even bigger', 'big, but not biggest']

如本答案所述，该解决方案将具有 O(nlogn( 时间复杂度。