Улучшение преобразования массива в Javascript

Question

Предположим, у меня есть входной массив, подобный следующему

var inputArray = [
    {a: 1, b: 1, c: 1, d: 1, value: 1, rank: 1},
    {a: 1, b: 1, c: 1, d: 1, value: 2, rank: 2},
    {a: 1, b: 1, c: 1, d: 1, value: 3, rank: 3},
    {a: 1, b: 1, c: 1, d: 1, value: 4, rank: 4},
    {a: 1, b: 1, c: 1, d: 1, value: 5, rank: 5},
    {a: 1, b: 2, c: 1, d: 1, value: 1, rank: 1},
    {a: 1, b: 2, c: 1, d: 1, value: 2, rank: 2},
    {a: 1, b: 2, c: 1, d: 1, value: 3, rank: 3},
    {a: 1, b: 2, c: 1, d: 1, value: 4, rank: 4},
    {a: 1, b: 2, c: 1, d: 1, value: 5, rank: 5}
]

Я хочу преобразовать мой inputArray в следующее outputArray

var outputArray = [
    {
        a: 1,
        b: 1,
        c: 1,
        d: 1,
        values:{
            "1":{value: 1},
            "2":{value: 2},
            "3":{value: 3},
            "4":{value: 4},
            "5":{value: 5}
        }
    },
    {
        a: 1,
        b: 2,
        c: 1,
        d: 1,
        values:{
            "1":{value: 1},
            "2":{value: 2},
            "3":{value: 3},
            "4":{value: 4},
            "5":{value: 5}
        }
    }
]

Это означает, что мне нужно создать словарь для того же свойства a, b, c и d, где значение свойства rank является ключом словаря и значением словаря object, где единственным свойством является value.

Мы предполагаем, что inputArray не будет отсортирован по комбинации a, b, c и d. Итак, мой подход такой,

(function(){
    var inputArray = [
        {a: 1, b: 1, c: 1, d: 1, value: 1, rank: 1},
        {a: 1, b: 1, c: 1, d: 1, value: 2, rank: 2},
        {a: 1, b: 1, c: 1, d: 1, value: 3, rank: 3},
        {a: 1, b: 1, c: 1, d: 1, value: 4, rank: 4},
        {a: 1, b: 1, c: 1, d: 1, value: 5, rank: 5},
        {a: 1, b: 2, c: 1, d: 1, value: 1, rank: 1},
        {a: 1, b: 2, c: 1, d: 1, value: 2, rank: 2},
        {a: 1, b: 2, c: 1, d: 1, value: 3, rank: 3},
        {a: 1, b: 2, c: 1, d: 1, value: 4, rank: 4},
        {a: 1, b: 2, c: 1, d: 1, value: 5, rank: 5}
    ]

    var temp = inputArray.sort(function(valA, valB){
        if(valA.a === valB.a){
            if(valA.b === valB.b){
                if(valA.c === valB.c){
                    return valA.d < valB.d;
                }
                return valA.c < valB.c;
            }
            return valA.b < valB.b;
        }
        return valA.a < valB.a;
    });

    var outputArray = [],
    currentIndex = 0;
    for(var i = 0; i < inputArray.length; i++){
        if(i > 0 && isConfigurationSame(inputArray[i], inputArray[i-1])){
            outputArray[currentIndex-1].values[inputArray[i].rank] = {
                value: inputArray[i].value
            }
        }
        else{
            outputArray.push(mapToOutputArrayObject(inputArray[i]));
            currentIndex++;
        }
    }
    console.log(outputArray);

    function isConfigurationSame(A, B) {
        return A.a === B.a
            && A.b === B.b
            && A.c === B.c
            && A.d === B.d;
    }

    function mapToOutputArrayObject(val){
        var row = {};
        row['a'] = val.a;
        row['b'] = val.b;
        row['c'] = val.c;
        row['d'] = val.d;
        row['values'] = {};
        row.values[val.rank] = {
            value: val.value
        }
        return row;
    }
}());

Но проблема в том, что эта вещь действительно получает больше времени, если длина входного массива огромна. Эта многокритериальная сортировка также занимает много времени.

Есть ли лучший подход для достижения результата более эффективно с меньшими затратами времени?

Спасибо за ваше время и терпение.

ОБНОВЛЕНИЕ: Значения a, b, c и d могут быть целыми числами или null.

Answer 1

Вы можете создать хеш-таблицу и сгенерировать уникальный ключ на основе a, b, c и d:

const hash = {};

for(const { a, b, c, d, value, rank } of array) {
  const key = JSON.stringify([a, b, c, d]); // generate a unique, but not random key
  if(hash[key]) { // check if it already exists,
   hash[key].values[rank] = value; // merge
  } else {
   hash[key] = { // create a new entry
     a, b, c, d,
     values: { [rank]: value },
   };
  }
}

const result = Object.values(hash); // turn the object into an array

То есть O (n), что лучше, чем временная сложность любого .sort реализация (но она работает, только если a, b, c и d сериализуемы (как в этом случае)).

Answer 2

Вы можете взять Map и массив ключей группировки и собрать значения для каждой группы.

var array = [{ a: 1, b: 1, c: 1, d: 1, value: 1, rank: 1 }, { a: 1, b: 1, c: 1, d: 1, value: 2, rank: 2 }, { a: 1, b: 1, c: 1, d: 1, value: 3, rank: 3 }, { a: 1, b: 1, c: 1, d: 1, value: 4, rank: 4 }, { a: 1, b: 1, c: 1, d: 1, value: 5, rank: 5 }, { a: 1, b: 2, c: 1, d: 1, value: 1, rank: 1 }, { a: 1, b: 2, c: 1, d: 1, value: 2, rank: 2 }, { a: 1, b: 2, c: 1, d: 1, value: 3, rank: 3 }, { a: 1, b: 2, c: 1, d: 1, value: 4, rank: 4 }, { a: 1, b: 2, c: 1, d: 1, value: 5, rank: 5 }],
    keys = ['a', 'b', 'c', 'd'],
    result = [],
    map = new Map;
    
array.forEach(o => {
    var key = keys.map(k => o[k]).join('|'),
        temp = map.get(key);

    if (!temp) {
        map.set(key, temp = Object.assign(...keys.map(k => ({ [k]: o[k] })), { values: {} }));
        result.push(temp);
    }

    temp.values[o.rank] = { value: o.value };
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

Вот еще один вариант, сначала группировка по a, b, c и d.Затем сопоставление каждой группы с преобразованием value и rank.

var inputArray = [{a: 1, b: 1, c: 1, d: 1, value: 1, rank: 1}, {a: 1, b: 1, c: 1, d: 1, value: 2, rank: 2}, {a: 1, b: 1, c: 1, d: 1, value: 3, rank: 3}, {a: 1, b: 1, c: 1, d: 1, value: 4, rank: 4}, {a: 1, b: 1, c: 1, d: 1, value: 5, rank: 5}, {a: 1, b: 2, c: 1, d: 1, value: 1, rank: 1}, {a: 1, b: 2, c: 1, d: 1, value: 2, rank: 2}, {a: 1, b: 2, c: 1, d: 1, value: 3, rank: 3}, {a: 1, b: 2, c: 1, d: 1, value: 4, rank: 4}, {a: 1, b: 2, c: 1, d: 1, value: 5, rank: 5}];

function groupBy(array, callback) {
  return array.reduce((groups, item, ...args) => {
    const key = callback(item, ...args),
          group = groups[key] || (groups[key] = []);

    group.push(item);
    return groups;
  }, {});
};

console.log(
  Object
    .values( groupBy(inputArray, ({a, b, c, d}) => [a, b, c, d]) )
    .map(group => {
      const {a, b, c, d} = group[0],
            values = {};
      
      group.forEach(({value, rank}) => values[rank] = {value});
      return {a, b, c, d, values};
    })
);

Answer 4

Вот удар, используя Set, Map и метод const для создания объекта Values.

var inputArray = [
    {a: 1, b: 1, c: 1, d: 1, value: 1, rank: 1},
    {a: 1, b: 1, c: 1, d: 1, value: 2, rank: 2},
    {a: 1, b: 1, c: 1, d: 1, value: 3, rank: 3},
    {a: 1, b: 1, c: 1, d: 1, value: 4, rank: 4},
    {a: 1, b: 1, c: 1, d: 1, value: 5, rank: 5},
    {a: 1, b: 2, c: 1, d: 1, value: 1, rank: 1},
    {a: 1, b: 2, c: 1, d: 1, value: 2, rank: 2},
    {a: 1, b: 2, c: 1, d: 1, value: 3, rank: 3},
    {a: 1, b: 2, c: 1, d: 1, value: 4, rank: 4},
    {a: 1, b: 2, c: 1, d: 1, value: 5, rank: 5}
];

const getValueObject = (a,b,c,d, arr) => {
  let obj = {};
  arr.filter(i => i.a === a &&
                  i.b === b &&
                  i.c ===c &&
                  i.d === d)
    .forEach(item => obj[item.value] = item.rank);
  return obj;
};

// Get a set based on the key a,b,c,d
let newArray = [...new Set(inputArray.map(({a,b,c,d}) => `${a},${b},${c},${d}`))]
              .map(item => {
                let [a,b,c,d] = item.split(',').map(i => parseInt(i));
                // filter and add
                return {
                  a: a,
                  b: b,
                  c: c,
                  d: d,
                  values: getValueObject(a,b,c,d, inputArray)
                };
  
});

console.log(newArray);