dicts - python을 사용한 동적 프로그래밍

Question

list은 dict입니다. 색인을 얻고 itertools.combinations을 사용하여 색인 조합을 얻습니다.

list_of_dict = [{1: 'a', 2:'b', 3: 'c', 4: 'd'}, 
       {1: 'b', 2:'b', 3: 'a', 4: 'd'}, 
       {1: 'a', 2:'c', 3: 'd', 4: 'd'}, 
       {1: 'c', 2:'a', 3: 'd', 4: 'b'}] 
indices = [0, 1, 2, 3] 
combinations = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), 
       (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), 
       (0, 1, 2, 3)] 

는 지금은 2 개 dict의 소요 merge 기능이 병합의 내 논리를 구현하고 하나의 dict을 반환 정의합니다. combinations의 모든 요소를 ​​병합합니다. 다음과 같이 merge에

호출이 발생 :

candidates = {} 
for p in combinations: 
    n = 1 
    temp_p = None 
    c = None 
    while (n < (len(p) - 2)): 
     c = tuple(list(p)[0:-n]) 
     if c in candidates: 
      temp_p = candidates[c] 
      break 
     else: 
      n += 1 
    if temp_p: 
     p1 = temp_p 
     p2 = p[len(c)] 
     candidate[p] = merge(list_of_dict[p1], list_of_dict[p2]) 
    else: 
     candidates[p] = merge(list_of_dict[p[0]], list_of_dict[p[1]]) 

논리를 우리가 볼 수 있듯이 내가 merge(0, 1, 2)을 계산할 때, 나는 merge(0, 1)의 출력을 다시 사용할 수 있습니다; 즉 merge(0, 1, 2) = merge(merge(0,1), 2)입니다. 마찬가지로 merge(0, 1, 2, 3)에 대해서는 merge(0, 1, 2)을 다시 사용할 수 있습니다.

질문 :

1. 나는 위의 코드 덩어리가 "논리"에 설명되어 있습니다 정확히 않는 경우 완전히 확실하지 않다.
2. 위 우아하고 효율적인 방법이 있습니까?

편집 : 병합 기능은 다음을 수행합니다. d1 [k] == d2 [k]이면 d1 [k]를 새 dict에 추가하고 else는 반환하지 않습니다. 은 그래서 예로부터 주어진 :

merge(0,1)가 반환해야합니다 : {1: None, 2: 'b', 3: None, 4: 'd'}

및

merge(0, 1, 2)는 merge({1: None, 2: 'b', 3: None, 4: 'd'}, {1: 'a', 2:'c', 3: 'd', 4: 'd'})을 병합하고 dicts의 모든 조합이 병합 될 때까지이 과정이 계속 {1: None, 2: None, 3: None, 4: 'd'}

반환해야된다.

우리는 알고리즘에 제시된 사전의 초기 숫자를 모르는 경우 특히 중요합니다. 전용 메모리에서의 참조가 함수에 전달이 경우 있도록 dict가 변경 가능한 객체이기 때문에, 내가 merge에 사전 전달 왼쪽, 모든

from collections import defaultdict 

def merge(d1, d2, *dicts): 
    new_dict = defaultdict() 
    new_dict.update(d1.copy()) 

    for key, value in d2.items(): 
     if value != new_dict[key]: 
      new_dict[key] = None 

    if dicts: 
     new_dict = merge(new_dict, *dicts) 

    return new_dict 


for comb in combinations: 
    print(merge(*map(list_of_dict.__getitem__, comb))) 

첫째 :

Answer 1

이 코드는 모든 요구 사항을 맞습니다. id 기능으로 쉽게 확인할 수 있습니다. 따라서이 솔루션은 색인을 사용하여 목록에서 사전을 수집하는 것보다 읽기 쉽기 때문에 더 평이합니다.

2 차적으로, 은 merge으로 전달 된 첫 번째 사전을 사용하므로 원래 조합은 다른 조합에 대해 수정되지 않은 상태로 유지됩니다.

또한 당신이 대신 dict으로 볼 수 나는 collections 패키지에서 defaultdict을 사용하므로 d1 및 d2 다른 키가있는 경우 - 당신은 new_dict의 경우 키 존재를 확인 건너 뛸 수 있습니다.

마지막으로 map(list_of_dict.__getitem__, comb) - 이것은 list_of_dict의 항목이있는 생성자 객체 (파이썬 3.x)를 반환하며, 색인은 comb입니다. (*) map 앞에있는 와일드 카드는 을 인자로 풀고, 실제로는 새로운리스트 나 튜플을 생성하지 않고 (그리고 나중에 풀지 않고) 단지 merge 인수와 같은 항목 (목록의 사전 참조)을 생성합니다.

그게 전부입니다. 나는 20 개 사전의 목록이 코드 (각 사전 LEN = 10000)를 테스트 한 또한

defaultdict(None, {1: None, 2: 'b', 3: None, 4: 'd'}) 
defaultdict(None, {1: 'a', 2: None, 3: None, 4: 'd'}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: 'd'}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 
defaultdict(None, {1: None, 2: None, 3: 'd', 4: None}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: 'd'}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 
defaultdict(None, {1: None, 2: None, 3: None, 4: None}) 

을하고 난 다음 타이밍있어 :

제공 코드는이 인쇄됩니다

을 dicts
1. 의 생성 목록 : 15.630234674000349

,617,451 : 15.96887145599976

이 (총 1012)는 각 인덱스 조합에 병합 적용