Модераторы: LSD, AntonSaburov
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Java heap space и Граф 
:(
    Опции темы
FewG
Дата 30.12.2011, 14:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 23.11.2010

Репутация: нет
Всего: нет



Добрый День,

есть такая проблема, при создании Графа в виде матрикса (Узлы -> int[], рёбра -> int[][])  с  более 15к узов VM не хватает памяти и выкидывает ошибку: java.lang.OutOfMemoryError: Java heap space. Собственно каким образом можно импплементировать такой граф, какую структуру выбрать?
PM MAIL   Вверх
Stolzen
Дата 30.12.2011, 15:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48



В базе данных хранить можно и загружать оттуда в кэш значения кластерами.

Это сообщение отредактировал(а) Stolzen - 30.12.2011, 15:53


--------------------
datatalks.ru - анализ данных, статистика, машинное обучение
PM MAIL WWW   Вверх
dorogoyIV
Дата 30.12.2011, 15:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46



что такое 15к ?
можно, конечно, попробовать дать больше ресурсов памяти: java -Xmx1024m [твоя прога]


Цитата(FewG @  30.12.2011,  14:48 Найти цитируемый пост)
какую структуру выбрать?

в джава нет структур.
что ты использовал?
просто некорректен вопрос, поэтому сложно ответить на него...

уточни, поясни, ...
PM MAIL   Вверх
FewG
Дата 30.12.2011, 16:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 23.11.2010

Репутация: нет
Всего: нет



Цитата
что такое 15к ?

15 000 (пятьнадцать тысяч)

Цитата
в джава нет структур.

А как же 1D, 2D array; heaps и тд. тп? 


P.S. Вроде и так ясно -> имплементирую Граф с 15000-20000 узлами, VM говорит: "мол места нет". Значит мной выбраная "структура"

Код

public class Graph {

    private int[][] edges;
    private int[] vertices;

    public Graph(int V) {
        this.edges = new int[V][V];
        this.vertices = new int[V];
    }
}



не подходит.

PM MAIL   Вверх
dorogoyIV
Дата 30.12.2011, 16:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46



Цитата(FewG @  30.12.2011,  16:14 Найти цитируемый пост)
(пятьнадцать тысяч)

блин... smile
вслух, по буквам произнеси!!!
smile ты второй smile
ладно, не обижайся, тут вообще не форум лэнгвистов...



Цитата(FewG @  30.12.2011,  16:14 Найти цитируемый пост)
А как же 1D, 2D array; heaps и тд. тп? 

тут я опять тебя не понимаю...
что имеется ввиду под словом "структура" ?
Код

struct MyElem
{
    int inf;
    struct MyElem * link;
}
* begq = NULL, * endq = NULL;

вот структура на С/C++, а ты про что?

ну а пробовал добавить памяти? - -Xmx
PM MAIL   Вверх
FewG
Дата 30.12.2011, 17:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 23.11.2010

Репутация: нет
Всего: нет



Цитата
тут я опять тебя не понимаю...
что имеется ввиду под словом "структура" ?

Википедия  smile 

Отводил доп. память, не спасает.  Ведь  всё-таки 15000 в квадрате многовато будет, значит нужно искать другой подход реализации графа.  smile 
PM MAIL   Вверх
dorogoyIV
Дата 30.12.2011, 18:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46



да, мы тут помедетируем...
к тому же, возможно телепаты вернуться из отпуска...

(и все равно не понятно - 15к, это 15 Кб что ли?, тогда это 15 * 1024 = 15360 (никак не 15000 !!!)) - ну не могу я тебя понять!!!
PM MAIL   Вверх
FewG
Дата 30.12.2011, 21:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 23.11.2010

Репутация: нет
Всего: нет



Цитата(dorogoyIV @ 30.12.2011,  18:19)
да, мы тут помедетируем...
к тому же, возможно телепаты вернуться из отпуска...

(и все равно не понятно - 15к, это 15 Кб что ли?, тогда это 15 * 1024 = 15360 (никак не 15000 !!!)) - ну не могу я тебя понять!!!

15 000 Узлов Графа. На картинке их 6, у меня более 15 000. Ясно?  smile 

user posted image
PM MAIL   Вверх
dorogoyIV
Дата 31.12.2011, 03:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46



 smile  во, теперь понятно
ну 15000 это не страшно. может быть ты для каждого узла пишешь - new ... ?
или прога заходит в бесконечную рекурсию или цикл... ?
посмотри внимательно, попробуй оптимизировать код  smile 
PM MAIL   Вверх
Stolzen
Дата 31.12.2011, 05:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48



Кстати, 15к и правда не так много, год назад где-то на с++ писал программу, оперирующую на порядок большим количеством узлов - и не вылетала она от потери памяти. Правда данные обрабатывала несколько суток и неправильно smile 

Как сам граф хранится? В виде какой матрицы? Может лучше в виде списков ребер хранить? (И от самого графа ведь зависит! Разреженный он или нет, и прочее)

Это сообщение отредактировал(а) Stolzen - 31.12.2011, 05:26


--------------------
datatalks.ru - анализ данных, статистика, машинное обучение
PM MAIL WWW   Вверх
dorogoyIV
Дата 31.12.2011, 05:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46



windows дает в ваше распоряжение 4 Гб памяти. (как в линуксах, я, извините не знаю :( )
этой паматью можно по разному распорядиться...

PM MAIL   Вверх
Mirkes
Дата 1.1.2012, 20:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17



Если я правильно понял вопрос, то под "структурой" понимается хранение графа в виде массива вершин и матрици инциденций. 
Как верно заметил Stolzen эффективный способ хранения графа сильно зависит от разреженности. 
Недавно сам писал работу с графами и использовал следующую структуру данных:
1. Масссив вершин 
2. двумерный массив для ребер. При этом для каждой вершины в соответсвующей строке двумерного массива хранился только список вершин, связанных с данной ребром. 
Такая структура данных для графа дает существенную экономию по памяти, если граф не близок к полносвязому (в последнем случае можно хранить список вершин, с которыми данная НЕ связяна ребром).
Правда с такой структурой не удобно работать прирешении некоторых задач на графах.  


--------------------
Mirkes
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Java"
LSD   AntonSaburov
powerOn   tux
javastic
  • Прежде, чем задать вопрос, прочтите это!
  • Книги по Java собираются здесь.
  • Документация и ресурсы по Java находятся здесь.
  • Используйте теги [code=java][/code] для подсветки кода. Используйтe чекбокс "транслит", если у Вас нет русских шрифтов.
  • Помечайте свой вопрос как решённый, если на него получен ответ. Ссылка "Пометить как решённый" находится над первым постом.
  • Действия модераторов можно обсудить здесь.
  • FAQ раздела лежит здесь.

Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Java: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.1134 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.