Python OOP 분산 집합 성능

Question

Kruskal의 MST 알고리즘과 함께 사용하기 위해 분리 집합 데이터 구조를 만들었습니다. 200k 상호 연결 노드를 사용하여 그래프를로드하고 결합해야하며 데이터 구조 구현이 병목 현상이라고 생각합니다.

성능을 향상시키는 방법에 대한 제안 사항이 있으십니까? 내 방법이 문제가 될 수 있다고 생각합니다.

class partition(object): 
    def __init__(self, element=None): 
     self.size = 0 
     if element == None: 
      self.contents = set() 
      self.representative = None 
     else: 
      self.contents = {element} 
      self.representative = element 
      self.size = 1 

    def find(self, element): 
     return element in self.contents 

    def add(self, partition): 
     self.contents = self.contents.union(partition) 
     self.size = len(self.contents) 

    def show(self): 
     return self.contents 

    def __repr__(self): 
     return str(self.contents) 

class disjoint_set(object): 
    def __init__(self): 
     self.partitions_count = 0 
     self.forest = {} 

    def make_set(self, element): 
     if self.find(element) == False: 
      new_partition = partition(element) 
      self.forest[new_partition.representative] = new_partition 
      self.partitions_count += 1 

    def union(self, x, y): 
     if x != y: 
      if self.forest[x].size < self.forest[y].size: 
       self.forest[y].add(self.forest[x].show()) 
       self.delete(x) 
      else: 
       self.forest[x].add(self.forest[y].show()) 
       self.delete(y) 

    def find(self, element): 
     for partition in self.forest.keys(): 
      if self.forest[partition].find(element): 
       return self.forest[partition].representative 
     return False 

    def delete(self, partition): 
     del self.forest[partition] 
     self.partitions_count -= 1 

if __name__ == '__main__': 
    t = disjoint_set() 
    t.make_set(1) 
    t.make_set(2) 
    t.make_set(3) 
    print("Create 3 singleton partitions:") 
    print(t.partitions_count) 
    print(t.forest) 
    print("Union two into a single partition:") 
    t.union(1,2) 
    print(t.forest) 
    print(t.partitions_count) 

편집 :

의견을 읽고 내 원래의 알고리즘이 얼마나 잘못 설계된 나는 깨달았다 추가 연구를 수행 한 후. 나는 처음부터 다시 시작하고 이것을 집어 넣었다. 모든 파티션을 단일 해시 테이블에 넣고 find()에서 경로 압축을 사용했습니다. 이것이 어떻게 보이며 내가 다루어야 할 눈부신 문제가 있습니까?

class disjoint_set(object): 
def __init__(self): 
    self.partitions_count = 0 
    self.size = {} 
    self.parent = {} 

def make_set(self, element): 
    if self.find(element) == False: 
     self.parent[element] = element 
     self.size[element] = 1 
     self.partitions_count += 1 

def union(self, x, y): 
    xParent = self.find(x) 
    yParent = self.find(y) 
    if xParent != yParent: 
     if self.size[xParent] < self.size[yParent]: 
      self.parent[xParent] = yParent 
      self.size[yParent] += self.size[xParent] 
      self.partitions_count -= 1 
     else: 
      self.parent[yParent] = xParent 
      self.size[xParent] += self.size[yParent] 
      self.partitions_count -= 1 

def find(self, element): 
    if element in self.parent: 
     if element == self.parent[element]: 
      return element 
     root = self.parent[element] 
     while self.parent[root] != root: 
      root = self.find(self.parent[root]) 
     self.parent[element] = root 
     return root 
    return False 

if __name__ == '__main__': 
    t = disjoint_set() 
    t.make_set(1) 
    t.make_set(2) 
    t.make_set(3) 
    t.make_set(4) 
    t.make_set(5) 
    print("Create 5 singleton partitions") 
    print(t.partitions_count) 
    print("Union two singletons into a single partition") 
    t.union(1,2) 
    print("Union three singletones into a single partition") 
    t.union(3,4) 
    t.union(5,4) 
    print("Union a single partition") 
    t.union(2,4) 
    print("Parent List: %s" % t.parent) 
    print("Partition Count: %s" % t.partitions_count) 
    print("Parent of element 2: %s" % t.find(2)) 
    print("Parent List: %s" % t.parent) 

Answer 1

나는 당신의 발견 구현이 잘못되어 있다고 생각합니다.

다음 변경 사항이 도움이 될 수 있습니다.

class disjoint_set(object): 
    def __init__(self): 
     self.partitions_count = 0 
     self.forest = {} 
     self.parent = {} 

    def make_set(self, element): 
     if not self.find(element): 
      new_partition = partition(element) 
      self.parent[element] = element 
      self.forest[new_partition.representative] = new_partition 
      self.partitions_count += 1 

def union(self, x, y): 
    if x != y: 
     if self.forest[x].size < self.forest[y].size: 
      self.forest[y].add(self.forest[x].show()) 
      #Update parent details 
      self.parent[self.forest[x].representative] = self.forest[y].representative 
      self.delete(x) 
     else: 
      self.forest[x].add(self.forest[y].show()) 
      #Update parent details 
      self.parent[self.forest[y].representative] = self.forest[x].representative 
      self.delete(y) 

def find(self, element): 
    if self.parent[element] == element: 
     return element 
    else: 
     return find(element) 

코드는 여전히 O (1)에서 실행 disjoint_set.find을 갖도록 경로 압축 최적화 될 수있다. 나는 O (log n)이 큰 숫자에 여전히 좋은 것 같아요.

다른 병목 현상이 사용자의 공용 기능 일 수 있습니다. 특히 함수 추가 구현.

def add(self, partition): 
    self.contents = self.contents.union(partition) 

집합 업데이트 방법을 사용하십시오 (inplace union). 거대한 no.of 노드에 대해 많은 메모리 오버 헤드가 발생한다고 생각합니다.

self.contents.update(partition) 

같은 뭔가 설정 조합 및 업데이트 기능 here에 좋은 토론이있다.

희망이 있습니다.