Разреженные массивы, созданные с помощью хэш-карт, очень неэффективны для часто читаемых данных. Наиболее эффективные реализации используют Trie, который позволяет получить доступ к одному вектору, где сегменты распределены.
Trie может вычислить, присутствует ли элемент в таблице, выполняя только индексирование ДВУ массива только для чтения, чтобы получить эффективную позицию, где хранится элемент, или узнать, отсутствует ли он в базовом хранилище.
Он также может предоставить позицию по умолчанию в резервном хранилище для значения по умолчанию для разреженного массива, так что вам не нужен ЛЮБОЙ тест для возвращаемого индекса, потому что Trie гарантирует, что все возможные исходные индексы будут отображаться по крайней мере в положение по умолчанию в резервном хранилище (где вы часто будете хранить ноль, или пустую строку, или нулевой объект).
Существуют реализации, которые поддерживают быстро обновляемые Tries, с условной операцией «compact ()», чтобы оптимизировать размер резервного хранилища в конце нескольких операций. Попытки выполняются НАМНОГО быстрее, чем хеш-карты, потому что они не нуждаются ни в какой сложной функции хеширования и не должны обрабатывать коллизии при чтении (в случае хеш-карт у вас есть коллизия ОБА для чтения и записи, для этого требуется цикл для перехода к следующая кандидатская позиция и проверка каждого из них для сравнения индекса эффективного источника ...)
Кроме того, Java Hashmaps может индексировать только объекты, и создание объекта Integer для каждого хешированного исходного индекса (создание этого объекта будет необходимо для каждого чтения, а не только записи) является дорогостоящим с точки зрения операций с памятью, поскольку оно подчеркивает сборщик мусора.
Я действительно надеялся, что JRE включит IntegerTrieMap в качестве реализации по умолчанию для медленного HashMap или LongTrieMap в качестве реализации по умолчанию для еще более медленного HashMap ... Но это все еще не так.
Вы можете спросить, что такое Три?
Это просто небольшой массив целых чисел (в меньшем диапазоне, чем полный диапазон координат для вашей матрицы), который позволяет отображать координаты в целочисленную позицию в векторе.
Например, предположим, что вы хотите матрицу 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's 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 стоит значения по сравнению с существующим размером значений, чтобы увидеть, предлагает ли он эффективное сжатие (если нет, остановитесь: вы нашли оптимальный размер поддиапазона непосредственно из процесса сжатия с перемежением). case; размер поддиапазона будет изменяемым во время сжатия.
Но этот код показывает, как вы назначаете ненулевые значения и перераспределяете массив data для дополнительных (ненулевых) поддиапазонов, а затем, как вы можете оптимизировать (с помощью compact() после выполнения назначений с помощью * 1054). * метод) хранение этих данных при наличии дублированных поддиапазонов, которые могут быть объединены в данных и переиндексированы в той же позиции в массиве subrangePositions.
В любом случае, здесь реализованы все принципы дерева:
Всегда быстрее (и более компактно в памяти, что означает лучшую локальность) представлять матрицу, используя один вектор вместо массива массивов с двойным индексом (каждый из которых выделяется отдельно). Улучшение видно по методу double getAt(int, int)!
Вы экономите много места, но при назначении значений может потребоваться время для перераспределения новых поддиапазонов. По этой причине поддиапазоны не должны быть слишком маленькими, иначе перераспределения будут происходить слишком часто для настройки вашей матрицы.
Можно автоматически преобразовать исходную большую матрицу в более компактную матрицу путем обнаружения общих поддиапазонов. Типичная реализация будет тогда содержать метод, такой как compact() выше. Однако, если доступ get () очень быстрый, а set () довольно быстрый, compact () может быть очень медленным, если нужно сжать много общих поддиапазонов (например, при выделении из себя большой не разреженной случайно заполненной матрицы) или умножив его на ноль: в этом случае будет проще и намного быстрее сбросить значение дерева путем создания нового экземпляра и удаления старого).
Общие поддиапазоны используют общее хранилище данных, поэтому эти общие данные должны быть доступны только для чтения. Если вам нужно изменить одно значение без изменения остальной матрицы, вы должны сначала убедиться, что оно указывается только один раз в индексе subrangePositions. В противном случае вам потребуется выделить новый поддиапазон в любом месте (удобно в конце) вектора values, а затем сохранить положение этого нового поддиапазона в индексе subrangePositions.
Обратите внимание, что универсальная библиотека Colt, хотя она и очень хороша, не так хороша при работе с разреженной матрицей, потому что она использует технику хеширования (или сжатия строк), которая пока не реализует поддержку попыток, несмотря на то, что Это отличная оптимизация, которая экономит пространство и и экономит время, особенно для наиболее частых операций getAt ().
Даже описанная здесь операция setAt () для попыток экономит много времени (здесь реализован способ, т. Е. Без автоматического уплотнения после установки, которое все еще может быть реализовано на основе спроса и предполагаемого времени, когда сжатие все равно сохранит много пространство для хранения по цене времени): экономия времени пропорциональна количеству ячеек в поддиапазонах, а экономия пространства обратно пропорциональна количеству ячеек в поддиапазоне. Хороший компромисс, если затем использовать размер поддиапазона, например, количество ячеек на поддиапазон, является квадратным корнем от общего числа ячеек в 2D-матрице (это будет кубический корень при работе с 3D-матрицей).
Техника хеширования, используемая в реализациях разреженных матриц Colt, имеет неудобство, заключающееся в том, что они увеличивают объем памяти и сокращают время доступа из-за возможных коллизий. Попытки могут избежать всех коллизий, а затем могут гарантировать сохранение линейного O (n) времени до O (1) времени в худших случаях, где (n) - количество возможных коллизий (которое в случае разреженной матрицы может быть вплоть до количества ячеек с ненулевым значением в матрице, т.е. до общего числа размеров матрицы, умноженных на коэффициент, пропорциональный коэффициенту заполнения хеширования, для не разреженной, то есть полной матрицы).
Техника RC (сжатие строк), используемая в Colt, ближе к Tries, но это за другую цену, здесь используется техника сжатия, которая имеет очень медленное время доступа для наиболее частых операций get () только для чтения, и очень медленное сжатие для операций setAt (). Кроме того, используемое сжатие не является ортогональным, в отличие от этого представления Tries, где сохраняется ортогональность. Попытки также сохранят эту ортогональность для связанных операций просмотра, таких как шагание, транспозиция (рассматриваемая как шаговая операция на основе целочисленных циклических модульных операций), поддиапазон (и подвыборы в целом, в том числе с сортировочными видами).
Я просто надеюсь, что Colt будет обновлен в будущем, чтобы реализовать другую реализацию с использованием Tries (то есть TrieSparseMatrix вместо просто HashSparseMatrix и RCSparseMatrix). Идеи в этой статье.
Реализация Trove (основанная на картах int-> int) также основана на методах хеширования, аналогичных HastSparseMatrix Colt, т.е. они имеют то же неудобство. Попытки будут выполняться намного быстрее, с умеренным потреблением дополнительного пространства (но это пространство может быть оптимизировано и может стать даже лучше, чем Trove и Colt, за отложенное время, используя последнюю операцию compact () ion для получаемой матрицы / trie).
Примечание: эта реализация Trie привязана к определенному нативному типу (здесь double). Это является добровольным, потому что общая реализация, использующая типы бокса, имеет огромные накладные расходы (и намного медленнее во время доступа). Здесь он просто использует собственные одномерные массивы типа double, а не общий Vector. Но, безусловно, можно получить обобщенную реализацию и для Tries ... К сожалению, Java все еще не позволяет писать действительно универсальные классы со всеми преимуществами нативных типов, за исключением написания нескольких реализаций (для универсального типа Object или для каждого родной тип) и обслуживает все эти операции через фабрику типов. Язык должен иметь возможность автоматически создавать собственные реализации и автоматически создавать фабрику (сейчас это не так даже в Java 7, и это то, что .Net по-прежнему сохраняет свои преимущества для действительно универсальных типов, которые так же быстры, как и собственные). типов).