數據結構：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

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。

我們所做的是創建我們的自定義堆類，該類需要一個關鍵參數，我們指定要排序的值。

接下來是每當這個尺寸大於8時，我們彈出最小項目。這確保我們始終只有最多8個值。

Answer 2

如果您的數據不適合內存，您需要特別關注它的存儲方式。它是在數據庫，平面文件，csv文件，JSON還是什麼？

如果是「矩形」文件格式，那麼只需使用標準* nix排序實用程序，然後在第一行k行中讀取即可。

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)])