Представление 100K X 100K матриц в Java

Question

Представление 100K X 100K матриц в Java

Как я могу сохранить 100K X 100K матриц в Java?

Я не могу сделать этого с нормальным объявлением массива, поскольку оно бросает a java.lang.OutofMemoryError.

8

java arrays

задан Peter Mortensen 8 February 2010 в 17:50

9 ответов

Библиотека Colt имеет реализацию с разреженной матрицей для Java.

В качестве альтернативы вы можете использовать Berkeley DB в качестве механизма хранения.

Теперь, если на вашем компьютере достаточно оперативной памяти (не менее 9 гигабайт), вы можете увеличить размер кучи в командной строке Java.

14

ответ дан 5 December 2019 в 04:32

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

10

ответ дан 5 December 2019 в 04:32

100 000 x 100 000 = 10 000 000 000 (10 миллиардов) записей. Даже если вы храните однобайтовые записи,

7

ответ дан 5 December 2019 в 04:32

Вы можете обновление до этой машины:

http://www.azulsystems.com/products/compute_appliance.htm

864 процессорных ядра и 768 ГБ памяти, стоит где-то только дом на одну семью.

4

ответ дан 5 December 2019 в 04:32

Что ж, я бы посоветовал вам увеличить объем памяти в вашем jvm, но вам понадобится много памяти, поскольку вы говорите о 10 миллиардах элементов. Это (едва) возможно при большом количестве памяти или кластеризованном jvm, но, вероятно, это неправильный ответ.

Вы получаете outOfmemory, потому что, если вы объявляете int [1000], память выделяется немедленно (вдобавок двойные значения занимают больше места, чем int - представление int также сэкономит вам место). Может быть, вы можете заменить более эффективную реализацию вашего массива (если у вас много пустых записей, ищите представления "разреженной матрицы").
Вы можете хранить части во внешней системе, например, в memcached или в буферах с отображением памяти.

Здесь есть много хороших предложений,

3

ответ дан 5 December 2019 в 04:32

Вы должны попробовать «внешний» пакет для обработки матриц, я никогда этого не делал, может что-то вроде jama .

2

ответ дан 5 December 2019 в 04:32

Если у вас нет 100K x 100K x 8 ~ 80 ГБ памяти, вы не можете создать эту матрицу в памяти. Вы можете создать эту матрицу на диске и получить к ней доступ, используя отображение памяти. Однако использование этого подхода будет очень медленным.

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

2

ответ дан 5 December 2019 в 04:32

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

Если вычисление 100K * 100K * 8 меньше, чем объем физической памяти на вашей машине для использования JVM, то простым решением будет использование разреженного массива.

Если массив разреженный, с (скажем, 75% и более элементов - ноль, то вы можете сэкономить место, используя библиотеку разреженных массивов. Были предложены различные альтернативы, но во всех случаях все равно нужно разобраться, даст ли это достаточную экономию. Выясните, сколько ненулевых элементов будет, умножьте их на 8 (чтобы удвоить) и (скажем, на 4), чтобы учесть накладные расходы разреженного массива. Если это меньше, чем количество физической памяти, которое вы можете предоставить JVM, то разреженные массивы являются приемлемым решением.

Если разреженные и не разреженные массивы (в памяти) не будут работать, то все усложнится, и жизнеспособность любого решения будет зависеть от паттернов доступа к данным массива.

Одним из подходов является представление массива в виде файла, который отображен в памяти в виде MappedByteBuffer. Предположив, что у вас недостаточно физической памяти для хранения всего файла в памяти, вы сильно ударите по системе виртуальной памяти. Поэтому лучше всего, если ваш алгоритм в любой момент времени будет работать только на смежных разделах массива. Иначе вы, скорее всего, умрете от подмены.
Второй подход - это вариант первого. Сделайте карту массива/файла по секциям за раз, а когда закончите, распечатайте карту и перейдите к следующей секции. Это работает только в том случае, если алгоритм работает на массиве в секциях.
Третий подход заключается в представлении массива с использованием облегченной базы данных типа BDB. Это будет медленнее, чем любое решение в памяти, так как чтение элементов массива будет транслироваться в дисковые обращения. Но если вы ошибетесь, то это не убьет систему так, как это сделает подход с отображением памяти. (И если Вы сделаете это на Linux/Unix, то кэш блоков дисков системы может ускорить работу, в зависимости от шаблонов доступа к массивам Вашего алгоритма)
Четвертым подходом является использование кэша распределенной памяти. Он заменяет диск i/o на сетевой i/o, и трудно сказать, хорошо это или плохо.
Пятый подход заключается в анализе Вашего алгоритма и выяснении возможности его реализации в виде распределенного алгоритма; например, с разделами массива и соответствующими частями алгоритма на разных машинах.

5

ответ дан 5 December 2019 в 04:32

Другие вопросы по тегам:

java arrays

Похожие вопросы:

score 7 · Accepted Answer

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

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

public class SparseMatrix<T> {
    private T defaultValue;
    private int m;
    private int n;
    private Map<Integer, T> data = new TreeMap<Integer, T>();
    /// create a new matrix with m rows and n columns
    public SparseMatrix(int m, int n, T defaultValue) {
        this.m = m;
        this.n = n;
        this.defaultValue = defaultValue;
    }
    /// set value at [i,j] (row, col)
    public void setValueAt(int i, int j, T value) {
        if (i >= m || j >= n || i < 0 || j < 0) 
            throw new IllegalArgumentException(
                    "index (" + i + ", " +j +") out of bounds");        
        data.put(i * n + j, value);
    }
    /// retrieve value at [i,j] (row, col)
    public T getValueAt(int i, int j) {
        if (i >= m || j >= n || i < 0 || j < 0) 
            throw new IllegalArgumentException(
                    "index (" + i + ", " +j +") out of bounds");
        T value = data.get(i * n + j);
        return value != null ? value : defaultValue;
    }
}

Простой тестовый случай, иллюстрирующий использование SparseMatrix, будет следующим:

public class SparseMatrixTest extends TestCase {
    public void testMatrix() {
        SparseMatrix<Float> matrix = 
            new SparseMatrix<Float>(100000, 100000, 0.0F);
        matrix.setValueAt(1000, 1001, 42.0F);
        assertTrue(matrix.getValueAt(1000,1001) == 42.0);
        assertTrue(matrix.getValueAt(1001,1000) == 0.0);        
    }   
}

Это не самый эффективный способ сделать это, так как каждая запись не по умолчанию в матрице хранится как Объект. В зависимости от количества фактических значений, которые вы ожидаете, простота такого подхода может превзойти интеграцию стороннего решения (и, возможно, работу с его лицензией - опять же, в зависимости от вашей ситуации).

Добавление матричных операций, таких как умножение, в вышеприведенную реализацию SparseMatrix должно быть простым (и оставлено как упражнение для читателя ;-)

.