0

我正在处理一个关于巨大图的任务，我必须通过读取一个近 50 亿行的 .txt 文件来构建主图（作为邻接列表）。实际上，图由 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的数组而不是LinkedList，比如；

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
   }
4

2 回答 2

4

因为你正在索引它。这是对链表的 O(n) 操作，但对数组是 O(1)。

于 2013-07-31T00:05:09.060 回答
1

我相信这归结为时间复杂度。

数组的读取时间复杂度为 O(1)。但是当你使用双向链表时，时间复杂度为 O(n)。

我会建议我一直最喜欢的 ArrayList。

于 2013-07-31T00:09:48.013 回答