Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Структура данных для большого числа записей

Автор: CHEM_Eugene 16.3.2011, 12:26

Вообще мне нужно реализовать структуру известную как гиперкуб.
Что она из себя представляет - набор переменных, каждая из которых имеет конечный домен значений.

Например:

Гиперкуб из двух измерений (две переменные - v1 и r1):
[v1] = {000, 001, ... 111}
[r1] = {v1, v2, v3}

комбинация значений переменных гиперкуба дает целое число, например:
[000][v2] -> 10
[001][v3] -> 500

Я попытался реализовать подобную структуру в виде HashMap<String, Integer>, где
ключом выступает суррогатный ключ типа "000-v2", "001-v3" и т.д.

В итоге в структуре получается (размер домена переменной v1)*(размер домена переменной r1) строк.

И все бы хорошо, но на количестве в миллион строк, программа вылетает с Java Heap Memory exception

Возможно - это не самая лучшая реализация подобной структуры... Подскажите - как можно было бы хранить данные более оптимально в моём случае!
Я так понимаю мне бы подошел многомерный ассоциативный массив, к тому же он должен быть динамическим. Можете посоветовать что-то подобное?
И вообще, кто-нибудь сталкивался с решением подобной задачи?

Автор: COVD 16.3.2011, 13:21

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

Если недостаточно только памяти, то Terracotta предлагает BigMemory - доступная память как бы расширяется за счет того, что обьекты памяти сериализуются вне кучи. Вообще, любая cache система (например, ehcache) , где обьекты сохраняются на диск, может быть настроена, чтобы функционировать как динамический Map, т.е. в памяти всегда будет только часть обьектов. Но это медленнее.

Автор: CHEM_Eugene 16.3.2011, 16:37

COVD, я не уверен, что не достаточно одного компьютера. BigMemory - коммерческое решение, мне не подойдет.

Может быть все же подойдет что-то java-нативное ?

Ведь 1 млн. int-ов по идее должен убираться в памяти...

Автор: techmax 16.3.2011, 16:54

А памяти сколько выдели для JVM? по умолчанию довольно мало выделяется.

Автор: CHEM_Eugene 16.3.2011, 17:09

Цитата(techmax @ 16.3.2011, 16:54

)

А памяти сколько выдели для JVM? по умолчанию довольно мало выделяется.

Да как раз по-умолчанию и выделяю...

Как мне посчитать нужный размер памяти для моего HashMap?

Автор: COVD 16.3.2011, 17:16

Действительно, по умолчанию-то максимальный размер памяти 64М. Может просто увеличить и вопрос решен? Надо в строке запуска приложения указать начальную и максимальную память :

Код


java -Xms64M -Xmx1500M

Запросите максимально, 1500М. Сколько на самом деле программа получила и сколько свободно, можно замерить и вывести в консоль из программы

Код


       long free = Runtime.getRuntime().freeMemory();
       long total = Runtime.getRuntime().totalMemory();

Автор: CHEM_Eugene 16.3.2011, 21:14

Проблему с памятью решил, расширив ее, но увы, самым ресурсоемким оказался перебор 4 млн значений... Придется что-то менять в постановке задачи

Автор: math64 17.3.2011, 09:37

Integer занимает намного больше памяти, чем int, лучше пользоваться обычными массивами.

Код


// если почти все ячейки заняты
int[] array = new int[v1size*r1size]; // одномерный массив, индекс вычисляется v1*r1size+r1
int [][] array2 = new int[v1size][r1size]; // двумерных массив, память под пустые строки может не выделяться
HashMap<String,int[]> map = new HashMap<String,int[]>(); // строка ищется в HashMap, в строка хранится в обычном массиве
//если много пустых ячеек
class HC {
String v1;
String r1;
int value;
    @Override
    public int hashCode() {
        return f(v1.hashCode,r1.hashCode);
    }
    @Override
    public boolean equals(Object obj) {
        return v1.eqals(obj.v1 && r1.equals(obj,r1);
    }
}
HashSet<HC> set = new HashSet<HC>;