用键“减少”嵌套数组到对象的最快方法+按键查找的最快方法

Question

我需要转换这种类型的嵌套数组，以便能够以最快的方式通过键 (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但这看起来具有相同的复杂性并且占用更多内存。

有人有更好的主意来进行这种转变吗？我正在处理庞大的数据集，我开始觉得我需要找到更好的方法来处理数据。

我这样做是因为我需要在这个数据集中按 ID 快速搜索。在数组中搜索findIndex很慢。并且转换需要处理，如上所述。

我需要找到总体复杂度最低的选项。

Answer 1

去转型。这是一项值得付出代价的努力，因为您所做的每一次搜索都会从这项投资中受益。这是一个转换为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 transformationlet lookup = makeLookup(list);// Demo of a loookupconsole.log(lookup.get("1,2").name);console.log(lookup.get("2,3").example);