如何使用Map/Set来将代码优化到O(n)?

huangapple go评论195阅读模式
英文:

How to use Map/Set to improve the code to O(n)?

问题

也许我应该使用Map/Set,但我无法解决它...

let items = [
  {type: 'a', name: 'a1', color: 'yellow'},
  {type: 'b', name: 'b1', color: 'orange'}
];
const excludes = [
  {k: 'color', value: 'yellow'},
  {k: 'name', value: 'x'}
];

excludes.forEach((exclude) => {
  items = items.filter((item) => item[exclude.k] !== exclude.value)
})

console.log(items)
英文:

Maybe I should use Map/Set, but I can not work it out...

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

let items = [
  {type: &#39;a&#39;, name: &#39;a1&#39;, color: &#39;yellow&#39;},
  {type: &#39;b&#39;, name: &#39;b1&#39;, color: &#39;orange&#39;}
];
const excludes = [
  {k: &#39;color&#39;, value: &#39;yellow&#39;},
  {k: &#39;name&#39;, value: &#39;x&#39;}
];

excludes.forEach((exclude) =&gt; {
  items = items.filter((item) =&gt; item[exclude.k] !== exclude.value)
})

console.log(items)

<!-- end snippet -->

答案1

得分: 1

你至少不能避免读取输入。这已经需要O(n)的时间。所以你需要在O(1)的时间内检查是否需要排除一个元素。

我想到的可以做到这一点的数据结构(至少在大多数情况下)是哈希映射/集合。


附注:
我不确定Alexandre Fenyo在他的评论中想要指出什么,但我同意哈希映射/集合不能保证查找和插入的时间复杂度为O(1),因为可能会发生碰撞。
为了最小化碰撞,哈希映射/集合需要具有适当的大小(或者具有相对廉价的方式来增长其内部结构),并且所使用的哈希函数设计不能产生太多的碰撞。
有关更多详细信息,请参阅维基百科的哈希表条目。
对于良好的实现,大多数情况下可以达到O(1),这就是我在上面回答中所说的"在大多数情况下"的意思。

英文:

You cannot avoid to read the input at least. That already costs O(n). So you need to check if an element needs to be excluded in O(1).

The data structure that comes in mind that could do that (at least in most cases) is a Hash-Map/-Set.


P.s.
I'm not 100% sure what Alexandre Fenyo wants to point out in his comments, but I agree that a Hash-Map/-Set cannot guarantee O(1) for lookup and insert because of possible collisions.
To minimize collisions the Hash-Map/-Set needs to be of adequate size (or have a relative cheap way to grow its internal structure) and the hash-function used must not create too many collisions because of its design.
For further details wikipedia hash-table .
For good implementations you get O(1) in most cases, that is what I mean with "in most cases" in my answer above.

答案2

得分: 1

O(n)表示线性复杂度。下面是一个以线性复杂度执行并检查所有项的示例代码。

你可以使用Set来为每个键建立排除索引,以将过滤复杂度降低到O(1)。下面是一个O(n) + O(m) =~ O(n)的示例代码:

const items = [
  { type: "a", name: "a1", color: "yellow" },
  { type: "b", name: "b1", color: "orange" },
];
const excludes = [
  { k: "color", value: "yellow" },
  { k: "name", value: "x" },
];


const excludeIndex = { type: new Set(), name: new Set(), color: new Set() };

// 填充排除索引:O(m)
excludes.forEach((exclude) => excludeIndex[exclude.k].add(exclude.value));

// 过滤项:O(n)
const result = items.filter(
  (item) => !excludeIndex.type.has(item.type) && !excludeIndex.name.has(item.name) && !excludeIndex.color.has(item.color),
);

console.log(result);

通常,我们应该使用一个变量来存储索引键,并迭代它们以使代码更灵活。然而,迭代索引键可能会让审阅者对复杂度产生困惑。键的数量是恒定的(或可以忽略不计),不会影响复杂度。

英文:

O(n) means linear complexity. Here is an example code that does it in a linear complexity and checks all the keys of items.

You can use a Set to index excludes for each key to reduce filtering complexity to O(1). Below is an example code for O(n) + O(m) =~ O(n)

const items = [
  { type: &quot;a&quot;, name: &quot;a1&quot;, color: &quot;yellow&quot; },
  { type: &quot;b&quot;, name: &quot;b1&quot;, color: &quot;orange&quot; },
];
const excludes = [
  { k: &quot;color&quot;, value: &quot;yellow&quot; },
  { k: &quot;name&quot;, value: &quot;x&quot; },
];


const excludeIndex = { type: new Set(), name: new Set(), color: new Set() };

// Populate Exclude Index: O(m)
excludes.forEach((exclude) =&gt; excludeIndex[exclude.k].add(exclude.value));

// Filter Items: O(n)
const result = items.filter(
  (item) =&gt; !excludeIndex.type.has(item.type) &amp;&amp; !excludeIndex.name.has(item.name) &amp;&amp; !excludeIndex.color.has(item.color),
);

console.log(result);

Normally, we should use a variable for storing index keys and iterate them to make the code more flexible. However, iterating index keys may confuse reviewers about the complexity. The number of keys is constant (or negligible) and does not affect complexity.

huangapple
  • 本文由 发表于 2023年8月11日 15:24:08
  • 转载请务必保留本文链接:https://go.coder-hub.com/76881464.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定