Javascript 可排序数组/对象结构和性能

Question

在 javascript 中，如果对象应该保持排序顺序，我们就不能在对象中使用键/值对。相反，我们需要一个类似 ES6 map 的数组。

看起来下面可能是构建它的一种方式。我将 id 并将所有 items 包装到一个数组中。 col block 的想法相同。

[
  {
    id: 21,
    items: [
      {
        col: 'name',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      },
      {
        col: 'slug',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      }
    ]
  },
  {
    id: 44,
    items: [
      {
        col: 'name',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      },
      {
        col: 'slug',
        data: {
          data1: 'hello',
          data2: 'world'
        }
      }
    ]
  },
]

问题

这种方法的问题是，当它不能使用键/值对时，它需要遍历整个数组来找到 id 44 例如.在现实生活中，不只有两个组，可以有 100 个组。cols 也是一样。每个项目组可能有 20 列。它需要遍历所有项目以找到例如列别名。

梦想代码

let result = get(44, 'slug', 'data2');

问题

• 上面的结构是否良好且性能良好？
• 如何在不影响性能的情况下介入其中？

Answer 1

您的结构在查找任何内容时不会非常慢。通过对每个项目及其子字段进行线性扫描，您将获得 O(m*n) 复杂度，因为您需要遍历每个组，然后检查其每一列，最后抓取按名称的数据(假设它的复杂度为 O(1))。有 100 个组和 20 个列，如果你捕获最后一个项目，那最多仍然是 2000 次操作。这应该相当快，因为​​您只需检查它是否是正确的项目并丢弃其余的。

不过，如果这太慢了，并且您需要进行大量查找，您可以通过从数据生成一个查找表来将获取数据的复杂性降低到 O(1)基本上是这样工作的:

+----------+-------------+----------+-------+
| group id | column name | data key | value |
+----------+-------------+----------+-------+
|       21 | name        | data1    | hello |
|       21 | name        | data2    | world |
|       21 | slug        | data1    | hello |
|       21 | slug        | data2    | world |
|  etc...  |    etc...   |  etc...  | etc...|
+----------+-------------+----------+-------+

您可以使用嵌套 map 来表示:

const data = [ { id: 21, items: [ { col: 'name', data: { data1: 'hello', data2: 'world' } }, { col: 'slug', data: { data1: 'hello', data2: 'world' } } ] }, { id: 44, items: [ { col: 'name', data: { data1: 'hello', data2: 'world' } }, { col: 'slug', data: { data1: 'hello', data2: 'world' } } ] }, ];

const lookupTable = new Map();

data.forEach(group => {
  if (!lookupTable.has(group.id)) {
    lookupTable.set(group.id, new Map());
  }
  
  const groupLookupTable = lookupTable.get(group.id);
  
  group.items.forEach(column => {
    //only set the `data` object
    groupLookupTable.set(column.col, column.data);
  })
})

function get(id, col, data) {
  const group = lookupTable.get(id);
  
  if (!group) return;
  
  const columnData = group.get(col);
  
  if (!columnData) return;
    
  return columnData[data];
}


let result = get(44, 'slug', 'data2');

console.log(result)

您可以最后分配属于 data 的对象，因为它比将其转换为 Map 并在内存中为相同数据保留另一个对象要便宜。同时，在对象中查找key的速度应该和从Map中查找一样。事实上，您可以使用普通对象而不是 Maps 来实现它，但至少，Map 确保键保持相同的类型。