Самый быстрый способ «уменьшить» вложенный массив до объекта с ключами + самый быстрый способ найти по ключу - PullRequest
Новая
       0

Самый быстрый способ «уменьшить» вложенный массив до объекта с ключами + самый быстрый способ найти по ключу

0 голосов
/ 18 октября 2019

Мне нужно преобразовать этот тип вложенного массива, чтобы иметь возможность искать по ключу (id) самым быстрым способом: 

[
   {
      "id":1,
      "name":"example1",
      "items":[
         {
            "id":1,
            "name":"example1",
            "example":123
         },
         {
            "id":2,
            "name":"example1",
            "example":123
         }
      ]
   },
   {
      "id":2,
      "name":"example1",
      "items":[
         {
            "id":3,
            "name":"example1",
            "example":123
         },
         {
            "id":4,
            "name":"example1",
            "example":123
         }
      ]
   }
]

На самом деле вложенных массивов гораздо больше (около 4 уровней).

Мой текущий способ - сделать reduce каждого уровня, а затем я могу использовать, например, list[1].items[1].name. Это выглядит как очень медленный и неэффективный способ для меня.

Я также нашел здесь на stackoverflow , что я могу создать таблицу поиска id->index, но похоже, что она имеет ту же сложность и съедает больше памяти.

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

Я делаю это, потому что мне нужно быстро искать в этом наборе данных по идентификатору. Поиск в массиве по findIndex идет медленно. И преобразование требует обработки, как я описал выше.

Мне нужно найти вариант с наименьшей общей сложностью.

1 Ответ

2 голосов
/ 18 октября 2019

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

Вот преобразование в справочную таблицу на основе Map для извлечениясвязанный объект. В качестве ключа поиска будет принята строка значений id, разделенных запятыми: 

function makeLookup(list, map=new Map, prefix="") {
    for (let obj of list) {
        map.set(prefix + obj.id, obj);
        if (obj.items) makeLookup(obj.items, map, prefix + obj.id + ",");
    }
    return map;
}


let list = [{ "id":1, "name":"example1", "items":[
     {"id":1, "name":"example2", "example":123},
     {"id":2, "name":"example3", "example":123}
  ]}, { "id":2, "name":"example4", "items":[
     { "id":3, "name":"example5", "example":123 },
     { "id":4, "name":"example6", "example":123 }
  ]}
];

// One-shot transformation
let lookup = makeLookup(list);

// Demo of a loookup
console.log(lookup.get("1,2").name);
console.log(lookup.get("2,3").example);
...