상호 요소가있는 모든 하위 배열을 하나의 하위 배열로 병합

Question

모든 상호 요소를 공유하는 모든 하위 배열을 찾아 하나의 하위 배열로 병합해야합니다. 은 (Python으로 구현 그러나 어떤 알고리즘 생각 도움이 될 것입니다)

다차원 배열 구조 : 나는 하나 개의 목록으로 병합 '자동차', '자전거'와 '자전거'를 갖고 싶습니다

categories = {'car':['automobile','auto'], 
      'bike':['vehicle','motorcycle','motorbike','automobile'], 
      'software':['computer','macbook','apple','microsoft','mozilla'], 
      'firefox':['internet','mozilla','browser'] 
      'bicycle':['vehicle']} 

( 첫 번째 목록의 키를 유지 새 목록의 키는 관련 키일 수 있음) '소프트웨어'와 '파이어 폭스'가 하나의 목록으로 병합되었습니다.

성능이 중요합니다. 내가 지금까지 함께 올 수

가장 좋은 방법은 (예를 들어 '자동차'=> '자동차')는이 요소 =>list_key의 1 차원 배열을 평평하게 유지하고 다음을 실행하는 것입니다 다차원 배열 (의사)의 각 목록에 대한 재귀 함수 :

function merge_similar(list_key): 
    For each element in categories[list_key]: 
     If flatten_array.has_key(element): 
      list_to_merge = flatten_array[element] 
      merge_similar(list_to_merge) /* merge other lists which share an element with our newly found similar list */ 
      categories[list_key] = merge(categories [list_key], categories[list_to_merge]) 
      delete categories[list_to_merge] 

어떤 생각이 어떻게 성능의 향상을?

감사합니다.

Answer 1

은입니다. 첫 번째 키가 없습니다. - 명령을 보관하지 마십시오. 따라서 일부 주문을 보존해야하는 경우 다른 대체 데이터 구조에서 시작해야합니다. 별도로 주문 관련 문제에서

, 내가 좋아하는 뭔가를 시작 했죠 :

순서가 중요한 경우

def merged(dictoflists): 
    result = dict() 
    reversed = dict() 
    for k, l in dictoflists.iteritems(): 
    intersecting = set(reversed.get(w) for w in l) - set([None]) 
    if intersecting: 
     pickone = intersecting.pop() 
     into = result[pickone] 
    else: 
     pickone = k 
     into = result[k] = set() 
    for ok in intersecting: 
     into.update(result.pop(ok)) 
    into.update(l) 
    for w in into: 
     reversed[w] = pickone 
    return dict((k, sorted(l)) for k, l in result.iteritems()) 

, set의 사용이 문제가 될 것입니다 그리고 당신은해야 좀 더 복잡한 (속도가 느린) 데이터 구조 - 그렇다면, 발생할 수있는 여러 가지 가능한 경우에 존중해야하는 순서 제약 조건을 정확히 상세하게 지정해야합니다.

Answer 2

재귀적인 솔루션이 빠르다는 것을 상상할 수 없습니다.
list.extend()을 너무 느리게 사용하고 있습니까?

categories['car'].extend(categories['bike']); 
categories['car'].extend(categories['bicycle']); 

아니면 키의 목록에 전달하면 병합 할,보다 일반적인 될 :

first_key=None; 
for key in keys_whose_lists_I_want_to_merge: 
    if first_key is None: 
     first_key=key; 
    else: 
     categories[first_key].extend(categories[key]); 

당신의 톤을 병합하는 경우
당신이 뭔가를 할 수 있습니다 목록을 사용하면 처음부터 루프가 없음 검사를 수행하지 않도록 최적화 할 수 있습니다. Python Performance Tips 페이지의 '런타임시 재 맵핑 기능'팁을 참조하십시오.

Answer 3

>>> categories = {'car':['automobile','auto'], 
      'bike':['vehicle','motorcycle','motorbike','automobile'], 
      'software':['computer','macbook','apple','microsoft','mozilla'], 
      'firefox':['internet','mozilla','browser'], 
      'bicycle':['vehicle']} 
>>> # Use sets for values 
>>> for k,v in categories.items(): categories[k] = set(v) 

>>> # Acumulate 
>>> for k1, v1 in categories.items(): 
    if v1: 
     for k2,v2 in categories.items(): 
      if v2 and k1 != k2 and v1 & v2: 
       v1 |= v2 
       categories[k2] = None 
     categories[k1] = v1 


>>> # Print 
>>> for k1, v1 in categories.items(): 
    if v1: print('%s: %r' %(k1,v1)) 


bicycle: {'motorbike', 'vehicle', 'auto', 'automobile', 'motorcycle'} 
firefox: {'apple', 'mozilla', 'macbook', 'computer', 'internet', 'microsoft', 'browser'} 
>>>