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

Опуская некоторые второстепенные подробности, имеется большая разреженная 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 (то есть индексы, конечно, можно пересчитывать внутри, приводя к неотрицательному виду, но это лишний гемор и вычисления).
  • Вопрос задан
  • 611 просмотров
Пригласить эксперта
Ответы на вопрос 2
Adamos
@Adamos
> Массив массивов. Жирный минус: непонятно, как искать и обходить занятые элементы? Организовать полный цикл со стопицциот индексами и проверками на undefined? Оно искать будет до всемирного потопа.

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

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

Войти через центр авторизации
Похожие вопросы