复杂度分析
大 O 复杂度表示法
常见的有 O(1), O(n), O(logn), O(nlogn)
时间复杂度除了大 O 表示法外, 还有以下情况
最好情况时间复杂度
最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
代码执行效率分析
大多数情况下, 代码执行的效率可以采用时间复杂度分析, 但是大 O 表示法通常会省略常数.
但是在工业级实现中, 真正的执行效率通常会考虑多方面:
时间复杂度
空间复杂度
缓存友好
指令条数
性能退化(如哈希冲突解决方案等)
等
以上是理论层级, 对于前端开发来说, 如果你开发的是基础库会被广泛使用时, 只是基于理论的分析是不够的.
此时就可以借助一些基准库来对你的模块进行测试: benchmark.JS https://benchmarkjs.com/
数据结构
1. 数组
特点: 连续内存, 支持下标访问, 缓存友好, 时间复杂度 O(1)
深入: 从 JS 继承链可以知道在 JS 中的 Array 数组继承于 Object, 在某些情况下数组会退化为哈希表结构[Dictionary].
思考: 考虑如下情况, 浏览器会怎样存储该数组?
- let myArray = [10000];
- myArray[0] = 0;
- myArray[9999] = 1;
2. 链表
特点: 非连续内存, 查找元素时间复杂度最坏情况 O(n), 最好情况 O(1).
单向链表
双向链表
深入: 判断链表是否有环形?
使用一个步进为 1, 和一个额外的步进为 2 的参数, 如果在遍历完之前相遇, 则有环.
3. 栈
特点: 先进后出, 后进先出, 底层结构可以为数组或链表.
场景: 函数调用时对当前执行环境进行入栈操作, 调用完成后出栈恢复调用前上下文.
深入: 递归调用时连续入栈操作, 如果递归层级过深造成堆栈溢出.
比如 AngularJS 中的脏值检查嵌套深度上线为 10.
思考: 浏览器的前进后退功能可否用栈实现?
使前进栈和后退栈的双栈结构
4. 队列
特点: 先进先出, 底层结构可以为数组或链表.
无阻塞队列
基于链表
阻塞队列
基于数组的循环队列
深入: JS 中的 Macro 队列和 Micro 队列
5. 跳表
底层为链表, 为了增加查找效率, 在链表基础上, 以 (2/3/4/../n) 个节点增加一层查找链表
特点: '支持区间查找', 支持动态数据结构, 需要额外的存储空间来存储索引链节点
时间复杂度: 基于链表的查找时间复杂度由跳表层高决定
场景: 如 Redis 中的有序集合
6. 散列表
底层为数组结构, 使用散列函数计算 key 将其映射到数组中的下标位置.
散列函数要求:
散列值为非负整数
key1 = key2, 则 hash(key1) = hash(key2)
key1 != key2, 则 hash(key1) != hash(key2)
常见的哈希算法有: MD5, SHA, CRC 等.
散列冲突:
开放寻址
线性探测: 散列冲突时, 依次往后查找空闲
双重散列: 使用多个散列函数, 如果第一个散列值被占用, 则用第二个散列值
链表法
散列冲突时, 在一级数据后链接一个链表结构. 该链表可以是单 / 双链, 或树形链表
装载因子: 整个数组中已经被使用的位置 / 总位置
动态扩容: 当装载因子达到某个限定值 (如: 0.75) 时, 对整个底层数组进行扩容
注: 工业级实现中, 动态扩容并不是一次完成的.
一次完成的动态扩容会造成性能瓶颈, 一般是在装载因子达到设定值时, 申请一个新的数组. 在后续的每次操作时, 将一个数据从原数组搬到新数组, 直到原数组为空.
JavaScript 对象数据结构
我在另一篇文章中有将到 JS 中的对象在底层存储的时候会有好几种模式, 下面我们结合源码来详细分析一下
- //https://github.com/v8/v8/blob/master/src/objects/js-objects.h
- // 我们先来看 JS 中 object 的定义, 继承自 JSReceiver
- // Line 278
- class JSObject : public JSReceiver {
- // 省略...
- }
- // Line 26
- // 接下来再看, JSReceiver 继承自 HeapObject, 并且有几个重要属性
- // JSReceiver includes types on which properties can be defined, i.e.,
- // JSObject and JSProxy.
- class JSReceiver : public HeapObject {
- public:
- NEVER_READ_ONLY_SPACE
- // Returns true if there is no slow (IE, dictionary) backing store.
- // 是否有快速属性模式
- inline bool HasFastProperties() const;
- // Returns the properties array backing store if it exists.
- // Otherwise, returns an empty_property_array when there's a Smi (hash code) or an empty_fixed_array for a fast properties map.
- // 属性数组
- inline PropertyArray property_array() const;
- // Gets slow properties for non-global objects.
- // 字典属性
- inline NameDictionary property_dictionary() const;
- // Sets the properties backing store and makes sure any existing hash is moved
- // to the new properties store. To clear out the properties store, pass in the
- // empty_fixed_array(), the hash will be maintained in this case as well.
- void SetProperties(HeapObject properties);
- // There are five possible values for the properties offset.
- // 1) EmptyFixedArray/EmptyPropertyDictionary - This is the standard
- // placeholder.
- //
- // 2) Smi - This is the hash code of the object.
- //
- // 3) PropertyArray - This is similar to a FixedArray but stores
- // the hash code of the object in its length field. This is a fast
- // backing store.
- //
- // 4) NameDictionary - This is the dictionary-mode backing store.
- //
- // 4) GlobalDictionary - This is the backing store for the
- // GlobalObject.
- // 初始化属性
- inline void initialize_properties();
由上可知对象有快速属性和字典属性两种模式, 快速属性由数组存储, 字典属性采用 hash 表存储.
快速属性这里不深入, 我们接下来看看 NameDictionary 的底层结构
- // https://github.com/v8/v8/blob/master/src/objects/dictionary.h
- // 我们先来看看继承链
- // Line 202
- class V8_EXPORT_PRIVATE NameDictionary : public BaseNameDictionary<NameDictionary, NameDictionaryShape>{
- }
- // Line 128
- class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) BaseNameDictionary : public Dictionary<Derived, Shape> {
- }
- // Line 26
- class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary : public HashTable<Derived, Shape> {
- }
- // 由上可知继承自 HashTable, 我们来看 HashTable 的定义
- // https://github.com/v8/v8/blob/master/src/objects/hash-table.h
- // 并且在文件开头的注释已经很详细了
- // HashTable is a subclass of FixedArray that implements a hash table that uses open addressing and quadratic probing.
* 重要: hash 表使用数组为基础数据, 并在其上实现了开放寻址和二次探测
- // In order for the quadratic probing to work, elements that have not yet been used and elements that have been deleted are distinguished.
- // Probing continues when deleted elements are encountered and stops when unused elements are encountered.
* 为了使二次探测工作正常, 未使用 / 被删除的元素将被标记删除而不是直接删除
- // - Elements with key == undefined have not been used yet.
- // - Elements with key == the_hole have been deleted.
- // 以下会被使用的 hash 表派生类
- // Line 292
- template <typename Derived, typename Shape>
- class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) ObjectHashTableBase
- : public HashTable<Derived, Shape> {}
接下来我们看看 V8 在实现 hash 表时的几个重要行为和参数
// https://github.com/v8/v8/blob/master/src/objects/objects.cc
1. 扩容
- // Line 7590
- // 下面源代码是新增一个元素后的逻辑
- ObjectHashTableBase<Derived, Shape>::Put(Isolate* isolate, Handle<Derived> table, Handle<Object> key, Handle<Object> value, int32_t hash) {
- int entry = table->FindEntry(roots, key, hash);
- // Key is already in table, just overwrite value.
- // key 已经存在, 覆盖值
- if (entry != kNotFound) {
- table->set(Derived::EntryToValueIndex(entry), *value);
- return table;
- }
- // 如果 33% 以上元素都被删除了, 考虑重新 hash
- // Rehash if more than 33% of the entries are deleted entries.
- // TODO(jochen): Consider to shrink the fixed array in place.
- if ((table->NumberOfDeletedElements() <<1)> table->NumberOfElements()) {
- table->Rehash(roots);
- }
- // If we're out of luck, we didn't get a GC recently, and so rehashing isn't enough to avoid a crash.
- // 如果没有足够的预估空位, 按二倍大小进行重新 hash
- if (!table->HasSufficientCapacityToAdd(1)) {
- int nof = table->NumberOfElements() + 1;
- int capacity = ObjectHashTable::ComputeCapacity(nof * 2);
- if (capacity> ObjectHashTable::kMaxCapacity) {
- for (size_t i = 0; i <2; ++i) {
- isolate->heap()->CollectAllGarbage(
- Heap::kNoGCFlags, GarbageCollectionReason::kFullHashtable);
- }
- table->Rehash(roots);
- }
- }
- // Line 6583.
- // 下面是计算预估空位的逻辑
- HashTable<Derived, Shape>::EnsureCapacity(Isolate* isolate, Handle<Derived> table, int n, AllocationType allocation) {
- if (table->HasSufficientCapacityToAdd(n)) return table;
- int capacity = table->Capacity();
- int new_nof = table->NumberOfElements() + n;
- const int kMinCapacityForPretenure = 256;
- bool should_pretenure = allocation == AllocationType::kOld ||
- ((capacity> kMinCapacityForPretenure) &&
- !Heap::InYoungGeneration(*table));
- Handle<Derived> new_table = HashTable::New(
- isolate, new_nof,
- should_pretenure ? AllocationType::kOld : AllocationType::kYoung);
- table->Rehash(ReadOnlyRoots(isolate), *new_table);
- return new_table;
- }
2. 收缩
- // Line 6622
- HashTable<Derived, Shape>::Shrink(Isolate* isolate,
- Handle<Derived> table,
- int additionalCapacity) {
- int capacity = table->Capacity();
- int nof = table->NumberOfElements();
- // Shrink to fit the number of elements if only a quarter of the capacity is filled with elements.
- // 当只有 1/4 的装载量时, 进行收缩
- if (nof> (capacity>> 2)) return table;
- // Allocate a new dictionary with room for at least the current number of
- // elements + {additionalCapacity}. The allocation method will make sure that
- // there is extra room in the dictionary for additions. Don't go lower than
- // room for {kMinShrinkCapacity} elements.
- int at_least_room_for = nof + additionalCapacity;
- int new_capacity = ComputeCapacity(at_least_room_for);
- if (new_capacity <Derived::kMinShrinkCapacity) return table;
- if (new_capacity == capacity) return table;
- const int kMinCapacityForPretenure = 256;
- bool pretenure = (at_least_room_for> kMinCapacityForPretenure) &&
- !Heap::InYoungGeneration(*table);
- Handle<Derived> new_table =
- HashTable::New(isolate, new_capacity,
- pretenure ? AllocationType::kOld : AllocationType::kYoung,
- USE_CUSTOM_MINIMUM_CAPACITY);
- table->Rehash(ReadOnlyRoots(isolate), *new_table);
- return new_table;
- }
来源: http://www.bubuko.com/infodetail-3094890.html