Эффективный алгоритм частичного переупорядочения
Рассмотрим следующий массив объектов:
[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]
Некоторые объекты содержат свойство ptr, ссылающееся на значение свойства v объекта, которому оно должно предшествовать. Два объекта никогда не будут пытаться непосредственно предшествовать одному и тому же объекту, и в массиве никогда не будет цикла (например, a->b->c->a).
Таким образом, вот две возможные допустимые перестановки объектов:
[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]
[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]
Совершенно не имеет значения, где объекты появляются в выводе, если нет свойства ptr, ссылающегося на него. Все, что имеет значение, это то, что определенные объекты непосредственно предшествуют другим, если этого требует свойство ptr.
Каков достаточно эффективный алгоритм для выполнения такого рода перестановки?
Хотя данные гарантированно не содержат циклов, переупорядочение должно быть осторожным, чтобы не попасть в бесконечный цикл, в котором объекты будут переупорядочиваться навсегда.
Обратите внимание: хотя в этих примерах для v и ptr используются строки, в реальном приложении в качестве значений для ссылок v и ptr будут использоваться элементы DOM. Следовательно, решение должно иметь возможность сравнивать только свойства v и ptr на предмет равенства.
Если вы думаете о массиве как описывающем граф, где значения v — это узлы, а объекты со значениями ptr описывают ребра, то упорядочение узлов эквивалентно топологической сортировке. Чего я не вижу в вопросе, так это ничего, что указывает на то, как упорядочивать другие объекты, не имеющие значений ptr.
@danh, спасибо, совершенно не важно, где в выводе появляются другие объекты. Все, что имеет значение, это то, что определенные объекты непосредственно предшествуют другим, если этого требует свойство ptr.
То есть никакого v нет... просто цепочка ptr, верно?
@danh: Это немного строже, чем топологическая сортировка, потому что объекты со свойством ptr должны непосредственно предшествовать соответствующему объекту. При топологической сортировке, если бы a имело выходящее к b ребро и c не имело инцидентных ребер, a, c, b был бы действительным порядком.
@SpencerМожет быть, правильно: в реальном приложении сортировать v было бы невозможно, поскольку это всего лишь ссылки на элементы DOM, а не строки.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 3
Выясните, на какие объекты указывает другой объект. Затем для каждого объекта, на который не указывает другой объект, добавьте в выходные данные этот объект и все, что находится в следующей цепочке ptr:
let val_to_obj = new Map();
let has_predecessor = new Set();
for (let obj of arr) {
val_to_obj.set(obj.v, obj);
if ('ptr' in obj) {
has_predecessor.add(obj.ptr);
}
}
let res = [];
for (let obj of arr) {
if (has_predecessor.has(obj.v)) {
continue;
}
while (obj !== undefined) {
res.push(obj);
obj = val_to_obj.get(obj.ptr);
}
}
Я знаю, что на этот вопрос уже ответили, но я все равно хочу опубликовать свой: p
Также добавлено еще несколько цепочек для тестирования. Корень каждой цепочки — это то место, где будет порождаться результирующая цепочка, поэтому, хотя цепочка, начинающаяся с c, определена до несвязанного g, последний элемент i является корнем цепочки c, поэтому вся ее цепочка располагается там.
var st = [
{v: 'a'},
{v: 'f', ptr: 'e'},
{v: 'b', ptr: 'h'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
{v: 'h'},
{v: 'g'},
{v: 'i', ptr: 'c'}
]
function createChain(x) {
let i = 0;
while (i < x.length) {
// if chaining
if (x[i]?.ptr) {
// find index of chained element
let follows = x.findIndex(y => y.v == x[i].ptr);
if (follows > -1) {
let offset = 0;
// search for already-chained elements with `follows`
while (x[follows+offset+1] && x[follows+offset]?.ptr == x[follows+offset+1].v) {
offset++;
}
// splicing elements before index requires an offset
i = follows < i ? i-offset : i;
// offset calculations were non inclusive of follows, +1
x.splice(i, 0, ...x.splice(follows, offset+1));
// reset index to offset end position
i += offset-1;
}
}
i++;
}
return x;
}
console.info(createChain(st));Спасибо, я подумаю, нет ли каких-нибудь пропущенных крайних случаев.
Весь поиск и сращивание приводят к очень плохой временной сложности для этого кода — я думаю, что она может быть даже O(N^3).
@user2357112 user2357112 Я внес обновление в свой пост, которое сократило время выполнения примерно на 50% за счет поиска существующих цепочек после искомой переменной follows. Я не совсем уверен, как вычислить значение сложности, я просто делаю разницу во времени, лол.
@AndrewParks Я сделал обновление, протестировал еще немного, и, похоже, оно все еще проходит все, что я могу. Надеюсь, это подойдет и вам!
Соберите элементы с помощью ptr и скопируйте введенные данные, вставив элементы ptr перед их целями:
const input = [
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]
const pres = input.reduce((r, item) => ('ptr' in item && r.set(item.ptr, item), r), new Map);
const prefill = (item, r) => {
const pre = pres.get(item.v);
if (!pre) return;
pres.delete(item.v);
prefill(pre, r);
r.push(pre);
};
const result = input.reduce((r, item) => ('ptr' in item || (prefill(item, r), r.push(item)), r), []);
console.info(result);И эталон:
` Chrome/123
----------------------------------------------------------------------------------------
> n=6 | n=60 | n=600 | n=6000
Alexander ■ 1.00x x1m 187 | ■ 1.00x x1m 613 | ■ 1.00x x100k 472 | ■ 1.00x x10k 558
user2357112 1.33x x1m 249 | 2.82x x100k 173 | 3.39x x10k 160 | 3.01x x1k 168
----------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `
let offset = 0;
const $chunk = (offset++, [
{v: 'a' + offset},
{v: 'b' + offset},
{v: 'c', ptr: 'b' + offset},
{v: 'd' + offset, ptr: 'a' + offset},
{v: 'e', ptr: 'f' + offset},
{v: 'f' + offset, ptr: 'd' + offset}
]);
const $input = [];
// @benchmark user2357112
let arr = $input;
let val_to_obj = new Map();
let has_predecessor = new Set();
for (let obj of arr) {
val_to_obj.set(obj.v, obj);
if ('ptr' in obj) {
has_predecessor.add(obj.ptr);
}
}
let res = [];
for (let obj of arr) {
if (has_predecessor.has(obj.v)) {
continue;
}
while (obj !== undefined) {
res.push(obj);
obj = val_to_obj.get(obj.ptr);
}
}
res;
// @benchmark Alexander
const pres = $input.reduce((r, item) => ('ptr' in item && r.set(item.ptr, item), r), new Map);
const prefill = (item, r) => {
const pre = pres.get(item.v);
if (!pre) return;
pres.delete(item.v);
prefill(pre, r);
r.push(pre);
};
$input.reduce((r, item) => ('ptr' in item || (prefill(item, r), r.push(item)), r), []);
/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));Это не удается при вводе [{v: 'a'}, {v: 'b', ptr: 'a'}, {v: 'c', ptr: 'b'}].
Спасибо, хороший подход. Меня немного беспокоят ограничения, которые могут быть наложены на этот подход из-за рекурсии (и, следовательно, переполнения стека).
@AndrewParks, я думаю, цепочка PTR должна быть очень длинной
ок, я думаю, тебе следует добавить эту информацию в свой вопрос