BitSet內存不足Java

我正在使用BitSet來跟蹤圖中的節點是否已使用DFS方法訪問過。爲此我創建了一個BitSet []數組。 BitSets本身可以在100.000-500.000條目之間。BitSet內存不足Java

這是我正在使用的代碼。

public void tc() { 
//  if (scc_cache_valid) 
//   return; 
     marked2 = new BitSet[node_count]; 
     for (int v = 0; v < node_count; v++) { 
      //if (marked2[v] == null) 
       marked2[v] = new BitSet(edge_count); 
      System.out.println("aaa" + marked2[v].size()); 
      for (int w : children.get(v)) { 
       if (!marked2[v].get(w)) 
        dfs(v, w); 
      } 
     } 
    } 

    public void tc(int v) { 
//  if (scc_cache_valid && marked2[v] != null) 
//   return; 

//  marked2 = new BitSet[node_count]; 
//  for (int v = 0; v < node_count; v++) { 
     if (marked2[v] == null) 
      marked2[v] = new BitSet(node_count); 
     System.out.println(marked2[v].size()); 

     for (int w : children.get(v)) { 
       if (!marked2[v].get(w)) 
        dfs(v, w); 
      } 
//  } 
    } 

    public boolean reachable(int v, int w) { 
     return marked2[v].get(w); 
    } 

    private void dfs(int v, int w) { 
     marked2[v].set(w, true); 
     System.out.println(marked2[v].length()); 

     for (int z : children.get(w)) { 
      if (!marked2[v].get(z)) 
       dfs(v, z); 
     } 
    }

不幸的是我已經沒有了堆。有沒有更好的（更高效的內存）解決方案？

謝謝。

來源

2017-05-10 HGO HGO

您是否擴展了JVM的堆空間？默認情況下，最大設置非常低。 – Andy

您實際需要存儲多少個真/假值？ – khelwood

所以你基本上有一個500,000x500,000的矩陣？這將需要31,250,000,000字節。位圖對於非稀疏數據更好。 – RealSkeptic

我認爲你的DFS算法不正確。

樹的經典DFS算法根本不需要位圖。
用於DAG或完整圖的經典DFS算法需要圖中每個節點具有一位的單個位圖。這假定存在從節點到整數的（密集的）一對一映射;例如節點號碼。如果不是，那麼通常使用HashSet<Node>。

在任何一種情況下，空間要求是O(N)而不是O(N^2)。

爲DAG /圖形的情況下的僞碼算法是：

dfs(root) = dfs0(root, new Set()); 
dfs0(node, visited) = 
     if !visited.contains(node): 
      visited.add(node) 
      // do stuff for node 
      foreach n in node.children: 
       dfs0(n, visited)

注意：有在遍歷僅使用一個設置對象。

來源

2017-05-10 11:49:12

謝謝。但是我需要爲圖中的每個節點找到它的所有子節點並存儲它。我不需要爲每個節點分別設置一個BitSet嗎？ –

不一定。無論如何，這不是DFS算法的作用，你的問題*說*你正試圖實現DFS。你爲什麼不在問題中清楚解釋你實際上想要做什麼？ –

我想查找在DAG的任何2個節點之間是否存在路徑。 –

BitSet內存不足Java

回答

相關問題