Большая структура данных Java для хранения матрицы

Question

Мне нужно сохранить 2-мерную матрицу, содержащую почтовые индексы и расстояние в км между каждым из них. У моего клиента есть приложение, которое вычисляет расстояния, которые затем сохраняются в файле Excel. В настоящее время насчитывается 952 места. Таким образом, матрица будет иметь 952x952 = 906304 записей.

Я пытался отобразить это в HashMap [Integer, Float]. Целое число - это хеш-код двух строк для двух мест, например, «А» и «Б». Значение с плавающей запятой - это расстояние в км между ними.

При заполнении данных я сталкиваюсь с OutOfMemoryExceptions после 205 тыс. Записей. У вас есть совет, как я могу хранить это умным способом? Я даже не знаю, умно ли хранить целую кучу в памяти. Мои варианты: SQL и MS Access ...

Проблема в том, что мне нужен очень быстрый и, возможно, очень частый доступ к данным, поэтому я выбрал HashMap, потому что он работает в O (1) для поиска.

Спасибо за ваши ответы и предложения!

Marco

Answer 1

2d массив будет более эффективным с точки зрения памяти. Вы можете использовать маленькую хэш-карту, чтобы отобразить 952 места в число от 0 до 951. Тогда просто сделайте:

float[][] distances= new float[952][952];

Чтобы разобраться, просто используйте два поиска по хешу, чтобы преобразовать два места в два целых числа и использовать их в качестве индексов в массиве 2d.

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

Тем не менее, 906304 на самом деле не так много записей, вам просто нужно увеличить максимальный размер кучи Xmx

Answer 2

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

РЕДАКТИРОВАТЬ: есть два обычно используемых алгоритма для нахождения (приблизительного) геодезического расстояния между двумя точками, заданными парами долгота / широта.

• Формула Викенти основана на приближении эллипсоида. Это более точно, но сложнее в реализации.

• Формула Haversine основана на сферическом приближении. Это менее точно (0,3%), но проще в реализации.

Answer 3

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

Это не было бы проблемой, если бы вы конкатенировали две строки (будьте осторожны, используя разделитель, который не может появляться в указателях мест), и позволяя HashMap делать свое волшебство, но метод, который вы предложили Использование хеш-кодов для двух строк в качестве ключа приведет к неприятностям.

Answer 4

Можете ли вы просто увеличить объем памяти, доступной для JVM?

java -Xmx512m ...

По по умолчанию максимальная конфигурация памяти составляет 64 МБ. Еще несколько советов по настройке здесь . Если вы можете сделать это, то можете хранить данные в процессе и максимизировать производительность (т. Е. Вам не нужно рассчитывать на лету).

Answer 5

Стивен С. имеет хорошее замечание: если расстояния такие же, как у мух, то вы, вероятно, можете сэкономить память, выполнив некоторые вычисления на лету. Все, что вам нужно, это пространство для долготы и широты для 952 почтовых индексов, а затем вы можете использовать формулу vicenty , чтобы сделать свой расчет, когда вам нужно. Это позволит использовать вашу память O (n) в почтовых индексах.

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

Если эти предположения верны, то если вы тратите несколько вычислений на целый пакет памяти, это может помочь вам масштабироваться в будущем, если вам когда-нибудь понадобится обработать больший набор данных.

Answer 6

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

Предположим, у вас есть 4 локации. Затем вам нужно оценить расстояния между A-> B, A-> C, A-> D, B-> C, B-> D, C-> D. Это предполагает шесть записей в вашей HashMap (4 выберите 2).

Это заставит меня поверить в то, что фактический оптимальный размер вашей HashMap (952 выберите 2) = 452 676; НЕ 952х952 = 906,304.

Все это предполагает, конечно, что вы храните только односторонние отношения (то есть от A-> B, но не от B-> A, поскольку это избыточно), что я бы порекомендовал, поскольку вы уже испытываете проблемы с памятью.

Редактировать: Надо было сказать, что размер вашей матрицы не является оптимальным, вместо того, чтобы сказать, что описание не было точным.

Answer 7

В последнее время я справился с подобными реквизитами для моей магистерской диссертации.

Я закончил с классом Matrix, который использует double[], а не double[][], чтобы уменьшить двойные издержки с разыменованием (data[i] это массив, тогда array[i][j] это double) позволяя виртуальной машине выделять большой непрерывный кусок памяти:

public class Matrix {

    private final double data[];
    private final int rows;
    private final int columns;

    public Matrix(int rows, int columns, double[][] initializer) {
        this.rows = rows;
        this.columns = columns;
        this.data = new double[rows * columns];

        int k = 0;

        for (int i = 0; i < initializer.length; i++) {
            System.arraycopy(initializer[i], 0, data, k, initializer[i].length);
            k += initializer[i].length;
        }
    }

    public Matrix set(int i, int j, double value) {
        data[j + i * columns] = value;
        return this;
    }

    public double get(int i, int j) {
        return data[j + i * columns];
    }
}

этот класс должен использовать меньше памяти, чем HashMap, поскольку он использует примитивный массив (не требуется бокс): ему требуется только 906304 * 8 ~ 8 Mb (для double s) или 906304 * 4 ~ 4 Mb (для float s). Мои 2 цента.

NB Для простоты я пропустил некоторые проверки здравомыслия

Answer 8

Вам просто понадобится больше памяти. При запуске вашего Java-процесса, начните его так:

Java -Xmx256M MyClass

-Xmx определяет максимальный размер кучи, поэтому это говорит о том, что процесс может использовать до 256 МБ памяти для кучи. Если вы все еще не хватает, продолжайте увеличивать это число, пока не достигнете физического предела.

Answer 9

Создайте новый класс с 2 слотами для названий локаций. Имейте это всегда, поместите алфавитное имя в первом слоте. Дайте ему правильный метод равенства и хэш-кода. Сравните его (например, в алфавитном порядке по именам). Брось их всех в массив. Сортируй это.

Кроме того, hash1 = hash2 не подразумевает object1 = object2. Никогда не делай этого. Это хак.