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) 

該代碼可以與路徑壓縮來優化仍然有disjoint_set.find在O（1）運行。我猜O（log n）對大數仍然有用。

另一個瓶頸可能是你的工會職能。尤其是add函數的實現。

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

嘗試使用set（它是一個inplace聯合）的更新方法。我認爲會造成大量的節點內存開銷。喜歡的東西

self.contents.update(partition) 

有上並集和更新功能here一個很好的討論。

希望它有幫助！