создание списка смежности, ошибка нехватки памяти - PullRequest
Новая
       8

создание списка смежности, ошибка нехватки памяти

4 голосов
/ 19 апреля 2010

Я пытаюсь создать список смежности для хранения графа. Реализация отлично работает при сохранении 100 000 записей. Тем не менее, когда я пытался хранить около 1 миллиона записей Я столкнулся с ошибкой OutofMemory:

Исключение в потоке "main" java.lang.OutOfMemoryError: пространство кучи 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)

Ниже приведена моя реализация 

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

Мне интересно, есть ли лучший способ реализовать список смежности. Кроме того, я знаю количество узлов в самом начале и в будущем я сглаживаю список при посещении узлов. Есть предложения?

Спасибо

Ответы [ 2 ]

1 голос
/ 19 апреля 2010

Мне кажется, что здесь есть несправедливое преимущество, поскольку я узнаю как название проблемы (liarliar), так и точный характер ввода.

Я могу вам сказать, что это OutOfMemoryError разработано. Вам нужно найти лучший алгоритм, который не хранит всю информацию о смежности графа в памяти.

Я воздержусь от изложения слишком большого количества алгоритмических идей, но могу вам сказать, что вам нужно сесть и подумать больше, чем нужно для программирования на этом этапе. Может быть, почитайте хорошую книгу об алгоритмах и структурах данных.

Что вы делаете сейчас, так это то, что вы на самом деле храните строки из входного файла без необходимости в вашем HashMap<String,ArrayList<String>>. Это очень неэффективно, учитывая природу проблемы.

Гораздо проще и эффективнее, если вместо этого использовать java.util.Scanner. new Scanner(new File(inputFilename)), next() и nextInt() - все, что вам нужно.

Назначьте уникальное int каждому имени (подсказка: Map<String, Integer>) и сохраните вместо него гораздо меньший int.

0 голосов
/ 22 апреля 2010

Спасибо, что ответили на мой вопрос. Да, вы догадались, что это за код.

Я думаю, что да, использование отображения строки в целые числа сэкономило бы мне некоторое пространство для списка смежности. В этом смысле вышеуказанная ошибка может быть устранена.

Однако я использовал java -jar -Xmx1024M. Это дает возможность запускать программу с большим количеством динамической памяти, и поскольку она позволяет использовать ее в данной задаче, это не должно быть причиной того, что моя отправка не удалась.

Производительность может быть одной из причин сбоя бота, хотя я не уверен.

Что касается вашего решения,

Если я создам Карту, а затем сохраню числа в списке смежности, это сэкономит мне немного места, но также добавит дополнительный поиск каждый раз, когда мне нужно получить доступ к узлу во время моего обхода bfs / dfs. Это беспокоит меня. Вы говорите, что я не должен создавать список смежности вообще? Я правильно понял, что вы пытаетесь сказать правильно.

спасибо.

...