Javascript, частичное переупорядочение массива

Как лучше всего частично переупорядочить массив?

Я создал очень простой пример; По сути, я хочу изменить порядок массива (раньше), используя (индексы), хранящиеся в массиве.

Используя код, у меня есть выходы: 14,21,10,13. Однако я хотел бы затем сохранить оставшуюся часть массива, которая не включена, добавленную в новый массив after в том порядке, в котором они изначально появляются.

В результате массив after будет заполнен следующим образом: 14,21,10,13 23,8,15

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [2,1,4,0];

const reorderByIndexes = (arr, order) => order.map((index) => arr[index]);

const after = reorderByIndexes(before, indexes);

console.info(after.join());
// 14,21,10,13 23,8,15

Я знаю, что в таком упрощенном примере я мог бы использовать цикл для их перебора, но окончательная версия будет намного больше.

🤔 А знаете ли вы, что...
JavaScript можно использовать для создания видеоигр, как 2D, так и 3D, с использованием библиотеки Three.js.

[РЕШЕНО]Перейти к решению

181

Javascript273878 вопросов Arrays47171 вопрос Sorting7960 вопросов

Ответы:

Решено

Я предполагаю, что в вашем вопросе опечатка, и ожидаемый результат: 14,21,10,23,12,8,15

Упорядочите индексы arr либо по положению индекса в order, либо по самому индексу + order.length.

Мы добавляем order.length, чтобы что-то с индексом 1 в order появлялось перед чем-то, чего нет в order и что находится с индексом 0 в arr.

Затем сопоставьте индексы с элементами arr

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [2,1,4,0];

const reorderByIndexes = (arr, order) => {
  const f = i => {
    let r = order.indexOf(i)
    return r!==-1 ? r : i + order.length
  }
  return arr.map((_,i) => i).sort((i,j) => f(i) - f(j)).map(i => arr[i])
}

const after = reorderByIndexes(before, indexes)

console.info(after.join());

Обновление: еще более простая версия, имеющая примерно такую же производительность, как и ответ Александра:

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [2,1,4,0]

const reorderByIndexes = (arr, order) => 
  [...order.map(e => arr[e]), ...arr.filter((e,i) => !order.includes(i))]
  
const after = reorderByIndexes(before, indexes)

console.info(after.join());

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [2,1,4,0];

const reorderByIndexes = (arr, order) => 
  [...order.map(e=>arr[e]), ...arr.filter((e,i)=>!order.includes(i))]

const reorderByIndexes2 = (arr, order, r = order.map(e=>arr[e])) =>
  (r.push(...arr.filter((e,i)=>!order.includes(i))), r)

const reorderByIndexes3 = (arr, order) => {
  const r = Array(arr.length);
  const set = new Set(indexes);
  let j = order.length;
  arr.forEach((n, i) => {
    if (i < order.length) r[i] = arr[order[i]];
    if (!set.has(i)) r[j++] = n;
  });
  return r;
}

// @benchmark Andrew Parks 1
reorderByIndexes(before, indexes);

// @benchmark Andrew Parks 2
reorderByIndexes2(before, indexes);

// @benchmark Alexander
reorderByIndexes3(before, indexes);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

` Chrome/123
-------------------------------------------------------
Andrew Parks 2  ■ 1.00x | x10000000 786 787 793 796 810
Andrew Parks 1    1.04x | x10000000 818 841 852 858 863
Alexander         1.09x | x10000000 856 857 865 872 875
-------------------------------------------------------
https://github.com/silentmantra/benchmark `

Чтобы сделать его эффективным, просто заранее выделите массив и заполните его две половины. Используйте Set, чтобы отфильтровать оставшиеся значения:

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [2,1,4,0];

const reorderByIndexes = (arr, order) => {
    const r = Array(arr.length);
    const set = new Set(indexes);
    let i = -1, j = order.length;
    while(++i < order.length) r[i] = arr[order[i]], set.has(i) || (r[j++] = arr[i]);
    while(++i < r.length) set.has(i) || (r[j++] = arr[i]);
    return r;
}

const after = reorderByIndexes(before, indexes);

console.info(...after);

И эталон:

` Chrome/123
----------------------------------------------------------------------------------------------------------------
>                       n=7        |       n=70        |       n=700       |      n=7000      |     n=70000     
Nina 2             8.39x  x10m 802 | ■ 1.00x   x1m 522 | ■ 1.00x x100k 489 | ■ 1.00x x10k 438 | ■ 1.00x  x1k 879
Alexander          7.24x  x10m 692 |   1.75x   x1m 912 |   1.75x x100k 855 |   4.00x  x1k 175 |   3.11x x100 273
Thomas 2           4.35x  x10m 416 |   3.28x x100k 171 |   5.19x  x10k 254 |  39.27x x100 172 | 192.26x   x1 169
Thomas 1           4.79x  x10m 458 |   3.20x x100k 167 |   5.48x  x10k 268 |  42.01x x100 184 | 192.26x   x1 169
Andrew Parks 1     7.83x  x10m 749 |   3.41x x100k 178 |   5.99x  x10k 293 |  42.01x x100 184 | 194.54x   x1 171
Andrew Parks 2     8.87x  x10m 848 |   3.49x x100k 182 |   6.91x  x10k 338 |  42.69x x100 187 | 199.09x   x1 175
Nina 1           ■ 1.00x x100m 956 |   1.07x   x1m 558 |  13.23x  x10k 647 | 154.79x x100 678 | 780.43x   x1 686
----------------------------------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

` Firefox/124
----------------------------------------------------------------------------------------------------------------
>                      n=7        |       n=70        |       n=700       |     n=7000      |      n=70000      
Nina 2             3.84x x10m 688 | ■ 1.00x   x1m 686 | ■ 1.00x x100k 726 | ■ 1.00x x1k  88 |  ■ 1.00x x100   89
Alexander         19.16x  x1m 343 |   2.84x x100k 195 |   2.87x  x10k 208 |   5.52x x1k 486 |    6.26x x100  557
Andrew Parks 2     8.72x  x1m 156 |   4.11x x100k 282 |  19.70x   x1k 143 | 130.68x x10 115 | 1325.84x   x1 1180
Thomas 2           5.36x x10m 959 |   4.10x x100k 281 |  18.46x   x1k 134 | 136.36x x10 120 | 1329.21x   x1 1183
Thomas 1           7.99x  x1m 143 |   4.10x x100k 281 |  19.83x   x1k 144 | 139.77x x10 123 | 1329.21x   x1 1183
Andrew Parks 1    12.23x  x1m 219 |   5.00x x100k 343 |  19.42x   x1k 141 | 135.23x x10 119 | 1333.71x   x1 1187
Nina 1           ■ 1.00x x10m 179 |   2.03x x100k 139 |  17.49x   x1k 127 | 143.18x x10 126 | 1753.93x   x1 1561
----------------------------------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

const $chunks = [1, 10, 100, 1000, 10000];
const $chunk = [23, 21, 14, 12, 10, 8, 15]
let offset = 0;
const $chunkIndices = () => {
    const out = [2, 1, 4, 0].map(n => n + offset);
    offset += $chunk.length;
    return out;
};
const $input = [], $inputIndices = [], before = $input, indexes = $inputIndices;

const reorderByIndexesAP1 = (arr, order) => [
    ...order.map(i => arr[i]),
    ...arr.filter((_, i) => !order.includes(i))
];

const reorderByIndexesAP2 = (arr, order, r = order.map(e => arr[e])) =>
    (r.push(...arr.filter((e, i) => !order.includes(i))), r);

const reorderByIndexesAN1 = (arr, order) => {
    const r = Array(arr.length);
    const set = new Set(indexes);
    let i = -1, j = order.length;
    while(++i < order.length) r[i] = arr[order[i]], set.has(i) || (r[j++] = arr[i]);
    while(++i < r.length) set.has(i) || (r[j++] = arr[i]);
    return r;
}

const reorderByIndexesT1 = (arr, order) => {
    const result = [];

    for (const i of order) result.push(arr[i]);
    for (const i of arr.keys()) order.includes(i) || result.push(arr[i]);

    return result;
}

const reorderByIndexesT2 = (arr, order) => {
    const result = Array(arr.length), pivot = order.length;

    for (let i = 0, j = pivot; i < arr.length; ++i) {
        if (i < pivot) result[i] = arr[order[i]];
        if (!order.includes(i)) result[j++] = arr[i];
    }

    return result;
}

const reorderByIndicesNS1 = (values, order) => {
    for (let i = 0; i < order.length; i++) {
        let j = order[i];
        if (j <= i) j += i;
        while (i < j) {
            const temp = values[j];
            values[j] = values[j - 1];
            values[j - 1] = temp;
            j--;
        }
    }
    return values;
};

const reorderByIndicesNS2 = (values, order) => {
    const
        orderLength = order.length,
        valuesLength = values.length,
        taken = {},
        result = Array(valuesLength);

    let i = 0, // target index
        j = 0; // source index

    for (; i < orderLength; i++) {
        let k = order[i];
        taken[k] = true;
        result[i] = values[k];
    }
    for (; i < valuesLength; i++) {
        while (taken[j]) j++;
        result[i] = values[j++];
    }
    return result;
};

// @benchmark Andrew Parks 1
reorderByIndexesAP1(before, indexes);

// @benchmark Andrew Parks 2
reorderByIndexesAP2(before, indexes);

// @benchmark Alexander
reorderByIndexesAN1(before, indexes);

// @benchmark Thomas 1
reorderByIndexesT1(before, indexes);

// @benchmark Thomas 2
reorderByIndexesT2(before, indexes);

// @benchmark Nina 1
reorderByIndicesNS1(before, indexes);

// @benchmark Nina 2
reorderByIndicesNS2(before, indexes);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

Вы можете перемещать предметы (на месте).

const
    reorderByIndices = (values, order) => {
        for (let i = 0; i < order.length; i++) {
            let j = order[i];
            if (j <= i) j += i;
            while (i < j) {
                const temp = values[j];
                values[j] = values[j - 1];
                values[j - 1] = temp;
                j--;
            }
        }
        return values;
    },
    before = [23, 21, 14, 12, 10, 8, 15],
    indices = [2, 1, 4, 0],
    after = reorderByIndices(before, indices);

console.info(...after); // 14 21 10 23 12 8 15

Подход с дырками (немутирующий).

const
    reorderByIndices = (values, order) => {
        const
            orderLength = order.length,
            valuesLength = values.length,
            taken = {},
            result = Array(valuesLength);

        let i = 0, // target index
            j = 0; // source index

        for (; i < orderLength; i++) {
            let k = order[i];
            taken[k] = true;
            result[i] = values[k];
        }
        for (; i < valuesLength; i++) {
            while (taken[j]) j++;
            result[i] = values[j++];
        }
        return result;
    },
    before = [23, 21, 14, 12, 10, 8, 15],
    indices = [2, 1, 4, 0],
    after = reorderByIndices(before, indices);

console.info(...after); // 14 21 10 23 12 8 15

Хорошо, давайте перейдем к микрооптимизации:

const before = [23, 21, 14, 12, 10, 8, 15]
const indexes = [6, 5, 1, 4];

const reorderByIndexesAP1 = (arr, order) => [
  ...order.map(i => arr[i]), 
  ...arr.filter((_, i) => !order.includes(i))
];

const reorderByIndexesAP2 = (arr, order, r = order.map(e => arr[e])) =>
  (r.push(...arr.filter((e, i) => !order.includes(i))), r);

const reorderByIndexesAN1 = (arr, order) => {
  const r = Array(arr.length);
  const set = new Set(indexes);
  let j = order.length;
  arr.forEach((n, i) => {
    if (i < order.length) r[i] = arr[order[i]];
    if (!set.has(i)) r[j++] = n;
  });
  return r;
}

const reorderByIndexesT1 = (arr, order) => {
  const result = [];

  for (const i of order) result.push(arr[i]);
  for (const i of arr.keys()) order.includes(i) || result.push(arr[i]);

  return result;
}

const reorderByIndexesT2 = (arr, order) => {
  const result = Array(arr.length), pivot = order.length;

  for (let i = 0, j = pivot; i < arr.length; ++i) {
    if (i < pivot) result[i] = arr[order[i]];
    if (!order.includes(i)) result[j++] = arr[i];
  }

  return result;
}

// @benchmark Andrew Parks 1
reorderByIndexesAP1(before, indexes);

// @benchmark Andrew Parks 2
reorderByIndexesAP2(before, indexes);

// @benchmark Alexander
reorderByIndexesAN1(before, indexes);

// @benchmark Thomas 1
reorderByIndexesT1(before, indexes);

// @benchmark Thomas 2
reorderByIndexesT2(before, indexes);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

и все же, мой любимый — самый медленный код здесь

// from Andrew Parks:
const reorderByIndexes = (arr, order) => [
  ...order.map(i => arr[i]), 
  ...arr.filter((_, i) => !order.includes(i))
];

Это коротко и просто. Легко брать в руки и компактный, нечего заворачивать в голову и достаточно быстрый.

Да, вы можете сделать это быстрее, предварительно выделив массив, написав простой цикл и выполнив умную индексацию, но если этот код не находится на горячем пути, я бы выбрал простой вариант.

Javascript, частичное переупорядочение массива

Ответы:

Интересные вопросы для изучения