数据结构：Top K 按值排序的字典键

Question

我有一本非常大的字典，其中包含 {(Tuple) : [int, int]} 形式的条目。例如，无法放入内存的 dict = {(1.0, 2.1):[2,3], (2.0, 3.1):[1,4],...}。

我只对字典中按每个键值的第一个元素排序的前 K 个值感兴趣。是否有一种数据结构可以让我只保留最大的 K 个键值对？例如，我的字典中只需要 3 个值。我可以输入以下键值对； (1.0, 2.1):[2,3], (2.0, 3.1):[1,4], (3.1, 4.2):[8,0], (4.3, 4.1):[1,1] 而我的字典将是：(3.1, 4.2):[8,0], (1.0, 2.1):[2,3], (2.0, 3.1):[1,4]（如果键值对具有相同的第一个元素，将检查第二个元素，并且基于第二个元素的最大键值对将是保留）

Answer 1

如果您的数据不适合内存，您需要特别注意它的存储方式。它是在数据库、平面文件、csv 文件中，JSON，还是什么？

如果它是 "rectangular" 文件格式，您最好使用标准的 *nix 排序实用程序，然后只读前 k 行。

Answer 2

import heapq


class OnlyKDict(object):

    def __init__(self,K,key=lambda x:x):
        self.data = []
        self.dictionary = {}
        self.key=key         # Lambda function for the comparator
        self.K = K           # How many values to keep in dictionary

    def push(self,item):
        heapq.heappush(self.data,(self.key(item),item))
        self.dictionary[item[0]]=item[1]
        if len(self.data)>self.K:  #Size greater than k? pop minimum from heap and dict.
            item = self.pop()     #This ensure only k largest are there.
            self.dictionary.pop(item[0],None)

    def pop(self):
        return heapq.heappop(self.data)[1]

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

    def __setitem__(self,key,value):
        if self.dictionary.has_key(key):
            self.dictionary[key] = value #If key present update value
        else:
            self.push((key,value))  ##Else push key and value as a tuple

h = OnlyKDict(8,lambda x:x[0][1] if x[0][1]==x[0][0] else x[0][0]) ##Compare 2nd value if both equal else compare 1st value only.

for i in xrange(10):
    h[(i,i)] = [i,i]

print h.dictionary

输出：{(5, 5): [5, 5], (6, 6): [6, 6], (4, 4): [4, 4], (7, 7): [7, 7], (9, 9): [9, 9], (8, 8): [8, 8], (2, 2): [2, 2], (3, 3): [3, 3]}

您可以看到这里只存储了前 8 个值。

取自 heapq with custom compare predicate 的主要内容。

我们所做的是创建我们的自定义堆 class，它采用一个关键参数，我们在其中指定要排序的值。

接下来是每当这个大小大于 8 时，我们弹出最小项。这确保我们始终只有最多 8 个值。

Answer 3

这是一个自定义的 OrderedDict，它为您保留了 N 个最大的键：

from collections import OrderedDict
from operator import itemgetter


class LimitedSizeOrderedDict(OrderedDict):
    def __init__(self, *args, **kwds):
        self.maxlen = kwds.pop("maxlen", None)
        if args:
            try:
                top_n = sorted(*args, key=itemgetter(0, 0))[-self.maxlen:]
                self.min_key = top_n[0][0]
            except TypeError:
                raise Exception("keys should be in tuple format")
        else:
            self.min_key = (float("inf"), 0)
        super(LimitedSizeOrderedDict, self).__init__(top_n, **kwds)

    def __setitem__(self, key, value):
        if self._check_size():
            OrderedDict.__setitem__(self, key, value)
            if key[0] < self.min_key[0]:
                self.min_key = key
        elif key[0] > self.min_key[0]:
            self.pop(self.min_key)
            OrderedDict.__setitem__(self, key, value)
            self.min_key = min(self, key=itemgetter(0))

    def _check_size(self):
        if self.maxlen is not None:
            if len(self) < self.maxlen:
                return True
            return False
        return True

演示：

In [2]: a = LimitedSizeOrderedDict([((7,2),3), ((2, 5), 3), ((6, 0), 1)], maxlen= 2)

In [3]: a
Out[3]: LimitedSizeOrderedDict([((6, 0), 1), ((7, 2), 3)])

In [4]: a[(12, 5)] = 10

In [5]: a
Out[5]: LimitedSizeOrderedDict([((7, 2), 3), ((12, 5), 10)])

In [6]: a[(10, 5)] = 9

In [7]: a
Out[7]: LimitedSizeOrderedDict([((12, 5), 10), ((10, 5), 9)])

In [8]: a[(0, 5)] = 9

In [9]: a
Out[9]: LimitedSizeOrderedDict([((12, 5), 10), ((10, 5), 9)])

数据结构：Top K 按值排序的字典键

Data structure: Top K ordered dictionary keys by value

python

heap

dictionary

data-structures