我想根据条目的值保留一个前N个条目的列表，并在每次接收到更大的值时更新它。
LIST
id: 'abc' --> 323
id: 'cbs' --> 321
id: 'aac' --> 123
New entry: id: 'aaa' --> 101. Ignore
New entry: id: 'zzz' --> 111. Ignore
New entry: id: 'cwl' --> 322. Update list
LIST
id: 'abc' --> 323
id: 'cwl' --> 322
id: 'cbs' --> 321在C++中，这可以用大小为N的std::map来实现，添加并删除它的最后一个条目。在Python中，最好的方法是什么？假设版本大于3.6
1条答案
按热度按时间kognpnkq1#
首先，与C++进行比较并不容易，因为
std::map是按键排序的，而不是按值排序的（尽管您可以通过同时保持逆Map来解决这个问题）。在python中实现类似的东西，首先你要意识到，对于你的特定情况，你不需要一直对元素进行排序，你关心的重要的事情是知道你的最小元素是什么，你可以通过保持一个堆很容易地实现这一点（minheap）的最大大小N与所有的值到目前为止。当你得到一个新元素，你只需要比较的值与头（最小的元素），如果它更大，删除堆的头（和Map中相应的条目），并将新元素添加到Map中，将值添加到堆中。同样，为了知道从Map中删除哪个元素，您还需要保留逆Map。
Python在模块
heapq中有一个堆实现，参见参考文献here。为了完整性，我在这里补充一点，尽管python中没有原生的sorted map实现，但是你可以使用外部的包，例如sortedmap，但是因为对于你的特定情况来说这是不必要的，我仍然建议使用一个不需要外部包的堆，并且不添加不必要的依赖。