Início / coding / Perguntas / 78322342
Accepted
Andrew Parks
Asked: 2024-04-14 08:16:24 +0800 CST

Algoritmo eficiente para reordenação parcial

  • 772

Considere a seguinte matriz de objetos:

[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]

Alguns dos objetos contêm uma ptrpropriedade, referenciando o vvalor da propriedade de um objeto que deve preceder diretamente. Dois objetos nunca tentarão preceder diretamente o mesmo objeto e nunca haverá um loop (por exemplo, a->b->c->a) no array.

Portanto, aqui estão dois possíveis rearranjos válidos dos objetos:

[
{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'}
]

Não importa onde os objetos aparecem na saída, se não houver nenhuma ptrpropriedade que faça referência a eles. Tudo o que importa é que certos objetos precedam diretamente outros onde a ptrpropriedade o solicita.

Qual é um algoritmo razoavelmente eficiente para realizar esse tipo de rearranjo?

Embora seja garantido que os dados não contenham loops, o rearranjo deve ter cuidado para não entrar em um loop infinito onde fica reorganizando os objetos para sempre.

Observe que, embora esses exemplos usem strings para ve ptr, o aplicativo real envolverá elementos DOM como valores para ve ptrreferências. Portanto, a solução só deve ser capaz de comparar propriedades ve ptrigualdade.

javascript

3 respostas

  1. Best Answer

    Descubra quais objetos têm outro objeto apontando para eles. Então, para cada objeto que não possui outro objeto apontando para ele, adicione esse objeto e tudo na seguinte cadeia ptr à saída:

    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. Eu sei que isso foi respondido, mas ainda quero postar o meu: p

    Adicionadas mais algumas cadeias para teste também. A raiz de cada cadeia é onde a cadeia resultante se originará, portanto, mesmo que a cadeia que começa em c seja definida antes do g desencadeado, o último elemento i é a raiz da cadeia c, portanto, toda a sua cadeia está posicionada lá.

    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. Colete itens ptre copie a entrada inserindo ptritens antes de seus alvos:

    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);

    E uma referência:

    ` 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

relate perguntas