如何減少內存：

我需要創建輸入圖形（具有向後邊緣的圖形）。例如：第1個圖的邊緣從1到2，從2到3;輸入圖形的邊緣從3到2，從2到1. 問題是我正在創建矩陣（N^N內存使用情況）。如何使用更少的內存來完成這項任務？如何減少內存：

import java.util.Scanner; 

public class ReverseGraph{ 
    public static void main(String[] args){ 
     Scanner scan = new Scanner(System.in); 
     int n = Integer.parseInt(scan.nextLine()); // number of vertices 
     //matrix of vertices 
     int[][] matrix = new int[n][n]; 
     Scanner sc; 
//create graph by input method(if A vertex associates with B vert than put "1" on B row, A column) 
     for(int i = 0; i < n;i++){ 
      String line = scan.nextLine(); 
      sc = new Scanner(line); 
      while(sc.hasNextInt()){ 
       matrix[sc.nextInt() - 1][i] = 1; 
      } 

     } 
     scan.close(); 

//Begin write the input graph  
     System.out.println(n); //write num of vertices 

     //write 
     for(int i = 0; i < n; i++){ 
      for(int j = 0; j < n; j++){ 
       if(matrix[i][j] == 1) 
        System.out.print((j+1) + " "); 
      } 
      System.out.println(); 
     } 
    } 
}

來源

2016-12-01 Vladok AC

矩陣是隻可能被用於存儲圖形許多數據結構中的一個。雖然它的CPU性能非常好，但它的空間表現相當糟糕。你有什麼其他的數據結構？ –

@BobDalgleish我已經看過「鄰接表」。但是，在我看來，adj列表使用的內存並不比矩陣少得多。 –

@VladokAC - 也許你應該重新考慮一下。矩陣將採用O（N^2）空間，其中N是節點的數量。鄰接列表將採用O（L）空間，其中L是鏈接的數量。 –

減少內存佔用的選項。

作爲ArrayList<int[]>實現，其中int[]是2-元件陣列的每一個表示一個鏈路的鄰接表。
如上所述，除了使用自定義類和兩個int字段來表示鏈接。
作爲HashMap<Integer, HashSet<Integer>>或HashMap<Integer, HashSet<Integer>>或HashMap<Integer, TreeSet<Integer>>，其中每個組或列表表示鏈接的目的地。
相當於上面使用Trove collection types。

所有這些是O(L)上的鏈接數量上，如果節點數量相當O(N^2)。

^{1 - 除了使用TreeSet變化...}

來源

2016-12-02 07:40:30

如何減少內存：

回答

相關問題