Java-Code Ausführungszeit Ausgabe

Question

Ich habe den folgenden Code Modellierung eines schlanken Rahmenwerk für einen Eckpunkt in meiner Studie der Netzwerkdiffusion. Der erste Prototyp stammt von einem Framework in Python, das ich in Java übersetzt habe. Das Problem, das ich habe, ist, dass, während dieser Code viel schneller als seine Python-Version bis zu 10000 Vertices läuft, für eine größere Anzahl von Vertices (100.000+) zum Stillstand kommt. Tatsächlich wurde die Python-Version in 1.2 Minuten ausgeführt, während der Java-Build selbst nach 7 Minuten der Ausführung nicht zurückkehrte. Ich bin nicht sicher, warum der gleiche Code bei einer größeren Anzahl von Vertices zusammenbricht und ich brauche Hilfe bei der Korrektur des Codes.

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++; 
     } 
    } 

    } 
} 

Als Referenz ist die Python-Version dieses Code wie folgt:

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

Dies ist ein sehr interessantes Problem war, und ich glaube, ich etwas Neues auch gelernt. Ich habe versucht, den Code auf verschiedene Arten zu optimieren, wie zum Beispiel die Verwendung eines parallelen Stroms sowie die Verwendung von ThreadLocalRandom, die bis zu dreimal schneller sein kann als Random. Endlich habe ich jedoch den größten Engpass entdeckt: Speicher für die JVM reserviert.

Da Sie so viele Elemente zu Ihrer Map hinzugefügt haben (der schlimmste Fall ist 500.000 mit 100.000 Vertices), benötigen Sie viel Speicher (Heap-Speicher). Wenn Sie zulassen, dass die JVM Speicher dynamisch zuweist, dauert die Ausführung des Programms sehr lange. Die Art und Weise, wie ich das gelöst habe, bestand darin, Speicher für die JVM vorzuprogrammieren (speziell 3 GB), indem man -Xms3G als VM-Argument auf die Run-Konfiguration des Programms anwendet, was in Ihrer IDE oder über das Terminal erfolgen kann.

Ich habe auch Ihren Code ein wenig optimiert, die ich weiter unten wird Post (es in nur wenigen Sekunden für mich abgeschlossen):

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(); 
    } 

} 

Ich bin nicht sicher, ob der expliziten Konsequenzen bezüglich der Verwendung von ThreadLocalRandom in eine Multithread-Umgebung, aber Sie können es zurück zu Math#random schalten, wenn Sie möchten.