#javascript #arrays #performance #data-structures #quadtree
#javascript #массивы #Производительность #структуры данных #quadtree
Вопрос:
Я использую структуру данных четырехъядерного дерева для поиска близлежащих объектов на 2D плоскости. Я уже реализовал рабочее четырехъядерное дерево, которое возвращает массив для каждого объекта, включая всех его соседей. Проблема в том, что мне нужна каждая уникальная пара объектов из этой группы списков.
Допустим, у меня есть следующие точки [a, b, c, d] в массиве. И это:
a находится рядом с b,
b находится рядом с c,
c находится рядом с d,
Поэтому,
a НЕ находится рядом с c или d,
b НЕ находится рядом с d,
c НЕ находится рядом с a,
d НЕ находится рядом с a или b,
Поэтому, перебирая каждый объект и запрашивая его соседей, я получу следующий массив, где каждый элемент является собственным массивом, где первый элемент является рассматриваемым объектом, а каждый другой элемент — его соседями:
[
[a, b], // a is only near b
[b, a, c], // So b is near c and also a
[c, b, d], // So c is near b and also d
[d, c] // d is only near c
]
Я хочу массив, содержащий только уникальные пары соседних объектов (например, наличие обоих [a, b] и [b, a] неприемлемо), и поэтому в этом случае решение было бы:
[
[a, b],
[b, c],
[c, d]
]
Как я могу достичь этого результата?
Также мы были бы очень признательны, если бы код был максимально оптимизирован. Большое вам спасибо!
Комментарии:
1. Покажите минимальный рабочий пример, в котором вам нужна помощь.
2. @DominiqueFortin Я не совсем уверен, что вы имеете в виду. Я не могу действительно показать codepen, поскольку само quadtree слишком сложно реализовать. Я просто прошу функцию для фильтрации массива из [[a, b], [b, a, c], [c, b, d], [d, c]] в [[a, b], [b, c], [c, d]].
3. Вы должны обратиться к Stackoverflow за помощью по чему-то конкретному, что вы создали, а не просить кого-то что-то закодировать для вас.
4. @DominiqueFortin Я уверен, что решение моей проблемы на самом деле довольно простая функция Array.filter или что-то в этом роде, но я не могу понять, как это сделать. Я закодировал это четырехъядерное дерево и объекты, но все это часть гораздо большей программы, которая не поместится в примере codepen, даже если вы не хотите давать мне какой-либо код, вы могли бы, по крайней мере, указать мне направление. Так что это конкретно, я просто задаю вопрос, как это делают все остальные. Я посмотрю, смогу ли я сделать небольшой пример кода…
5. Нет, это не просто. Возможно, используя reduce, но я не уверен.
Ответ №1:
Я больше думал об этих строках
let unsortedArray = [
['a', 'b'],
['b', 'a', 'c'],
['c', 'b', 'd'],
['d', 'c']
];
function solver(arr) {
let marked = {};
let result = [];
arr.forEach((arcs) => {
let first;
arcs.forEach((vertex, i) =>{
if (i === 0 ) {
first = vertex;
} else {
let forward = first vertex, backward = vertex first;
if (!marked.hasOwnProperty(forward) amp;amp; !marked.hasOwnProperty(backward)) {
result.push([first, vertex]);
}
marked[forward] = 0;
marked[backward] = 0;
}
});
});
return resu<
}
console.log(solver(unsortedArray)); Ответ №2:
Я решил сортировку, но это довольно дорого с точки зрения вычислений, если кто-нибудь знает, как сократить этот код, я был бы очень признателен!
let unsortedArray = [
['a', 'b'],
['b', 'a', 'c'],
['c', 'b', 'd'],
['d', 'c']
];
function solver(arr) {
// Detach first elements
let groups = [];
for (let i = 0; i < arr.length; i ) {
let body = arr[i].shift();
groups[i] = {body, others: arr[i]};
}
// Get all pairs
let pairs = [];
for (let i = 0; i < groups.length; i ) {
for (let j = 0; j < groups[i].others.length; j ) {
let pair = [groups[i].body, groups[i].others[j]];
pairs.push(pair);
}
}
// Filter non unique pairs
for (let i = 0; i < pairs.length; i ) {
for (let j = i 1; j < pairs.length; j ) {
if (pairs[i] == pairs[j] || (pairs[i][0] == pairs[j][1] amp;amp; pairs[i][1] == pairs[j][0])) {
pairs.splice(j, 1);
}
}
}
return pairs;
}
let sortedArray = solver(unsortedArray);
console.log(sortedArray);