鏈接列表的內存優化

Question

我最近製作了一個腳本，它使用一個由多個迷宮節點構建的自定義迷宮類生成隨機迷宮。每個節點看起來是這樣的：

class mazeNode: 
    def __init__(self, pos, conn = None): 
     self.pos = pos 
     if conn: 
      self.conns = [conn] 
     else: 
      self.conns = [] 

conn是另一個mazeNode對象，self.conns創造迷宮包括每mazeNode對象，該節點連接到的過程中被改變。 pos是一個具有節點位置的元組。創建迷宮時，根據深度優先搜索算法創建mazeNode對象，並將其鏈接到一個分支中。

這個腳本運行得非常好，並且可以在大約10秒內創建尺寸爲500 * 500的迷宮。但是，它似乎不是非常有效的內存。我設法創建了尺寸爲6000 * 6000的迷宮，但是當我嘗試10000 * 10000時，無論我做什麼，即使分配了50GB的虛擬RAM，也會出現內存錯誤。對於這個尺寸，我最終得到10^8個迷宮節點對象。

我嘗試使用shelve模塊，但是這會減慢腳本太多以至於無法使用，對於更大的迷宮，我得到了遞歸深度錯誤（可能由於不必要的遞歸導致腳本變慢）。

我想知道是否有任何方法來優化腳本的內存使用率，同時保持速度。所有的節點都鏈接在一起，但並不是所有的節點都在RAM中。

EDIT 迷宮類如下：

class Maze: 

    def __init__(self, xSize, ySize): 

     self.pos = (xSize//2, ySize//2) 
     self.xSize = xSize 
     self.ySize = ySize 
     self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] 
     self.visit = set([self.pos]) 
     self.maze = mazeNode(self.pos) 
     self.node = self.maze 
     self.stack = Stack() 
     self.deadEnds = 0 
     for i in randPerm(list(range(4))): 
      self.stack.put(mazeNode(add(self.pos, self.directions[i]), self.node)) 

    def makeMaze(self): 
     while True: 
      while self.node.pos in self.visit and not self.stack.isEmpty(): 
       self.node = self.stack.pop() 
      if self.stack.isEmpty(): 
       break 
      if self.node.pos not in self.visit: 
       self.visit.add(self.node.pos) 

      for conn in self.node.conns: 
       conn.conns.append(self.node) 

      tempCount = 0 
      for i in randPerm(list(range(4))): 
       pos = add(self.node.pos, self.directions[i]) 
       if pos not in self.visit and check(pos, self.xSize, self.ySize): 
        self.stack.put(mazeNode(pos, self.node)) 
        tempCount += 1 
      if tempCount == 0: 
       self.deadEnds += 1 
     if len(self.maze.conns) == 1: 
      self.deadEnds += 1 

編輯2：

我用槽：和編輯mazeNode類，如下所示：

class mazeNode: 
    __slots__ = ('posx', 'posy', 'conns',) 

    def __init__(self, pos, conn = None): 
     self.posx = pos[0] 
     self.posy = pos[1] 
     self.conns = [conn] if conn else [] 

和使用sys.getsizeof()以獲取該類的實例的大小。

print(sys.getsizeof(self.maze), sys.getsizeof(self.maze.posx), sys.getsizeof(self.maze.posy), sys.getsizeof(self.maze.conns)) 

打印64 28 28 96。但是，如果我刪除__slots__，我得到56 28 28 96，這看起來很奇怪。我應該如何理解？ __slots__無法正常工作？

Answer 1

非常簡單易用，您只需將它們添加到您的類定義爲這樣：

class MazeNode(object): 
    __slots__ = ('pos', 'conn',) 

    def __init__(self, pos, conn=None): 
     self.pos = pos 
     self.conns = [conn] if conn else [] 

你要記住的唯一的事情是開槽類型/類不能添加到他們的屬性動態。只有__slots__中列出的屬性可以設置和/或修改。儘管他們做顯着減少每個對象的內存使用量，但不要瘋狂併爲您定義的每個類定義插槽。要明智，正確使用它們。