Опуская некоторые второстепенные подробности, имеется
большая разреженная 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 (то есть индексы, конечно, можно пересчитывать внутри, приводя к неотрицательному виду, но это лишний гемор и вычисления).
Простой
