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

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

С одной стороны, требуется иметь возможность быстрого доступа к элементу по индексу (a[i][j][k]). С дугой стороны, нужна возможность быстро обойти все непустые элементы и что-то с ними сделать (условно говоря, a.forEach(...)). Скорость очень важна.

Элемент матрицы - объект, поэтому типизированные массивы заведомо отпадают.

Вопрос в структуре данных. На текущий момент у меня есть такие идеи:

1. Массив массивов. Общий принцип упрощенно демонстрирует код:
var a = [];

function set (i, j, k, value) {
	if (a[i] === undefined) a[i] = [];
	if (a[i][j] === undefined) a[i][j] = [];
	a[i][j][k] = value;
	return a[i][j][k];
}

function get (i, j, k) {
	return (a[i] === undefined || a[i][j] === undefined) ? undefined : a[i][j][k];
}

Жирный минус: непонятно, как искать и обходить занятые элементы? Организовать полный цикл со стопицциот индексами и проверками на undefined? Оно искать будет до всемирного потопа.

2. Хэш
var a = {};

function set (i, j, k, value) {
	var key = i + '-' + j + '-' + k;
	return (a[key] = value);
}

function get (i, j, k) {
	var key = i + '-' + j + '-' + k;
	return a[key];
}

Минус: Ну наверное строки это медленно. Хотя, как я узнал недавно, V8 конкатенируемые строки в реальности не конкатенирует, а организует им внутренний объект со ссылками на куски.

3. Комбинация пунктов 1 и 2
То есть параллельно держать обе структуры данных и в каждой ситуации обращаться к той, какая удобнее. Поскольку конечные элементы это объекты, в массивах будут только ссылки. То есть изменение элементов через первую структуру будет видно и через второую.
Минус: оверхед по памяти и времени на построение.

4. Map
https://developer.mozilla.org/en/docs/Web/JavaScri...
Минусы: во-первых, неполная кроссбраузерность, во-вторых, эта структура не дает ничего особо нового в сравнении с самописным хэшем.
В Map в качестве ключей можно использовать объекты, но идентификация идет не по содержимому, а по значению ссылки! То есть если я что-то добавил по ключу { i: 1, j: 2, k:-3 }, то достать обратно это можно лишь передав этот же самый объект. Если сформировать новую тройку индексов, пусть и численно равную старой, вернется undefined.
Выходит, что нужно делать ключами те же самые составные строки или что-то ещё наподобии. То есть никакого профита - ну кроме синтаксического сахарка.

update
Упустил из вида очень важный момент - индексы могут быть и отрицательные тоже!
А поскольку в JS индексы массивов только положительные, это дополнительно снижает привлекательность вариантов 1 и 3 (то есть индексы, конечно, можно пересчитывать внутри, приводя к неотрицательному виду, но это лишний гемор и вычисления).
  • Вопрос задан
  • 666 просмотров
Пригласить эксперта
Ответы на вопрос 2
Adamos
@Adamos
> Массив массивов. Жирный минус: непонятно, как искать и обходить занятые элементы? Организовать полный цикл со стопицциот индексами и проверками на undefined? Оно искать будет до всемирного потопа.

Вообще-то проход
for(var index in array) { ... }
никаких undefined не выдает, будут перебираться только реально существующие ключи и значения. Никакой карты или хэшей здесь явно не требуется - это все реализовано в самом языке.
Ответ написан
Без учета изменений можно создать матрицу из вложенных сортированных массивов , а них хранить индекс и ссылку на массив или значение. Значением может быть объект или индекс объекта в отдельном списке всех объектов. Что-то читал давно про asm js. Может пригодится тут. С учетом изменений можно иметь вторую матрицу , в которой будут происходить изменения. На заднем фоне можно их склеивать. Вроде есть какие-то background workers. При поиске и обходе нужно учитывать две матрицы. Скорее всего есть готовые реализации под Вашу задачу на других языках.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

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