Comments 17
//....
return nstd.Structure.sort((a, b) => {
if (a.lkey > b.lkey) return 1
if (a.lkey < b.lkey) return -1
return 0
})
// better replace with
return nstd.Structure.sort((a, b) => a.lkey - b.lkey )
уверен что будут и более веские замечания.
Это какой-то ужас, а не код...
Вот примеры того, как код писать нельзя:
_nestedsets.removeItem = function (itemId) {
// ...
for (var i = 0; i < nstd.Structure.length; i++) {
if (nstd.Structure[i].itemId === itemId) {
var childs = nstd.getChilds(nstd.Structure[i]._id)
// ...
_nestedsets.getChilds = function (nodeId, depth) {
var nstd = this
var parentNode = nstd.getNode(nodeId)
_nestedsets.getNode = function (nodeId, asCopy) {
var nstd = this
var selectedNode = nstd.Structure.filter(n => n._id === nodeId)Тут в массиве нод по индексу берётся _id, после чего сразу же в том же самом массиве выполняется по этому _id поиск...
var childs = nstd.getChilds(nstd.Structure[i]._id)
for (var j = 0; j < childs.length; j++) {
nstd.removeNode(childs[j]._id)
}removeNode удаляет всё поддерево нод. Зачем тут вообще цикл и почему нельзя было написать просто nstd.removeNode(nstd.Structure[i]._id)?
На пустом месте оквадратили линейный алгоритм!
var childs = nstd.getNodes().filter(n => {
return n.lkey >= parentNode.lkey && n.rkey <= parentNode.rkey && nodeId !== n._id && (depth === undefined ? true : n.depth <= (parentNode.depth + depth))
})
// ...
childs.sort((a, b) => {
if (a.lkey > b.lkey) return 1
if (a.lkey < b.lkey) return -1
return 0
})getNodes() возвращает уже упорядоченный массив. Зачем его сортировать ещё раз по тому же самому свойству? С каких пор фильтрация сбивает сортировку?
var results = []
// ...
.map(n => {
n.data = nstd.Data[n.itemId]
results.push(n)
})
childs = resultsНу а .map(n => nstd.Data[n.itemId]) не судьба написать было? Зачем тут вообще массив results?
И ещё вопрос: зачем использовать метод .map в качестве заменителя цикла for-of, если у массивов есть метод .forEach для тех же целей?
И ещё один пример как не надо писать в том же самом месте, что и прошлые два.
if (childs.length > 0) {
var results = []
childs.sort((a, b) => {
if (a.lkey > b.lkey) return 1
if (a.lkey < b.lkey) return -1
return 0
}).map(n => {
n.data = nstd.Data[n.itemId]
results.push(n)
})
childs = results
}Зачем тут условный оператор? Что sort, что map на пустом массиве прекрасно работают. Если это была попытка оптимизации — то экономить надо в первую очередь на асимптотике, во вторую очередь на лишних массивах, и лишь в последнюю очередь на спичках.
Ну и последнее
var nstd = thisЗачем так делать в 2020м году? В стрелочных функциях this не "теряется", и его больше не требуется подобным способом "беречь".
Не говоря уже о том, что у вас уже есть переменная _nestedsets для тех же целей.
По поводу удаление ветки узлов, да вы абсолютно правы, внес изменения.
С сортировкой опять же да, лишние сортировки не нужны, убрал.
Что касается .map(n => nstd.Data[n.itemId]) позвольте не согласиться, эта конструкция вернет элемент из свйоства Data, а там храняться данные, а не узлы, мне же необходима информация по узлам. В качестве свойства data для каждого узла (как дополнение) я указывал элемент из свойства Data, но вся информация об узле также осталась.
О использовании map вместо forEach, разница методов в том, что один вернет новый массив, а второй вернет undefined. Если говорить о скорости, то я видел тесты, где map значительно быстрее forEach. Возможно не прав, если так — поправьте.
var nstd = this
Да, полностью согласен, не нужно так
Переписал все на Typescript.
github.com/orxtime/nestedsetsjs/blob/typescript/src/nestedsets.ts
Буду ждать от вас новых комментариев, спасибо.
Что касается .map(n => nstd.Data[n.itemId]) позвольте не согласиться, эта конструкция вернет элемент из свйоства Data, а там храняться данные, а не узлы, мне же необходима информация по узлам
В таком случае вам тем более не нужен массив results, поскольку его содержимое совпадает с содержимым childs.
О использовании map вместо forEach, разница методов в том, что один вернет новый массив, а второй вернет undefined. Если говорить о скорости, то я видел тесты, где map значительно быстрее forEach.
Это весьма странная информация. Мне почему-то кажется, в тех тестах сравнивался одиночный map и комбинация forEach + push.
По поводу Map vs forEach: проводил такой эксперимент
const myAwesomeArray = Array.from({length: 1000}, (e,i) => i)
console.time("forEachTest")
myAwesomeArray.forEach(x => (x + x) * 10000000000)
console.timeEnd("forEachTest")
console.time("mapTest")
myAwesomeArray.map(x => (x + x) * 10000000000)
console.timeEnd("mapTest")
Результаты такие:
forEachTest: 0.123ms
mapTest: 0.069ms
forEachTest: 0.122ms
mapTest: 0.078ms
forEachTest: 0.127ms
mapTest: 0.068ms
Ну а вот мой результат:
forEachTest: 0.04296875 ms
mapTest: 0.05078125 ms
forEachTest: 0.052978515625 ms
mapTest: 0.055908203125 ms
forEachTest: 0.053955078125 ms
mapTest: 0.057861328125 ms
Ищите проблему в окружении. Может, где-то полифил неоптимальный стоит, или наоборот — нестандартный. Или транспайлер начудил. Или всё проще, и GC прибирает за прошлым map как раз во время forEach.
Что же до вашего кода на Typescript — у вас там лишние классы NestedSetItem, NestedSetNode, NestedSetRootNode, NestedSetEmptyNode и NesteSetError (вместо них проще использовать литералы объектов, точно так же как вы на js делали). Кроме того, интерфейс INestedSet тоже лишний.
Ну и какой нафиг module.exports? Проще всего export class NestedSet { ... } написать. Ну а если так важно экспортировать именно объект — конструкция export = new NestedSet() в помощь. Хотя в таком случае лучше вообще отказаться от класса и экспортировать отдельные функции:
export function removeItem (itemId: number) {
// ...
}
export function addNode (targetNodeId: number, itemId: number) {
// ...
}
childs.sort((a, b) => {
if (a.lkey > b.lkey) return 1
if (a.lkey < b.lkey) return -1
return 0
})Пять копеек от меня:
childs.sort((a, b)=>(+(a.lkey>b.lkey)-(a.lkey<b.lkey))):)
Возможно это можно было бы использовать как хранилище на клиентской стороне (но это уже догадки). Из БД подгружать данные на клиент и тот уже редактирует дерево, не нагружая при этом сервер. А когда редактирование завершено — записывает данные в БД. Тут конечно вопрос синхронизации с сервером.
А не проще ли в таком случае перейти от nested sets к нормальному древовидному виду, внести там изменения — и снова построить nested sets? Быстрее так точно:
function nestedSetsToTree(items) {
items.sort(...);
let root = { rkey: +Infinity, data: { children: [] } };
let stack = [ root ];
let top = () => stack[stack.length-1];
for (let { lkey, rkey, ...data } of items) {
data = { ...data, children: [] };
while (lkey >= top().rkey) stack.pop();
top().data.children.push(data);
stack.push({ rkey, data });
}
return root.data.children;
}
function treeToNestedSets(roots) {
let result = [];
let nextKey = 0;
for (let root in roots) visit(root);
return result;
function visit({children, ...data}) {
let item = { lkey: nextKey++, ...data };
result.push(item);
for (let child in children) visit(child);
item.rkey = nextKey++;
}
}
const maxId = Math.max(...this.Structure.map(o => o._id)) || 0Если будет слишком много элементов, случится Maximum call stack size exceeded
reduce будет понадежнее, хотя и медленнее
Но у вас уже используется map, и с учетом этого reduce будет уже быстрее чем map+rest arguments
var arr = Array.from(Array(100000), () => ({_id: Math.round(Math.random() * 10000)}));
console.time('reduce');// 1180ms
for(var i = 0; i < 1000; i++)
arr.reduce((a,{_id}) => (a > _id ? a : _id), -Infinity)
console.timeEnd('reduce');
console.time('rest args');// 1748ms
for(var i = 0; i < 1000; i++)
Math.max(...arr.map(x => x._id))
console.timeEnd('rest args');
Также || 0 выглядит как ненужная перестраховка
Если элементов не будет, то вы получите -Infinity, и этот код не поможет
В остальных случая _id вроде всегда число, а значит мы и так получим максимальный _id
Nested Sets для Javascript