Python의 목록에서 중첩 된 dicts와 중복 된 dicts를 제거하려면 어떻게합니까?

Question

나는이 같은 사전을 중첩 포함 사전의 목록을 가지고 : 나는 순서에 대해 걱정하지 않는다

v1 = [ { 'a': 1, 'b': { 'c': 3 } }, 
     { 'a': 1, 'b': { 'c': 3 }, 'd': 4 }, 
     { 'a': 1 } ] 

:

v0 = [ { 'a': 1, 'b': { 'c': 3 } }, 
     { 'a': 1, 'b': { 'c': 3 }, 'd': 4 }, 
     { 'a': 1 }, 
     { 'a': 1, 'b': { 'c': 3 } } ] 

가 어떻게 같은 결과 중복 목록 요소를 제거 할 수 있습니다 , 나는 모든 요소 집합을 원한다. 비슷한 질문을 여러 번 보았지만 대답은 중첩 된 사전이 아닌 목록에있는 간단한 사전에서만 작동합니다. 예를 들어 :

v1 = [dict(t) for t in set([tuple(d.items()) for d in v0])] 

사전의 중첩되지 않은 경우이 작동 것이다, 그러나 때문에, 나는 오류 "형식 오류 : unhashable 유형 : 'DICT'"수

Answer 1

>>> v0 = [ { 'a': 1, 'b': { 'c': 3 } }, 
...  { 'a': 1, 'b': { 'c': 3 }, 'd': 4 }, 
...  { 'a': 1 }, 
...  { 'a': 1, 'b': { 'c': 3 } } ] 
>>> out = [] 
>>> for v in v0: 
...  if v not in out: 
...   out.append(v) 
...   
>>> out 
[{'a': 1, 'b': {'c': 3}}, {'a': 1, 'b': {'c': 3}, 'd': 4}, {'a': 1}] 

Answer 2

첫째, 여부를 고려 충분히 간단한 아이디어가 있습니다.

귀하의 사전 세트가 그리 크지 않다면, 마지막 한 단어는 매우 쉽습니다. 은 이미 set처럼 작동하지만, 각 검색은 상수 시간 대신 선형입니다. 그래서, 같은 코드가 선형 대신에 2 차 시간을 취할 것입니다, 그러나 그것은 작동 할 것이고, 죽은 - 간단합니다, 그래서 그것이 받아 들일 만하다면, 그냥하십시오.

사전 집합이 상당히 커질 수 있다면 비교적 쉬운 대안이 있습니다. blist 또는 bintrees과 같은 트리 기반 모음은 대수 시간으로 검색 할 수 있습니다. 따라서 동일한 코드가 선형 대신 로그 직선 시간을 사용하게됩니다. 일반적으로 충분하며 다시 작동하고 죽은 것처럼 단순합니다.

심지어 log-linear가 너무 느리면 고정 된 dict 유형과 재귀 동결 기능이 필요합니다. 하지만 Python과 ActiveState에 대한 구현이 있습니다 (예 : frozendict). 직접 작성하기는 어렵지 않습니다.

사실, 당신은 중간에 있습니다. set([tuple(d.items()] for d in v0])은 한 단계의 동결을 수행하고 튜플 세트로 여러 개의 고정 된 임시 변통을 만듭니다 (많은 유스 케이스에서는 작동하지 않지만 사용자에게는 적합합니다). 따라서 재귀 적으로 동일한 작업을 수행하면됩니다. 당신이 차 알고리즘에 만족하는 경우

Answer 3

,

uniq = [x for n, x in enumerate(v0) if v0.index(x) == n] 

그렇지 않으면, O (N^2)이이 점에 유의하는 것이 중요

import json 
uniq = {json.dumps(x, sort_keys=True):x for x in v0}.values()