Welcome to Dream.In.Code
Getting Java Help is Easy!

Join 86,392 Java Programmers. There are 1,410 online right now! Ask your question and get quick answers from Dream.In.Code experts. Join the #1 programming help community on the internet! Registration is fast and FREE... Join Now!

Chat LIVE With a Java Expert
Powered by LivePerson.com

Register to Make This Box Go Away!

Running out of memory on adjacency list

 
Reply to this topicStart new topic

Running out of memory on adjacency list

Jay3205
post 9 May, 2008 - 02:50 PM
Post #1


New D.I.C Head

*
Joined: 9 May, 2008
Posts: 2



I'm trying to create an adjacency list, using an arraylist of linkedlist. I am given a file where the first line contains two integers (one for the number of vertices and one for the number of edges in the graph). The following lines contain the the start and end vertex of each edge. My code works fine, but it seems to be very memory intensive, and I need to make an adjacency list that represents a graph with a hundred thousand nodes and a million edges. However, I keep on running out of heap space. Any tips on improving efficiency?

Here's my code.

CODE
// open input
            BufferedReader in = new BufferedReader(new FileReader(args[0]));
            
            // get # of vertices & edges
            String [] init = in.readLine().split("[ \t\n\r\f]");            
            vertex_total = Integer.parseInt(init[0]);
            edge_total = Integer.parseInt(init[2]);

            // initialize adjacency matrix
            vertices = new boolean[vertex_total];
            edges = new ArrayList <LinkedList <Integer>>(vertex_total);    

            // initialize all elements of arraylist
            for (int i = 0; i < vertex_total; i++){
                edges.add(i, new LinkedList <Integer>());
            }
    
            // create adjacency matrix for depth first search
            in.readLine();
            for (int i = 0; i < edge_total; i++){
                if (i% 10000 == 0){
                System.out.println(i);
                }            
                String [] line = in.readLine().split("[ \t\n\r\f]");
                int v = Integer.parseInt(line[0]);
                int e = Integer.parseInt(line[2]);
                                        
                edges.get(v).addFirst(e);
                edges.get(e).addFirst(v);
            }


This post has been edited by Jay3205: 9 May, 2008 - 03:36 PM
User is offlineProfile CardPM
Go to the top of the page
+Quote Post


Martyr2
post 9 May, 2008 - 04:15 PM
Post #2


Programming Theoretician

Group Icon
Joined: 18 Apr, 2007
Posts: 3,561

Your last two lines there where you are adding the vertices and edges is where you are eating up your heap. Each time you throw your int into the add first, it is being boxed up in an object and thrown on the heap. The question is getting around it... hmmm....

You could try instead of using an arraylist of linkedlists instead create an arraylist of a custom object which wraps an int array and of course the support functions for adding/removing values much like a list does. The idea is that these objects can be stored in the array list and instead of manipulating objects like a linkedlist does, it would be handling primatives which are not stored on the heap. You would also be able to control how slim your custom object is, providing only the most basic functionality required instead of the bloat of supporting all the other functions a linkedlist has with it.

The idea would be to reduce the footprint each object has and instead of a list of boxed up Integer references you would instead have a managed int array.

I can't guarantee it would work, but it would be worth exploring.

smile.gif

This post has been edited by Martyr2: 9 May, 2008 - 04:15 PM
User is offlineProfile CardPM
Go to the top of the page
+Quote Post

Jay3205
post 9 May, 2008 - 04:29 PM
Post #3


New D.I.C Head

*
Joined: 9 May, 2008
Posts: 2

Thanks alot! That idea works. = )

This post has been edited by Jay3205: 9 May, 2008 - 04:33 PM
User is offlineProfile CardPM
Go to the top of the page
+Quote Post

Fast ReplyReply to this topicStart new topic
Time is now: 5/17/08 05:10AM

Live Java Help!

Java Tutorials

Reference Sheets

Java Snippets

Bye Bye Ads

Free DIC T-Shirt

T-Shirt Example

Related Sites

Monthly Drawing

Thumb Drive

Partners

Top Contributors

Top 10 Kudos This Month