![]() |
Модераторы: LSD, AntonSaburov |
![]() ![]() ![]() |
|
FewG |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 23.11.2010 Репутация: нет Всего: нет |
Добрый День,
есть такая проблема, при создании Графа в виде матрикса (Узлы -> int[], рёбра -> int[][]) с более 15к узов VM не хватает памяти и выкидывает ошибку: java.lang.OutOfMemoryError: Java heap space. Собственно каким образом можно импплементировать такой граф, какую структуру выбрать? |
|||
|
||||
Stolzen |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1041 Регистрация: 17.10.2005 Репутация: 23 Всего: 48 |
В базе данных хранить можно и загружать оттуда в кэш значения кластерами.
Это сообщение отредактировал(а) Stolzen - 30.12.2011, 15:53 |
|||
|
||||
dorogoyIV |
|
|||
Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1503 Регистрация: 26.3.2007 Репутация: 3 Всего: 46 |
||||
|
||||
FewG |
|
||||||
![]() Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 23.11.2010 Репутация: нет Всего: нет |
15 000 (пятьнадцать тысяч)
А как же 1D, 2D array; heaps и тд. тп? P.S. Вроде и так ясно -> имплементирую Граф с 15000-20000 узлами, VM говорит: "мол места нет". Значит мной выбраная "структура"
не подходит. |
||||||
|
|||||||
dorogoyIV |
|
|||
Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1503 Регистрация: 26.3.2007 Репутация: 3 Всего: 46 |
блин... ![]() вслух, по буквам произнеси!!! ![]() ![]() ладно, не обижайся, тут вообще не форум лэнгвистов... тут я опять тебя не понимаю... что имеется ввиду под словом "структура" ?
вот структура на С/C++, а ты про что? ну а пробовал добавить памяти? - -Xmx |
|||
|
||||
FewG |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 23.11.2010 Репутация: нет Всего: нет |
Википедия ![]() Отводил доп. память, не спасает. Ведь всё-таки 15000 в квадрате многовато будет, значит нужно искать другой подход реализации графа. ![]() |
|||
|
||||
dorogoyIV |
|
|||
Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1503 Регистрация: 26.3.2007 Репутация: 3 Всего: 46 |
да, мы тут помедетируем...
к тому же, возможно телепаты вернуться из отпуска... (и все равно не понятно - 15к, это 15 Кб что ли?, тогда это 15 * 1024 = 15360 (никак не 15000 !!!)) - ну не могу я тебя понять!!! |
|||
|
||||
FewG |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 23.11.2010 Репутация: нет Всего: нет |
15 000 Узлов Графа. На картинке их 6, у меня более 15 000. Ясно? ![]() ![]() |
|||
|
||||
dorogoyIV |
|
|||
Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1503 Регистрация: 26.3.2007 Репутация: 3 Всего: 46 |
![]() ну 15000 это не страшно. может быть ты для каждого узла пишешь - new ... ? или прога заходит в бесконечную рекурсию или цикл... ? посмотри внимательно, попробуй оптимизировать код ![]() |
|||
|
||||
Stolzen |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1041 Регистрация: 17.10.2005 Репутация: 23 Всего: 48 |
Кстати, 15к и правда не так много, год назад где-то на с++ писал программу, оперирующую на порядок большим количеством узлов - и не вылетала она от потери памяти. Правда данные обрабатывала несколько суток и неправильно
![]() Как сам граф хранится? В виде какой матрицы? Может лучше в виде списков ребер хранить? (И от самого графа ведь зависит! Разреженный он или нет, и прочее) Это сообщение отредактировал(а) Stolzen - 31.12.2011, 05:26 |
|||
|
||||
dorogoyIV |
|
|||
Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1503 Регистрация: 26.3.2007 Репутация: 3 Всего: 46 |
windows дает в ваше распоряжение 4 Гб памяти. (как в линуксах, я, извините не знаю :( )
этой паматью можно по разному распорядиться... |
|||
|
||||
Mirkes |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 586 Регистрация: 18.8.2011 Где: Красноярск Репутация: 7 Всего: 17 |
Если я правильно понял вопрос, то под "структурой" понимается хранение графа в виде массива вершин и матрици инциденций.
Как верно заметил Stolzen эффективный способ хранения графа сильно зависит от разреженности. Недавно сам писал работу с графами и использовал следующую структуру данных: 1. Масссив вершин 2. двумерный массив для ребер. При этом для каждой вершины в соответсвующей строке двумерного массива хранился только список вершин, связанных с данной ребром. Такая структура данных для графа дает существенную экономию по памяти, если граф не близок к полносвязому (в последнем случае можно хранить список вершин, с которыми данная НЕ связяна ребром). Правда с такой структурой не удобно работать прирешении некоторых задач на графах. -------------------- Mirkes |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Java" | |
|
Если Вам помогли, и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, LSD, AntonSaburov, powerOn, tux, javastic. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Java: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |