主页 / coding / 问题 / 78322342
Accepted
Andrew Parks
Asked: 2024-04-14 08:16:24 +0800 CST

部分重新排序的高效算法

  • 772

考虑以下对象数组：

[
{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实际应用程序将涉及 DOM 元素作为v和 的值ptr引用。因此，解决方案应该只能比较v和ptr属性是否相等。

javascript

3 个回答

  1. Best Answer

    找出哪些对象有另一个对象指向它们。然后，对于没有其他对象指向它的每个对象，将该对象以及以下 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);
    }
}
    • 1

  2. 我知道这个问题已经得到解答，但我仍然想发布我的: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.log(createChain(st));

    • 1

  3. 通过在目标之前插入项目来收集项目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.log(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));

    • 1

相关问题