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

问题描述

我的我的是什么时候复杂的（在大O表示法中）是由ES6规范提供的关键集合（Set，Map，WeakSet和WeakMap）期望，我期望大多数开发人员的规范和实现将使用广泛接受的演示算法，在这种情况下 Set.prototype.has ，添加和删除在平均情况下为O（1）。对于 Map 和 Weak - 等同的。

对我来说，实现的时间复杂度是否被强制要求是不完全明白的在 ECMAScript 2015语言规范 - 第6版 - 23.2设置对象

除非我误解它（这当然是非常可能的），它看起来ECMA规范要求实现（例如 Set.prototype.has ）是使用线性时间（O（n））算法。这将使我非常惊讶，更多的性能算法不会被强制甚至被规范允许，我将非常感兴趣的解释为什么会这样。

解决方案

从非常段落您链接到：

设置对象必须使用[机制]实现，平均而言，提供访问时间是集合中元素数量的子线。

您将找到与地图，WeakMaps 和 WeakSets 。

它看起来ECMA规范要求实施（例如， Set.prototype.has）将使用线性时间（ O（n））算法。

否：

Set 对象规范仅用于描述Set对象所需的可观察语义。它不是一个可行的实现模型。




可观察的语义主要与可预测的迭代顺序相关（这仍然可以实施高效快捷）。实际上，通过规范，实现使用散列表或与常量访问类似的东西，尽管也允许使用树（具有对数访问复杂性）。

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

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.

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.

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.

解决方案

Right from that very paragraph your linked to:

Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection.

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

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

No:

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屋！