使用鏈表和數組構造具有鄰接表的圖形之間巨大的性能差異

我正在處理有關巨大圖的任務，並且我必須從讀取幾乎具有的.txt文件構造主圖（作爲鄰接列表） 50億行。實際上，圖由870k個頂點組成。無論如何，我意識到我的第一次和第二次實施之間存在巨大的時間差（超過2小時）。我很好奇爲什麼這兩個實現之間存在不可忽視的差異。在這裏你可以看到關於讀取txt文件和構建圖形的主要簡單代碼;使用鏈表和數組構造具有鄰接表的圖形之間巨大的性能差異

public class KosarajusSCC { 

    private int t; // for finishing times in 1st pass 
    private int s; // for leaders in 2nd pass 
    private static final int N = 875714; 
    private LinkedList<Vertex> mainList; 

    public KosarajusSCC(){ 

     this.t = 0; 
     this.s = 0; 

     this.mainList = new LinkedList<>(); 
    } 

    public void contructMainGraph() throws FileNotFoundException{ 

     Scanner reader = new Scanner(new File("src\\Assignment4\\SCC.txt")); 

     for (int i = 1; i <= N; i++) { 

      mainList.add(new Vertex(i)); 
     } 

     StringTokenizer tokenizer; 
     String str; 

     int counter = 0; 

     // construct the adjaceny list of vertices 
     while(reader.hasNextLine()){ 

      str = reader.nextLine(); 

      tokenizer = new StringTokenizer(str); 

      int tailVertex = Integer.parseInt(tokenizer.nextToken()); 
      int headVertex = Integer.parseInt(tokenizer.nextToken()); 

      mainList.get(tailVertex-1).getAdjacencyList().add(mainList.get(headVertex-1)); 
     } 

     reader.close(); 
    }

}

所以這個contructMainGraph()方法需要超過2小時，但是，如果我使用一個陣列，大小爲N的代替鏈表，等;

Vertex[] mainArray = new Vertex[N]; 

for (int i = 0; i < mainArray.length; i++) { 

    mainArray[i] = new Vertex(i+1); 
}

如果我更改while循環的最後一條語句;

mainArray[tailVertex-1].getAdjacencyList().add(mainArray[headVertex-1]);

然後在不到10秒內完成所有事情。那麼在那裏發生了什麼？我會感激，如果你能幫助，並感謝反正

編輯：我忘了共享頂點類:)

public class Vertex { 

    private int finishTime; 
    private int leader; 
    private boolean marked; 
    private int vertexID; 
    private LinkedList<Vertex> adjacencyList; 

    public Vertex(int vertexID){ 

     this.vertexID = vertexID; 
     this.marked = false; 
     this.finishTime = 0; 
     this.leader = 0; 
     this.adjacencyList = new LinkedList<>(); 
    } 
    // getters and setters here 
    }

來源

2013-07-31 quartaela

因爲你索引到它。這是一個鏈接列表上的O（n）操作，但是是一個數組上的O（1）。

來源

2013-07-31 00:05:09

你是對的，但我認爲'get（）'方法與array [i] – quartaela

@quartaela - [Javadoc for LinkedList]（http://docs.oracle.com/javase/7/docs/ api/java/util/LinkedList.html）：「所有的操作都可以像雙向鏈表那樣執行，索引到列表中的操作將從頭或尾遍歷列表中的任何一個，指定索引「。使用'ArrayList'提供與數組相同的O（1）索引。 –

@BrianRoach現在一切都很清楚。非常感謝。並感謝您的回覆奧利:) – quartaela

我認爲這歸結爲時間複雜性。

數組的讀時間複雜度爲O（1）。但是，當您使用雙鏈表時，其時間複雜度爲O（n）。

我會建議我所有的時間最喜歡的ArrayList。

來源

2013-07-31 00:09:48

使用鏈表和數組構造具有鄰接表的圖形之間巨大的性能差異

回答

相關問題