création de liste d'adjacence, erreur de mémoire insuffisante

Question

J'essaie de créer une liste d'adjacence pour stocker un graphique. L'implémentation fonctionne correctement lors du stockage de 100 000 enregistrements. Cependant, quand j'ai essayé de stocker environ 1 million de dossiers je suis tombé Erreur de mémoire saturée:

Exception dans le thread « principal » java.lang.OutOfMemoryError: espace de tas Java à java.util.Arrays.copyOfRange (Arrays.java: 3209) à java.lang.String. (String.java:215) à java.io.BufferedReader.readLine (BufferedReader.java:331) à java.io.BufferedReader.readLine (BufferedReader.java:362) à liarliar.main (liarliar.java:39)

Après ma mise en œuvre

HashMap<String,ArrayList<String>> adj = new HashMap<String,ArrayList<String>>(num); 


     while ((str = in.readLine()) != null) 
     { 

      StringTokenizer Tok = new StringTokenizer(str); 
      name = (String) Tok.nextElement(); 
      cnt = Integer.valueOf(Tok.nextToken()); 
      ArrayList<String> templist = new ArrayList<String>(cnt); 

      while(cnt>0) 
      { 
        templist.add(in.readLine()); 
        cnt--; 
      } 
      adj.put(name,templist); 

     } //done creating a adjacency list 

Je me demande, s'il y a une meilleure façon d'implémenter la liste d'adjacence. De plus, je connais le nombre de nœuds au début et, à l'avenir, j'aplatirai la liste lorsque je visiterai des nœuds. Aucune suggestion ?

Merci

Answer 1

Il me semble avoir un avantage injuste ici que je reconnais à la fois le nom du problème (liarliar) et la nature exacte de l'entrée.

Je peux vous dire que ce OutOfMemoryError est voulu. Vous devez trouver un meilleur algorithme qui ne stocke pas toute l'information d'adjacence du graphe en mémoire. Je vais m'abstenir de donner trop d'informations algorithmiques, mais je peux vous dire que vous devez vous asseoir et penser plus que ce que vous avez besoin de programmer à ce stade. Peut-être lire un bon livre sur les algorithmes et les structures de données.

---

Ce que vous faites est en ce moment que vous stockez réellement les chaînes à partir du fichier d'entrée inutilement dans votre HashMap<String,ArrayList<String>>. Ceci est très inefficace en raison de la nature du problème.

C'est beaucoup plus facile et beaucoup plus efficace si vous utilisez un java.util.Scanner à la place. new Scanner(new File(inputFilename)) et next(), et nextInt() sont tout ce dont vous avez besoin.

Affectez un int unique à chaque nom (indice: Map<String, Integer>) et stockez le int beaucoup plus petit à la place.

Answer 2

Merci d'avoir répondu à ma question. Oui, vous l'avez deviné, de quoi parle le code.

Je pense que oui, l'utilisation d'un mappage de chaîne à des entiers permettrait de gagner de l'espace pour la liste d'adjacence. Dans ce sens, l'erreur ci-dessus peut être supprimée.

Cependant, j'ai utilisé java -jar -Xmx1024M. Cela donne un moyen d'exécuter le programme avec plus de mémoire de tas, et puisqu'il est autorisé à l'utiliser dans le prolem donné, cela ne sera pas la raison pour laquelle ma soumission échoue.

Les performances peuvent être l'une des raisons de l'échec du bot mais je ne suis pas sûr.

En ce qui concerne votre solution,

Si je crée une carte, puis stocker les numéros dans la liste des adjacencey il me sauver un peu d'espace, mais il faudra également ajouter une recherche supplémentaire chaque fois que je besoin d'accès un noeud pendant ma traversée bfs/dfs. Cela me dérange. Êtes-vous en train de dire que je ne devrais pas créer la liste d'adjacence du tout? Ai-je compris ce que vous essayez de dire correctement?

merci.