Редкие матрицы/массивы в Java

Ответ 1

Рассеянные массивы, построенные с помощью hashmaps, очень неэффективны для часто читаемых данных. В наиболее эффективных реализациях используется Trie, которая позволяет получить доступ к одному вектору, в котором распределены сегменты.

A Trie может вычислять, присутствует ли элемент в таблице, выполняя только TWO-индексирование только для чтения, чтобы получить эффективную позицию, в которой хранится элемент, или знать, отсутствует ли его в базовом хранилище.

Он также может предоставить позицию по умолчанию в хранилище резервных копий для значения по умолчанию для разреженного массива, так что вам не нужен ЛЮБОЙ тест по возвращенному индексу, поскольку Trie гарантирует, что все возможные исходные индексы будут отображаться как минимум к позиции по умолчанию в хранилище резервных копий (где вы часто храните нуль или пустую строку или нулевой объект).

Существуют реализации, поддерживающие быстро обновляемые Tries с автономной "компактной" операцией для оптимизации размера хранилища в конце нескольких операций. Трижды намного быстрее, чем хэшмапы, потому что им не нужна сложная хеширующая функция и не нужно обрабатывать конфликты для чтения (с помощью Hashmaps у вас есть столкновение BOTH для чтения и записи, для этого требуется, чтобы цикл пропускал следующую позицию кандидата и тест по каждому из них для сравнения эффективного индекса источника...)

Кроме того, Java Hashmaps может индексировать только объекты и создавать объект Integer для каждого хешированного исходного индекса (создание этого объекта потребуется для каждого чтения, а не только для записи) является дорогостоящим с точки зрения операций с памятью, поскольку оно подчеркивает сборщик мусора.

Я действительно надеялся, что JRE включил IntegerTrieMap <Object> в качестве реализации по умолчанию для медленного HashMap < Integer, Object > или LongTrieMap <Object> в качестве реализации по умолчанию для еще более медленного HashMap < Long, Object > ... Но это все еще не так.

Вы можете задаться вопросом, что такое Trie?

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

Например, предположим, что вам нужна матрица 1024 * 1024, содержащая только несколько ненулевых значений. Вместо того, чтобы хранить эту матрицу в массиве, содержащем 1024 * 1024 элемента (более 1 миллиона), вы можете просто разбить его на поддиапазоны размером 16 * 16, и вам потребуется всего 64 * 64 таких поддиапазонов.

В этом случае индекс Trie будет содержать только 64 * 64 целых числа (4096), и будет находиться не менее 16 * 16 элементов данных (содержащих нулевые значения по умолчанию или самый общий поддиапазон, найденный в вашей разреженной матрице).

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

Поэтому вместо использования синтаксиса типа matrix[i][j] вы должны использовать синтаксис типа:

trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] +
            ((i & 15) << 4) + (j & 15)]

который будет более удобно обрабатываться с использованием метода доступа для объекта trie.

Вот пример, встроенный в класс с комментариями (я надеюсь, что он скомпилирует ОК, поскольку он был упрощен, сообщите мне, есть ли ошибки для исправления):

/**
 * Implement a sparse matrix. Currently limited to a static size
 * (<code>SIZE_I</code>, <code>SIZE_I</code>).
 */
public class DoubleTrie {

    /* Matrix logical options */        
    public static final int SIZE_I = 1024;
    public static final int SIZE_J = 1024;
    public static final double DEFAULT_VALUE = 0.0;

    /* Internal splitting options */
    private static final int SUBRANGEBITS_I = 4;
    private static final int SUBRANGEBITS_J = 4;

    /* Internal derived splitting constants */
    private static final int SUBRANGE_I =
        1 << SUBRANGEBITS_I;
    private static final int SUBRANGE_J =
        1 << SUBRANGEBITS_J;
    private static final int SUBRANGEMASK_I =
        SUBRANGE_I - 1;
    private static final int SUBRANGEMASK_J =
        SUBRANGE_J - 1;
    private static final int SUBRANGE_POSITIONS =
        SUBRANGE_I * SUBRANGE_J;

    /* Internal derived default values for constructors */
    private static final int SUBRANGES_I =
        (SIZE_I + SUBRANGE_I - 1) / SUBRANGE_I;
    private static final int SUBRANGES_J =
        (SIZE_J + SUBRANGE_J - 1) / SUBRANGE_J;
    private static final int SUBRANGES =
        SUBRANGES_I * SUBRANGES_J;
    private static final int DEFAULT_POSITIONS[] =
        new int[SUBRANGES](0);
    private static final double DEFAULT_VALUES[] =
        new double[SUBRANGE_POSITIONS](DEFAULT_VALUE);

    /* Internal fast computations of the splitting subrange and offset. */
    private static final int subrangeOf(
            final int i, final int j) {
        return (i >> SUBRANGEBITS_I) * SUBRANGE_J +
               (j >> SUBRANGEBITS_J);
    }
    private static final int positionOffsetOf(
            final int i, final int j) {
        return (i & SUBRANGEMASK_I) * MAX_J +
               (j & SUBRANGEMASK_J);
    }

    /**
     * Utility missing in java.lang.System for arrays of comparable
     * component types, including all native types like double here.
     */
    public static final int arraycompare(
            final double[] values1, final int position1,
            final double[] values2, final int position2,
            final int length) {
        if (position1 >= 0 && position2 >= 0 && length >= 0) {
            while (length-- > 0) {
                double value1, value2;
                if ((value1 = values1[position1 + length]) !=
                    (value2 = values2[position2 + length])) {
                    /* Note: NaN values are different from everything including
                     * all Nan values; they are are also neigher lower than nor
                     * greater than everything including NaN. Note that the two
                     * infinite values, as well as denormal values, are exactly
                     * ordered and comparable with <, <=, ==, >=, >=, !=. Note
                     * that in comments below, infinite is considered "defined".
                     */
                    if (value1 < value2)
                        return -1;        /* defined < defined. */
                    if (value1 > value2)
                        return 1;         /* defined > defined. */
                    if (value1 == value2)
                        return 0;         /* defined == defined. */
                    /* One or both are NaN. */
                    if (value1 == value1) /* Is not a NaN? */
                        return -1;        /* defined < NaN. */
                    if (value2 == value2) /* Is not a NaN? */
                        return 1;         /* NaN > defined. */
                    /* Otherwise, both are NaN: check their precise bits in
                     * range 0x7FF0000000000001L..0x7FFFFFFFFFFFFFFFL
                     * including the canonical 0x7FF8000000000000L, or in
                     * range 0xFFF0000000000001L..0xFFFFFFFFFFFFFFFFL.
                     * Needed for sort stability only (NaNs are otherwise
                     * unordered).
                     */
                    long raw1, raw2;
                    if ((raw1 = Double.doubleToRawLongBits(value1)) !=
                        (raw2 = Double.doubleToRawLongBits(value2)))
                        return raw1 < raw2 ? -1 : 1;
                    /* Otherwise the NaN are strictly equal, continue. */
                }
            }
            return 0;
        }
        throw new ArrayIndexOutOfBoundsException(
                "The positions and length can't be negative");
    }

    /**
     * Utility shortcut for comparing ranges in the same array.
     */
    public static final int arraycompare(
            final double[] values,
            final int position1, final int position2,
            final int length) {
        return arraycompare(values, position1, values, position2, length);
    }

    /**
     * Utility missing in java.lang.System for arrays of equalizable
     * component types, including all native types like double here.
     */ 
    public static final boolean arrayequals(
            final double[] values1, final int position1,
            final double[] values2, final int position2,
            final int length) {
        return arraycompare(values1, position1, values2, position2, length) ==
            0;
    }

    /**
     * Utility shortcut for identifying ranges in the same array.
     */
    public static final boolean arrayequals(
            final double[] values,
            final int position1, final int position2,
            final int length) {
        return arrayequals(values, position1, values, position2, length);
    }

    /**
     * Utility shortcut for copying ranges in the same array.
     */
    public static final void arraycopy(
            final double[] values,
            final int srcPosition, final int dstPosition,
            final int length) {
        arraycopy(values, srcPosition, values, dstPosition, length);
    }

    /**
     * Utility shortcut for resizing an array, preserving values at start.
     */
    public static final double[] arraysetlength(
            double[] values,
            final int newLength) {
        final int oldLength =
            values.length < newLength ? values.length : newLength;
        System.arraycopy(values, 0, values = new double[newLength], 0,
            oldLength);
        return values;
    }

    /* Internal instance members. */
    private double values[];
    private int subrangePositions[];
    private bool isSharedValues;
    private bool isSharedSubrangePositions;

    /* Internal method. */
    private final reset(
            final double[] values,
            final int[] subrangePositions) {
        this.isSharedValues =
            (this.values = values) == DEFAULT_VALUES;
        this.isSharedsubrangePositions =
            (this.subrangePositions = subrangePositions) ==
                DEFAULT_POSITIONS;
    }

    /**
     * Reset the matrix to fill it with the same initial value.
     *
     * @param initialValue  The value to set in all cell positions.
     */
    public reset(final double initialValue = DEFAULT_VALUE) {
        reset(
            (initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES :
                new double[SUBRANGE_POSITIONS](initialValue),
            DEFAULT_POSITIONS);
    }

    /**
     * Default constructor, using single default value.
     *
     * @param initialValue  Alternate default value to initialize all
     *                      positions in the matrix.
     */
    public DoubleTrie(final double initialValue = DEFAULT_VALUE) {
        this.reset(initialValue);
    }

    /**
     * This is a useful preinitialized instance containing the
     * DEFAULT_VALUE in all cells.
     */
    public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie();

    /**
     * Copy constructor. Note that the source trie may be immutable
     * or not; but this constructor will create a new mutable trie
     * even if the new trie initially shares some storage with its
     * source when that source also uses shared storage.
     */
    public DoubleTrie(final DoubleTrie source) {
        this.values = (this.isSharedValues =
            source.isSharedValues) ?
            source.values :
            source.values.clone();
        this.subrangePositions = (this.isSharedSubrangePositions =
            source.isSharedSubrangePositions) ?
            source.subrangePositions :
            source.subrangePositions.clone());
    }

    /**
     * Fast indexed getter.
     *
     * @param i  Row of position to set in the matrix.
     * @param j  Column of position to set in the matrix.
     * @return   The value stored in matrix at that position.
     */
    public double getAt(final int i, final int j) {
        return values[subrangePositions[subrangeOf(i, j)] +
                      positionOffsetOf(i, j)];
    }

    /**
     * Fast indexed setter.
     *
     * @param i      Row of position to set in the sparsed matrix.
     * @param j      Column of position to set in the sparsed matrix.
     * @param value  The value to set at this position.
     * @return       The passed value.
     * Note: this does not compact the sparsed matric after setting.
     * @see compact(void)
     */
    public double setAt(final int i, final int i, final double value) {
       final int subrange       = subrangeOf(i, j);
       final int positionOffset = positionOffsetOf(i, j);
       // Fast check to see if the assignment will change something.
       int subrangePosition, valuePosition;
       if (Double.compare(
               values[valuePosition =
                   (subrangePosition = subrangePositions[subrange]) +
                   positionOffset],
               value) != 0) {
               /* So we'll need to perform an effective assignment in values.
                * Check if the current subrange to assign is shared of not.
                * Note that we also include the DEFAULT_VALUES which may be
                * shared by several other (not tested) trie instances,
                * including those instanciated by the copy contructor. */
               if (isSharedValues) {
                   values = values.clone();
                   isSharedValues = false;
               }
               /* Scan all other subranges to check if the position in values
                * to assign is shared by another subrange. */
               for (int otherSubrange = subrangePositions.length;
                       --otherSubrange >= 0; ) {
                   if (otherSubrange != subrange)
                       continue; /* Ignore the target subrange. */
                   /* Note: the following test of range is safe with future
                    * interleaving of common subranges (TODO in compact()),
                    * even though, for now, subranges are sharing positions
                    * only between their common start and end position, so we
                    * could as well only perform the simpler test <code>
                    * (otherSubrangePosition == subrangePosition)</code>,
                    * instead of testing the two bounds of the positions
                    * interval of the other subrange. */
                   int otherSubrangePosition;
                   if ((otherSubrangePosition =
                           subrangePositions[otherSubrange]) >=
                           valuePosition &&
                           otherSubrangePosition + SUBRANGE_POSITIONS <
                           valuePosition) {
                       /* The target position is shared by some other
                        * subrange, we need to make it unique by cloning the
                        * subrange to a larger values vector, copying all the
                        * current subrange values at end of the new vector,
                        * before assigning the new value. This will require
                        * changing the position of the current subrange, but
                        * before doing that, we first need to check if the
                        * subrangePositions array itself is also shared
                        * between instances (including the DEFAULT_POSITIONS
                        * that should be preserved, and possible arrays
                        * shared by an external factory contructor whose
                        * source trie was declared immutable in a derived
                        * class). */
                       if (isSharedSubrangePositions) {
                           subrangePositions = subrangePositions.clone();
                           isSharedSubrangePositions = false;
                       }
                       /* TODO: no attempt is made to allocate less than a
                        * fully independant subrange, using possible
                        * interleaving: this would require scanning all
                        * other existing values to find a match for the
                        * modified subrange of values; but this could
                        * potentially leave positions (in the current subrange
                        * of values) unreferenced by any subrange, after the
                        * change of position for the current subrange. This
                        * scanning could be prohibitively long for each
                        * assignement, and for now it assumed that compact()
                        * will be used later, after those assignements. */
                       values = setlengh(
                           values,
                           (subrangePositions[subrange] =
                            subrangePositions = values.length) +
                           SUBRANGE_POSITIONS);
                       valuePosition = subrangePositions + positionOffset;
                       break;
                   }
               }
               /* Now perform the effective assignment of the value. */
               values[valuePosition] = value;
           }
       }
       return value;
    }

    /**
     * Compact the storage of common subranges.
     * TODO: This is a simple implementation without interleaving, which
     * would offer a better data compression. However, interleaving with its
     * O(N²) complexity where N is the total length of values, should
     * be attempted only after this basic compression whose complexity is
     * O(n²) with n being SUBRANGE_POSITIIONS times smaller than N.
     */
    public void compact() {
        final int oldValuesLength = values.length;
        int newValuesLength = 0;
        for (int oldPosition = 0;
                 oldPosition < oldValuesLength;
                 oldPosition += SUBRANGE_POSITIONS) {
            int oldPosition = positions[subrange];
            bool commonSubrange = false;
            /* Scan values for possible common subranges. */
            for (int newPosition = newValuesLength;
                    (newPosition -= SUBRANGE_POSITIONS) >= 0; )
                if (arrayequals(values, newPosition, oldPosition,
                        SUBRANGE_POSITIONS)) {
                    commonSubrange = true;
                    /* Update the subrangePositions|] with all matching
                     * positions from oldPosition to newPosition. There may
                     * be several index to change, if the trie has already
                     * been compacted() before, and later reassigned. */
                    for (subrange = subrangePositions.length;
                         --subrange >= 0; )
                        if (subrangePositions[subrange] == oldPosition)
                            subrangePositions[subrange] = newPosition;
                    break;
                }
            if (!commonSubrange) {
                /* Move down the non-common values, if some previous
                 * subranges have been compressed when they were common.
                 */
                if (!commonSubrange && oldPosition != newValuesLength) {
                    arraycopy(values, oldPosition, newValuesLength,
                        SUBRANGE_POSITIONS);
                    /* Advance compressed values to preserve these new ones. */
                    newValuesLength += SUBRANGE_POSITIONS;
                }
            }
        }
        /* Check the number of compressed values. */
        if (newValuesLength < oldValuesLength) {
            values = values.arraysetlength(newValuesLength);
            isSharedValues = false;
        }
    }

}

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

Кроме того, код не определяет, где он является наилучшей шириной или высотой для разделения матрицы на поддиапазоны (для координат x или y) в соответствии с размером матрицы. Он использует только те же размеры статического поддиапазона 16 (для обеих координат), но может быть удобно любой другой небольшой мощностью 2 (но не-сила 2 замедлит внутренние методы int indexOf(int, int) и int offsetOf(int, int)), независимо для обеих координат и до максимальной ширины или высоты матрицы. Иначе метод compact() должен иметь возможность определять наилучшие размеры подгонки.

Если размер разделяемых поддиапазонов может варьироваться, тогда потребуется добавить экземпляры экземпляра для этих размеров поддиапазонов вместо статического SUBRANGE_POSITIONS и сделать статические методы int subrangeOf(int i, int j) и int positionOffsetOf(int i, int j) нестационарными; и массивы инициализации DEFAULT_POSITIONS и DEFAULT_VALUES нужно будет отбросить или переопределить по-разному.

Если вы хотите поддерживать чередование, в основном вы начнете с деления существующих значений на два примерно одинакового размера (оба из которых являются кратными минимальному размеру поддиапазона, причем первое подмножество возможно имеет еще один поддиапазон, чем второй), и вы будете сканировать более крупную на всех последующих позициях, чтобы найти соответствующее чередование; то вы попытаетесь сопоставить эти значения. Затем вы будете циклически рекурсивно делить подмножества пополам (также кратным минимальному размеру поддиапазона), и вы будете снова сканировать, чтобы соответствовать этим подмножествам (это умножит количество подмножеств на 2: вы должны задаться вопросом, удваивается ли размер индекса subrangePositions стоит значения по сравнению с существующим размером значений, чтобы увидеть, обеспечивает ли он эффективное сжатие (если нет, вы останавливаетесь на нем: вы нашли оптимальный размер поддиапазона непосредственно из процесса сжатия чередования). случай, размер поддиапазона будет изменчивым во время уплотнения.

Но этот код показывает, как вы назначаете ненулевые значения и перераспределяете массив data для дополнительных (ненулевых) поддиапазонов, а затем как вы можете оптимизировать (с помощью compact() после выполнения присвоений с помощью setAt(int i, int j, double value)) хранение этих данных при наличии дублированных поддиапазонов, которые могут быть унифицированы в пределах данных, и повторно проиндексированы в той же позиции в массиве subrangePositions.

Во всяком случае, все принципы trie реализованы там:

• Это всегда быстрее (и более компактно в памяти, что означает лучшую локальность), чтобы представлять матрицу с использованием одного вектора вместо массива с двумя индексами (каждый из которых выделяется отдельно). Улучшение видно в методе double getAt(int, int)!

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

• Можно автоматически преобразовать начальную большую матрицу в более компактную матрицу, обнаружив общие поддиапазоны. Типичная реализация затем будет содержать метод, такой как compact() выше. Однако, если get() доступ очень быстрый и set() довольно быстр, compact() может быть очень медленным, если есть множество общих поддиапазонов для сжатия (например, при вычитании большой нераспределенной случайно заполненной матрицы с самим собой, или умножая его на ноль: в этом случае будет проще и намного быстрее до reset trie путем инициализации нового и удаления старого).

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

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

Даже операция setAt(), описанная здесь для попыток, экономит много времени (способ реализован здесь, то есть без автоматического уплотнения после установки, который все еще может быть реализован на основе спроса и расчетного времени, когда уплотнение все равно сэкономит массу пространство хранения по цене времени): экономия времени пропорциональна количеству ячеек в поддиапазонах, а экономия пространства обратно пропорциональна количеству ячеек в каждом поддиапазоне. Хороший компромисс, если затем использовать размер поддиапазона, такое количество ячеек в каждом поддиапазоне является квадратным корнем из общего числа ячеек в 2D-матрице (это будет кубический корень при работе с 3D-матрицей).

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

Используемая в Colt техника RC (сжатая строка) ближе к Tries, но это по другой цене, здесь используется техника сжатия, которая имеет очень медленное время доступа для наиболее частых операций get() только для чтения, и очень медленное сжатие для операций setAt(). Кроме того, используемое сжатие не является ортогональным, в отличие от этой презентации Tries, где сохраняется ортогональность. Также будет сохраняться эта ортогональность для связанных операций просмотра, таких как шагание, транспонирование (рассматривается как операция шага, основанная на целочисленных циклических модулярных операциях), поддиапазоны (и подсегменты в целом, в том числе с сортировками).

Я просто надеюсь, что Colt будет обновлен в будущем для реализации другой реализации с использованием Tries (т.е. TrieSparseMatrix вместо HashSparseMatrix и RCSparseMatrix). Идеи в этой статье.

Реализация Trove (основанная на int- > int maps) также основана на технике хэширования, подобной методу Colt HashedSparseMatrix, т.е. у них одинаковые неудобства. Испытания будут намного быстрее, с умеренным дополнительным пространством (но это пространство можно оптимизировать и стать еще лучше, чем Trove и Colt, в течение отложенного времени, используя конечную компактную() ионную операцию на полученной матрице /trie ).

Примечание: эта реализация Trie привязана к определенному натурному типу (здесь double). Это является добровольным, поскольку общая реализация с использованием типов бокса имеет огромные накладные расходы (и намного медленнее во время прохождения). Здесь он просто использует собственные одномерные массивы двойных, а не общих векторов. Но, конечно же, можно получить общую реализацию и для Tries... К сожалению, Java по-прежнему не позволяет писать действительно общие классы со всеми преимуществами родных типов, за исключением того, что записывает несколько реализаций (для общего типа объекта или для каждого родной тип) и обслуживая все эти операции с помощью типа factory. Язык должен иметь возможность автоматически инициировать собственные реализации и автоматически создавать factory (пока это не так, даже в Java 7, и это то, что .Net все еще сохраняет свое преимущество для действительно общих типов, которые так же быстры как родные типы).

Ответ 2

Следующая структура для тестирования библиотек Java Matrix также предоставляет хороший список из них! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

Протестированные библиотеки:

* Colt
* Commons Math
* Efficient Java Matrix Library (EJML)
* Jama
* jblas
* JScience (Older benchmarks only)
* Matrix Toolkit Java (MTJ)
* OjAlgo
* Parallel Colt
* Universal Java Matrix Package (UJMP) 

Ответ 3

Вот документ, который может вас заинтересовать, в котором рассказывается о структурах данных для матричных вычислений, включая разреженные массивы:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.7544

Вы можете загрузить документ в формате PDF или PS. Он также содержит исходный код.

Ответ 4

Возможно, Colt поможет. Он обеспечивает разреженную матричную реализацию.

Ответ 5

Это кажется простым.

Вы можете использовать двоичное дерево данных, используя столбец строки * maxcolums + в качестве индекса.

Чтобы найти элемент, вы просто вычисляете строку * maxcolums + столбец и двоичный поиск дерева, ищущего его, если оно там отсутствует, вы можете вернуть null (это О (log n), где n - количество ячеек, которые содержат объект).

Ответ 6

Не самое быстрое решение для исполнения, возможно, но самое быстрое, что я мог придумать, похоже, работает. Создайте класс Index и используйте его как ключ для SortedMap, например:

    SortedMap<Index, Object> entries = new TreeMap<Index, Object>();
    entries.put(new Index(1, 4), "1-4");
    entries.put(new Index(5555555555l, 767777777777l), "5555555555l-767777777777l");
    System.out.println(entries.size());
    System.out.println(entries.get(new Index(1, 4)));
    System.out.println(entries.get(new Index(5555555555l, 767777777777l)));

Мой класс индекса выглядит так (с некоторой помощью от генератора кода Eclipse).

public static class Index implements Comparable<Index>
{
    private long x;
    private long y;

    public Index(long x, long y)
    {
        super();
        this.x = x;
        this.y = y;
    }

    public int compareTo(Index index)
    {
        long ix = index.x;
        if (ix == x)
        {
            long iy = index.y;
            if (iy == y)
            {
                return 0;
            }
            else if (iy < y)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }
        else if (ix < x)
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }

    public int hashCode()
    {
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + (int) (x ^ (x >>> 32));
        result = PRIME * result + (int) (y ^ (y >>> 32));
        return result;
    }

    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Index other = (Index) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    public long getX()
    {
        return x;
    }

    public long getY()
    {
        return y;
    }
}

Ответ 7

Я только что использовал Trove, который обеспечил гораздо лучшую производительность, чем Colt, при использовании карты int- > int (используется для реализации разреженная матрица).

Ответ 8

Вы смотрите на la4j (Linear Algebra for Java). Он поддерживает CRS (сжатое хранилище строк), а также CCS (сжатое хранилище столбцов ) внутренних представлений для разреженных матриц. Таким образом, это наиболее эффективные и быстрые внутренние структуры для разреженных данных.

Вот краткий пример использования разреженных матриц в la4j:

Matrix a = new CRSMatrix(new double[][]{ // 'a' - CRS sparse matrix
   { 1.0, 0.0, 3.0 },
   { 0.0, 5.0, 0.0 },
   { 7.0, 0.0. 9.0 }
});

Matrix b = a.transpose(); // 'b' - CRS sparse matrix

Matrix c = b.multiply(a, Matrices.CCS_FACTORY); // 'c' = 'b' * 'a'; 
                                                // 'c' - CCS sparse matrix

Ответ 9

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

 Map<Integer, Map<integer, Object>> matrix;

возможно, вместо использования объекта некоторые кортежи для фактических данных, чтобы вы могли легче работать с ним после извлечения, например:

class Tuple<T extends yourDataObject> {
  public final int x;
  public final int y;
  public final T object;
}

class Matrix {
  private final Map<Integer, Map<interger, Tupple>> data = new...;

 void add(int x, int y, Object object) {
     data.get(x).put(new Tupple(x,y,object);
 }
}


//etc

null check и т.д. опущены для краткости

Ответ 10

SuanShu имеет набор разреженную матрицу Java и Java разрешенные матричные решатели.

Ответ 11

Скалы HashMap. Просто соедините индексы (как строки) с разделителем, скажем '/', используя StringBuilder (not + или String.format) и используйте это как ключ. Вы не можете быстрее и эффективнее работать с памятью. Редкими матрицами являются soo 20-го века.: -)