亲宝软件园·资讯

展开

yocto queue微型队列数据结构源码解读

田八 人气:0

引言

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('

加载全部内容

相关教程
猜你喜欢
用户评论