데이터 구조 : 값순으로 정렬 된 상위 키 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 [9,9], [8,8] : [8,8], [(2,2) : [2,2], (3,3)) : [7,7] : [3,3]}

여기서 상위 8 개 값만 저장되는 방법을 볼 수 있습니다.

주요 내용은 heapq with custom compare predicate에서 가져 왔습니다.

우리가 할 일은 정렬 할 값에 지정할 핵심 매개 변수를 취하는 사용자 정의 힙 클래스를 만드는 것입니다.

다음은이 크기가 8보다 큰 경우 최소 항목을 팝합니다. 이렇게하면 항상 최대 8 개의 값만 가질 수 있습니다.

다음

Answer 2

데이터가 메모리에 저장되지 않으면 저장 방법에 특히주의해야합니다. 그것은 데이터베이스, 플랫 파일, CSV 파일, JSON 또는 무엇입니까?

"직사각형"파일 형식 인 경우 표준 * nix 정렬 유틸리티를 사용하고 첫 번째 k 줄만 읽으면됩니다.

Answer 3

당신을위한 N 큰 키를 유지하는 사용자 정의 OrderedDict입니다 :

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