Javascript ES6 集合的计算/时间复杂度 [英] Javascript ES6 computational/time complexity of collections

问题描述

ES6 规范为 Keyed Collections(Set、Map、WeakSet 和 WeakMap)提供了什么时间复杂度(以大 O 表示法)?

What time complexity (in big-O notation) is provided by the ES6 specification for the Keyed Collections (Set, Map, WeakSet, and WeakMap)?

我和大多数开发人员的期望是，规范和实现将使用广泛接受的高性能算法，在这种情况下，Set.prototype.has、add 和 delete 在平均情况下都是 O(1).Map 和 Weak– 等价物也是如此.

My expectation, and I expect that of most developers, is that the specifications and implementations would use widely accepted performant algorithms, in which case Set.prototype.has, add and delete to all be O(1) in the average case. The same for the Map and Weak– equivalents.

我并不完全清楚实现的时间复杂度是否是强制性的，例如ECMAScript 2015 语言规范 - 第 6 版 — 23.2 设置对象.

It is not entirely apparent to me whether the time complexity of the implementations was mandated e.g. in ECMAScript 2015 Language Specification - 6th Edition — 23.2 Set Objects.

除非我误解了它(我当然很有可能会误解)，它看起来 ECMA 规范要求实现(例如 Set.prototype.has) 将使用线性时间 (O(n))算法.令我感到非常惊讶的是，规范不会强制要求甚至允许更高性能的算法，我很想解释为什么会这样.

Unless I misunderstand it (and it's certainly very possible I do), it looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm. It would strike me as exceedingly surprising that more performant algorithms would not be mandated or even permitted by the spec, and I would be very interested in an explanation for why this is the case.

推荐答案

来自 那个段落你链接到:

必须使用 [机制] 来实现 Set 对象，该机制平均提供与集合中元素数量次线性的访问时间.

您会在地图中找到相同的句子，WeakMaps 和 WeakSets.

You will find the same sentence for Maps, WeakMaps and WeakSets.

看起来 ECMA 规范要求实现(例如 Set.prototype.has)使用线性时间(O(n))算法.

It looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm.

否:

此Set 对象规范中使用的数据结构仅用于描述 Set 对象所需的可观察语义.它不是一个可行的实施模型.

The data structures used in this Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

可观察语义主要与可预测迭代顺序有关(仍然可以实现高效快速).尽管也允许使用树(具有对数访问复杂性)，但规范确实希望实现使用哈希表或类似的具有常量访问的东西.

The observable semantics are mostly related to the predictable iteration order (which still can be implemented efficient and fast). It is indeed expected by the specification that an implementation uses a hash table or something similar with constant access, though trees (with logarithmic access complexity) are allowed as well.

这篇关于Javascript ES6 集合的计算/时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！