in-place dictionary inversion of Python

Question

목록 사전을 뒤집을 필요가 있습니다. 정확하게 영어로 설명하는 법을 모르므로 여기에 원하는 코드가 있습니다. 너무 많은 메모리가 필요합니다.

def invert(oldDict): 
    invertedDict = {} 
    for key,valuelist in oldDict.iteritems(): 
     for value in valuelist: 
      try: 
       entry = invertedDict[value] 
       if key not in entry: 
        entry.append(key) 
      except KeyError: 
       invertedDict[value] = [key] 
    return invertedDict 

원본은 목록을 담은 것이며, 그 결과는 목록을 의미합니다. 이것은 그것을 "반전"시킨다.

test = {} 
test[1] = [1999,2000,2001] 
test[2] = [440,441] 
test[3] = [440,2000] 

print invert(test) 

이 제공이 현재 위치에서 할 수 있으면 현재의 내 전략은 내가 일하고 사전에 내 컴퓨터에 물리적 메모리의 양을 초과하기 때문에

{2000: [1, 3], 2001: [1], 440: [2, 3], 441: [2], 1999: [1]} 

내가 알 필요가 와. 발전기로 할 수있는 방법을 생각해 볼 수 있습니까?

Answer 1

이 자리에 그것을 할 수 있지만 제거 + 추가해야 할 수도 있으므로, popitem() 나는 DICT 년대는 크기가 증가하지 않는 한 크기가 조정되지 않습니다 느낌이

from collections import defaultdict 
def invert(oldDict): 
    invertedDict = defaultdict(list) 
    while oldDict: 
     key, valuelist = oldDict.popitem() 
     for value in valuelist: 
      invertedDict[value].append(key) 
    return invertedDict 

를 사용하여 oldDict 소모하지 않습니다 더미 아이템. Shrinkage rate

from collections import defaultdict 
def invert(oldDict): 
    invertedDict = defaultdict(list) 
    i=0 
    while oldDict: 
     key, valuelist = oldDict.popitem() 
     for value in valuelist: 
      invertedDict[value].append(key) 
     i+=1 
     if i%1000==0: # allow the dict to release memory from time to time 
      oldDict[None]=None 
      del oldDict[None] 
    return invertedDict 

Answer 2

가 실제로 어떤 식 으로든에게 크게에 개선 할 수있는 현재 알고리즘의 메모리 사용량을 볼 수 없습니다를 참조하십시오. 새 목록/사전을 완전히 작성하는 대신 반복자를 사용하므로 중요한 사전 메모리 사용은 원래 사전과 새 거꾸로 사전에서 비롯됩니다.

실제로 사용하고있는 사전에이 알고리즘을 실행하기에 충분한 RAM이 없다면 생각할 수있는 것은 원래의 dict과 거꾸로 된 dict을 메모리에 동시에 보관하지 않는 것입니다. 이 같이 할 수있는 역 DICT,에 추가로 그렇게하는 한 가지 방법은 원래의 DICT에서 항목을 제거하는 것입니다 :

def invert(old_dict): 
    inverted = collections.defaultdict(list) 
    while old_dict: 
     k,v = old_dict.popitem() 
     for vi in v: 
      inverted[vi].append(k) 
    return inverted 

나는 또한 코드를 단순화하기 위해 defaultdict을 사용

(통지하지만, 당신이 정말로 서브 클래스를 순수 dict, 필요가없는 경우, 당신은 당신이 try/except)

당신이 알고리즘이 완료된 후에 사용할 수있는 원본과 거꾸로 사전을 모두 유지하려면, 모든 I와 원래 있던 무슨처럼 뭔가를 할 수 디스크 파일에 파일을 저장하고 한 번에 하나의 파일 만로드 할 수있는 방법을 찾을 수 있다고 생각할 수 있습니다. 디스크에 dict을 저장하고 한 번에 하나의 코드 만로드 할 수있는 표준 Python 모듈을 모르므로 코드를 직접 작성해야 할 수도 있습니다.

Answer 3

직접적인 대답이 없습니다. 여기 내 생각이있다.

1. 나는 내가이 자리에서 할 수 있다고 생각하지 않습니다 당신이

2. Inverted index를 호출 할 수 있습니다 무엇을 원하는 생각도 나는 그것이 올바른 전략입니다 생각 하는가. 디스크 기반 솔루션을 살펴 봐야합니다. 원래 데이터 구조를 정렬하거나 구성하고 하나 이상의 파일에 기록한 다음 다시 읽은 다음 최종 데이터 구조에 병합하십시오.

Answer 4

알고리즘이 올바른 경우 현대 컴퓨터에서 RAM을 모두 소모하는 데 아마도 많은 시간이 걸릴 수 있습니다.이것을 가정 할 때, 한 번에 오직 청크 만 처리하기 위해 데이터를 위해 일부 영구 저장 장치를 사용해야합니다. DICT를 저장하기 위해 2 열의 간단한 데이터베이스 테이블을 사용하지 않는 이유는 무엇입니까?

key value 
1 1999 
1 2000 
1 2001 
2 440 
2 441 
... 

그럼 당신은 필요한 열을 order by로 선택하고 간단한 파이썬 코드와 다른 열에서 값을 그룹화하여 키로 중 열을 사용할 수 있습니다.