Огромная разница в производительности между использованием связного списка и массива для построения графа со списком смежности

Я работаю над заданием об огромных графах, и мне нужно построить основной граф (в виде списка смежности) из чтения файла.txt, который содержит почти 5 миллиардов строк. На самом деле, граф состоит из 870 тыс. вершин. Как бы то ни было, я понял, что между моей первой и второй реализацией существует огромная разница во времени (более 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
   }
Источник

2 ответа

Решение

Потому что ты в это включаешься. Это операция O(n) в связанном списке, но операция O(1) в массиве.

Источник

Я считаю, что все сводится к сложности времени.

Массив имеет временную сложность O(1) для чтения. Но при использовании списка с двойной связью временная сложность будет равна O(n).

Я бы предложил мой самый любимый ArrayList.

Источник
Другие вопросы по тегам