Java代碼執行時間問題

Question

我有以下代碼爲我的網絡擴散研究中的頂點建模輕量級框架。最初的原型是從Python中的框架，我翻譯成Java。我遇到的問題是，儘管此代碼運行速度比Python版本高達10000個頂點，但對於更多數量的頂點（100,000+）而言，它會停止運行。事實上，python版本在1.2分鐘內執行，而java版本即使在執行7分鐘後也不會返回。我不知道爲什麼相同的代碼在更多的頂點處崩潰，我需要幫助修復代碼。

import java.util.*; 

public class Vertex 
{ 
    private int id; 
    private HashMap<Integer, Double> connectedTo; 
    private int status; 

    public Vertex(int key) 
    { 
    this.id = key; 
    this.connectedTo = new HashMap<Integer, Double>(); 
    this.status = 0; 
    } 

    public void addNeighbour(int nbr, double weight) 
    { 
    this.connectedTo.put(nbr, weight); 
    } 

    public int getId() 
    { 
    return this.id; 
    } 

    public double getWeight(int nbr) 
    { 
    return this.connectedTo.get(nbr); 
    } 

    public int getStatus() 
    { 
    return this.status; 
    } 

    public Set<Integer> getConnections() 
    { 
    return this.connectedTo.keySet(); 
    } 

//testing the class 

    public static void main(String[] args) 
    { 
    int noOfVertices = 100000; 

    Vertex[] vertexList = new Vertex[noOfVertices]; 

    for (int i = 0; i < noOfVertices; i++) { 
     vertexList[i] = new Vertex(i); 
    } 

    for (Vertex v : vertexList) { 
     int degree = (int)(500*Math.random()); //random choice of degree 
     int neighbourCount = 0; // count number of neighbours built up 

     while (neighbourCount <= degree) { 
      int nbr = (int) (noOfVertices * Math.random()); // randomly choose a neighbour 
      double weight = Math.random(); // randomly assign a weight for the relationship 
      v.addNeighbour(nbr, weight); 
      neighbourCount++; 
     } 
    } 

    } 
} 

僅供參考，這段代碼的Python版本如下：

import random 

class Vertex: 
    def __init__(self, key): 
     self.id = key 
     self.connectedTo = {} 

    def addNeighbor(self, nbr, weight=0): 
     self.connectedTo[nbr] = weight 

    def __str__(self): 
     return str(self.id) + ' connectedTo: ' \ 
      + str([x.id for x in self.connectedTo]) 

    def getConnections(self): 
     return self.connectedTo.keys() 

    def getId(self): 
     return self.id 

    def getWeight(self, nbr): 
     return self.connectedTo[nbr] 

if __name__ == '__main__': 
    numberOfVertices = 100000 
    vertexList = [Vertex(i) for i in range(numberOfVertices)] # list of vertices 

    for vertex in vertexList: 
    degree = 500*random.random() 
    # build up neighbors one by one 
    neighbourCount = 0 

    while neighbourCount <= degree: 
     neighbour = random.choice(range(numberOfVertices)) 
     weight = random.random() # random choice of weight 
     vertex.addNeighbor(neighbour, weight) 
     neighbourCount = neighbourCount + 1 

Answer 1

這是一個非常有趣的問題，我相信我學到新的東西爲好。我嘗試以不同的方式優化代碼，例如使用並行流以及使用ThreadLocalRandom，這可以比Random快三倍。但是，我終於發現了主要瓶頸：將內存分配給JVM。

因爲你的Map中有很多元素被添加（最糟糕的情況是500000有100,000個頂點），所以你需要大量的內存（堆空間）。如果您允許JVM動態分配內存，那麼該程序將需要很長時間才能執行。我解決這個問題的方法是通過將-Xms3G作爲虛擬機參數，將程序的運行配置應用於IDE或通過終端，爲JVM預先分配內存（特別是3 GB）。

，我也進行了優化你的代碼，這一點我將在下面張貼（它完成在短短的幾秒鐘對我來說）：

import java.util.*; 
import java.util.concurrent.*; 
import java.util.stream.*; 

public class Test { 

    private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current(); 

    public static void main(String[] args) { 
     int noOfVertices = 100_000; 

     Vertex[] vertexList = new Vertex[noOfVertices]; 

     IntStream.range(0, noOfVertices).parallel().forEachOrdered(i -> { 
      vertexList[i] = new Vertex(i); 

      int degree = (int) (500 * RANDOM.nextDouble()); // random choice of degree 

      for (int j = 0; j <= degree; j++) { 
       int nbr = (int) (noOfVertices * RANDOM.nextDouble()); // randomly choose a neighbor 

       vertexList[i].addNeighbour(nbr, RANDOM.nextDouble()); 
      } 
     }); 
    } 

} 

class Vertex { 

    private int id; 

    private Map<Integer, Double> connectedTo; 

    private int status; 

    public Vertex(int id) { 
     this.id = id; 

     this.connectedTo = new HashMap<>(500); 
    } 

    public void addNeighbour(int nbr, double weight) { 
     this.connectedTo.put(nbr, weight); 
    } 

    public int getId() { 
     return this.id; 
    } 

    public double getWeight(int nbr) { 
     return this.connectedTo.get(nbr); 
    } 

    public int getStatus() { 
     return this.status; 
    } 

    public Set<Integer> getConnections() { 
     return this.connectedTo.keySet(); 
    } 

} 

我不知道在使用ThreadLocalRandom關於明確的後果一個多線程的環境，但如果你願意的話，你可以將它切換回Math#random。