Ответ 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 все еще сохраняет свое преимущество для действительно общих типов, которые так же быстры как родные типы).