【源码共读】yocto-queue 一个微型队列数据结构


theme: juejin
highlight: a11y-dark

我正在参与掘金会员专属活动-源码共读第一期,点击参与

yocto-queue是一个微型队列的数据结构,根据作者的介绍,如果在你一个数据量很大的数组上,大量的操作Array.pushArray.shift,那么你可以考虑使用yocto-queue来替代Array

因为Array.shift的时间复杂度是O(n),而Queue.dequeue的时间复杂度是O(1),这对于大量的数据来说,性能上的提升是非常明显的。

时间复杂度和空间复杂度

学习算法和数据结构的时候,我们经常会听到时间复杂度和空间复杂度,这两个概念是什么呢?

时间复杂度

时间复杂度是指一个算法执行所耗费的时间,它是一个函数,这个函数的变量是问题规模的函数;

通常会使用大O符号来表示时间复杂度,比如O(n)O(n^2)O(logn)等等,这就是大 O 表示法(Big O notation)。

O代表的是算法的渐进时间复杂度(asymptotic time complexity),也就是说,随着问题规模的增大,算法的执行时间的增长率和O中的函数相同,称作渐进时间复杂度。

O(1)表示算法的执行时间与问题规模无关,也就是说,不管问题规模有多大,算法执行所耗费的时间都是一样的,这种算法称为时间复杂度为常数阶的算法。

O(n)表示算法的执行时间与问题规模成正比,也就是说,随着问题规模的增大,算法执行所耗费的时间也随之增大,这种算法称为时间复杂度为线性阶的算法。

O(n^2)表示算法的执行时间与问题规模成平方比,也就是说,随着问题规模的增大,算法执行所耗费的时间呈二次方增长,这种算法称为时间复杂度为平方阶的算法。

通过上面的介绍,我们可以将O比喻成函数,O(1)就是一个常数函数,O(n)就是一个线性函数,O(n^2)就是一个平方函数,O(logn)就是一个对数函数。

说了这么多概念性的问题,不如直接来看看代码;

例如,我们有一个数组,我们要遍历这个数组,然后将数组中的每个元素都乘以2,那么我们可以这么写:

function multiplyBy2(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

这段代码的时间复杂度是O(n),因为我们遍历了数组,所以时间复杂度就是O(n)O代表这个函数,n代表问题规模,也就是数组的长度,组合起来就是O(n)

再直观一点,我们可以这么理解,当数组的长度为n时,我们需要执行n次循环,所以时间复杂度就是O(n),用代码表示就是:

function O(n) {
    for (let i = 0; i < n; i++) {
        // do something
    }
}

O(1); // O(1)
O(2); // O(2)
O(3); // O(3)
O(n); // O(n)

空间复杂度

空间复杂度是指一个算法执行所耗费的内存空间,它是一个函数,这个函数的变量是问题规模的函数;

和时间复杂度一样,空间复杂度也有O(1)O(n)O(n^2)O(logn)等等,它们的含义和时间复杂度一样,只不过它们是表示算法执行所耗费的内存空间的增长率。

当然空间复杂度计算的不是内存消耗,而是变量的个数,例如冒泡排序的空间复杂度是O(1),因为它只需要一个变量temp

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

而快速排序的空间复杂度是O(logn),因为它需要一个变量pivot,而且它是递归的,所以空间复杂度是O(logn)

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

源码分析

上面了解了时间复杂度和空间复杂度的概念,那么我们开始正式分析yocto-queue的源码;

代码不多,可以直接通过github1s在线阅读,然后使用浏览器控制台来查看效果;

代码分析

先来看一下yocto-queue的使用方式:

  • 安装
npm install yocto-queue
  • 使用
import Queue from 'yocto-queue';

const queue = new Queue();

queue.enqueue('🦄');
queue.enqueue('🌈');

console.log(queue.size);
//=> 2

console.log(...queue);
//=> '🦄 🌈'

console.log(queue.dequeue());
//=> '🦄'

console.log(queue.dequeue());
//=> '🌈'

然后再来看一下yocto-queue的代码:

/*
How it works:
`this.#head` is an instance of `Node` which keeps track of its current value and nests another instance of `Node` that keeps the value that comes after it. When a value is provided to `.enqueue()`, the code needs to iterate through `this.#head`, going deeper and deeper to find the last value. However, iterating through every single item is slow. This problem is solved by saving a reference to the last value as `this.#tail` so that it can reference it to add a new value.
*/

class Node {
    value;
    next;

    constructor(value) {
        this.value = value;
    }
}

export default class Queue {
    #head;
    #tail;
    #size;

    constructor() {
        this.clear();
    }

    enqueue(value) {
        const node = new Node(value);

        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }

        this.#size++;
    }

    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }

        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }

    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }

    get size() {
        return this.#size;
    }

    * [Symbol.iterator]() {
        let current = this.#head;

        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

可以直接直接粘贴到浏览器控制台中运行

构造函数

首先来看一下Queue的构造函数:

class Queue {
  #head;
  #tail;
  #size;

  constructor() {
    this.clear();
  }
}

一个Queue类,它有三个私有属性:#head#tail#size

class中,如果属性名前面加上#,表示这个属性是私有属性,外部是无法访问的;

  • #head:指向队列的头部;
  • #tail:指向队列的尾部;
  • #size:队列的长度;

然后在构造函数中调用了this.clear()方法,这个方法的作用是清空队列,代码如下:

class Queue {
    clear() {
        this.#head = undefined;
        this.#tail = undefined;
        this.#size = 0;
    }
}

enqueue

接下来看一下enqueue方法:

class Queue {
    enqueue(value) {
        const node = new Node(value);

        if (this.#head) {
            this.#tail.next = node;
            this.#tail = node;
        } else {
            this.#head = node;
            this.#tail = node;
        }

        this.#size++;
    }
}

enqueue方法的作用是向队列中添加一个元素;

首先创建一个Node实例,然后判断this.#head是否存在,如果存在,说明队列中已经有元素了,那么就把新创建的Node实例添加到队列的尾部;

如果this.#head不存在,说明队列中还没有元素,那么就把新创建的Node实例添加到队列的头部;

最后,队列的长度加一;

这里使用到了一个Node类,它的作用是用来保存队列中的元素的,代码如下:

class Node {
    value;
    next;

    constructor(value) {
        this.value = value;
    }
}
  • value:指向的是队列中的元素;
  • next:指向下一个Node实例;

dequeue

接下来看一下dequeue方法:

class Queue {
    dequeue() {
        const current = this.#head;
        if (!current) {
            return;
        }

        this.#head = this.#head.next;
        this.#size--;
        return current.value;
    }
}

dequeue方法的作用是从队列中移除一个元素;

首先获取队列的头部元素,然后判断current是否存在,如果不存在,说明队列中没有元素,那么就直接返回;

如果current存在,说明队列中有元素,那么就把队列的头部元素移除,然后把队列的长度减一;

最后,返回移除的元素;

图例

一个队列结构只会有两个操作:入队和出队,下面通过一个图例来说明一下;

入队时,会把新的元素添加到队列的尾部;

出队时,会把队列的头部元素移除;

graph TD
#head --> Node0
Node0 -->|value| Current0
Node0 -->|next| Node1

Node1 -->|value| Current1
Node1 -->|next| Node2

Node2 -->|value| Current2
Node2 -->|next| Node3

Node3 -->|value| Current3
Node3 -->|next| Node_n

Node_n -->|value| Current_n

#tail --> Node_n

上面的图例中,Node0表示队列的头部元素,Node_n表示队列的尾部元素;

Current0表示队列中的第一个元素,Current_n表示队列中的最后一个元素;

在队列中,只会关心头部和尾部的元素,头部的元素用于弹出队列,尾部的元素用于添加元素;

在上面的图例中,如果我们执行dequeue方法,那么就会把Node0移除,然后把Node1设置为队列的头部元素;

graph TD
dequeue -->|出队列 #head| #head

Node0 -->|value| Current0
Current0 -->|返回结果| End
Node0 -->|next| Node1

#head -->|修改指向为 Node1| Node1


Node1 -->|value| Current1
Node1 -->|next| Node2

Node2 -->|value| Current2
Node2 -->|next| Node3

Node3 -->|value| Current3
Node3 -->|next| Node_n

Node_n -->|value| Current_n

#tail --> Node_n

上面的dequeue方法执行完毕后,队列的头部元素就变成了Node1

Node0因为没有任何引用指向它,所以会被垃圾回收机制回收;

如果我们执行enqueue方法,那么就会把新的元素添加到队列的尾部:

graph TD
#head --> Node0
Node0 -->|value| Current0
Node0 -->|next| Node1

Node1 -->|value| Current1
Node1 -->|next| Node2

Node2 -->|value| Current2
Node2 -->|next| Node3

Node3 -->|value| Current3
Node3 -->|next| Node_n

Node_n -->|next 指向| newNode
newNode -->|value| newData

#tail -->|修改指向| newNode

上面的enqueue方法执行完毕后,队列的尾部元素就变成了newNode

迭代器

yocto-queue到最后还提供了一个迭代器,用于遍历队列中的元素;

class Queue {
    // ...

    *[Symbol.iterator]() {
        let current = this.#head;

        while (current) {
            yield current.value;
            current = current.next;
        }
    }
}

上面的代码中,使用了一个generator函数,它会返回一个迭代器;

迭代器中,会从队列的头部元素开始遍历,然后把每个元素的值返回出去;

迭代器的使用

迭代器是es6中的一个新特性,它可以用于遍历数据结构中的元素,使用起来也非常简单,只需要在数据结构上调用Symbol.iterator方法即可;

const obj = {
    [Symbol.iterator]() {
        let i = 0;

        return {
            next() {
                return {
                    value: i++,
                    done: i > 10
                };
            }
        };
    }
};

for (const item of obj) {
    console.log(item);
}

上面的代码中,我们定义了一个对象,它的Symbol.iterator方法返回了一个迭代器;

一个迭代器是一个对象,它有一个next方法,每次调用next方法,都会返回一个对象,这个对象中包含了当前元素的值和一个done属性,表示是否已经遍历完毕;

可以使用generator函数来简化上面的代码:

const obj = {
    *[Symbol.iterator]() {
        let i = 0;

        while (i < 10) {
            yield i++;
        }
    }
};

for (const item of obj) {
    console.log(item);
}

上面的代码中,我们使用了generator函数来简化迭代器的定义;

参考:

总结

yocto-queue是一个非常简单的队列实现,它的核心是使用了链表来存储数据;

链表的优点是插入和删除元素的时间复杂度是O(1),但是查找元素的时间复杂度是O(n),不过对于队列来说,查找元素的操作是不需要的;

对比于数组,每次插入和删除元素都需要移动元素,所以时间复杂度是O(n),但是查找元素的时间复杂度是O(1)

所以正如文章开头,作者提到的,对于一个大数组来实现队列,效率是非常低的,而应该使用链表来实现(因为这个库的核心实现就是链表,所以肯定优先推荐用这个库=);

通过阅读yocto-queue的源码,我们学习到了很多:

  • 时间复杂度、空间复杂度的概念
  • 链表的实现
  • 如何使用es6Symbol.iterator来实现可迭代对象;
  • 如何使用es6generator函数来实现迭代器;
  • 数组、队列、链表的区别;
© 版权声明
THE END
喜欢就支持一下吧
点赞6 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容