发表于 |

快速排序的一般javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
function Sort(num) {
  this.totalNum = num
  this.dataStore = []
  this.genData = function setData() {
    for (let i = 0; i < this.totalNum; ++i) {
      this.dataStore[i] = Math.floor(Math.random() * (this.totalNum + 1))
    }
  }

  this.quickSort = function quickSort(data) {
    let len = data.length
    if (len <= 1) {
      return [...data]
    }
    let left = []
    let right = []
    let pivot = data[0]
    for (let i = 1; i < len; i++) {
      let item = data[i]
      if (item < pivot) {
        left.push(item)
      } else {
        right.push(item)
      }
    }
    return this.quickSort(left).concat(pivot, this.quickSort(right))
  }

  this.quickSort2 = function quickSort2 (data) {
    let len = data.length
    if (len <= 1) {
      return [...data]
    }
    let left = []
    let middle = []
    let right = []
    let pivotLeft = data[0]
    let pivotRight = data[len - 1]
    for (let i = 1; i < len; i++) {
      let item = data[i]
      if (item < pivotLeft) {
        left.push(item)
      } else if (item > pivotRight) {
        right.push(item)
      } else {
        middle.push(item)
      }
    }
    return this.quickSort2(left).concat(pivotLeft, this.quickSort2(middle)).concat(pivotRight, this.quickSort2(right))
  }

  this.quickSort3 = function quickSort3 (start, end) {
    if (start >= end) {
      return
    }
    let data = this.dataStore
    let i = start
    let j = end
    let pivot = data[i]
    while(i < j) {
      while(i < j && data[j] >= pivot) {
        j--;
      }
      data[i] = data[j]
      while(i < j && data[i] <= pivot) {
        i++;
      }
      data[j] = data[i]
    }
    data[i] = pivot
    this.quickSort3(start, i - 1)
    this.quickSort3(j + 1, end)
  }

  this.quickSort4 = function quickSort4 (start, end) {
    if (start >= end) {
      return
    }
    let data = this.dataStore
    let i = start
    let j = end
    let mid = Math.floor((end - start) / 2)
    let pivot = data[mid]
    data[mid] = data[i]
    data[i] = pivot
    while(i < j) {
      while(i < j && data[j] >= pivot) {
        j--;
      }
      data[i] = data[j]
      while(i < j && data[i] <= pivot) {
        i++;
      }
      data[j] = data[i]
    }
    data[i] = pivot
    this.quickSort4(start, i - 1)
    this.quickSort4(j + 1, end)
  }

  this.genData()

  let start = Date.now()
  this.quickSort4(0, this.totalNum - 1)
  let end = Date.now()
  console.log('quickSort4耗时： ' + (end - start) + '毫秒')
}

发表于 |

每次git clone 下来项目然后npm install之后，遇到各种报错。

这次是这个：

1
2
3
4
5
...
...
...
ERROR in ./src/App.vue
vue-loader was used without the corresponding plugin. Make sure to include VueLoaderPlugin in your webpack config.

大概率是哪个npm包的版本不对。然后一查，果然，vue-loader用的 latest。

在当时开发人的场景下，版本号latest是可行的。但是等后面的人接手以后，latest可能就不是开发时候的版本号了，所以建议package.json文件里面的npm包名，不要使用latest，而是精确指定到某个大版本，比如^14.2.2。这样不管以后如何升级，都能保证，npm install 之后项目能跑起来。

发表于 |

问题描述

  • 写一个function，输入两个字符串序列（wordA, wordB），查找他们最长公共子序列并输出。
  • 例如 wordA = ‘abcdde’, wordB = ‘bcdff’。输出：’bcd’。

思路分析

没有哪个问题是两个for循环解决不了的，如果有那就三个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 三个for循环
function maxSub(wordA, wordB) {
	let lenA = wordA.length;
	let lenB = wordB.length;
	if (lenA > lenB) {
		let temp = wordA;
		wordA = wordB;
		wordB = temp;
		temp = lenA;
		lenA = lenB;
		lenB = temp;
	}
	let maxSubStr = '';
	for (let i = 0; i < lenA; i++) {
		for (l = 1; l <= lenA - i; l++) {
			let subStrA = wordA.slice(i, i + l);
			for (let j = 0; j < lenB; j++) {
				let subStrB = wordB.slice(j, j + l)
				if (subStrA === subStrB && l > maxSubStr.length) {
					maxSubStr = subStrA;
				}
			}
		}
	}
	return maxSubStr;
}

function genRandStr(n) {
	let charArr = 'ABCDEFGHJKMNPQRSTWXYZabcdefhijkmnprstwxyz2345678';
	let charLen = charArr.length;
	let randStr = '';
	for (i = 0; i < n; i++) {
		randStr += charArr.charAt(Math.floor(Math.random() * charLen));
	}
	return randStr;
}

function testFunc(n) {
	let wordA = genRandStr(n);
	let wordB = genRandStr(n);
	let startTime = Date.now();
	let result = lcs(wordA, wordB);
	let endTime = Date.now();
	console.log(result, endTime - startTime);
}

// 两个for循环
function lcs(word1, word2) {
  var max = 0;
  var index = 0;
  var lcsarr = new Array(word1.length + 1);
    for (var i = 0; i <= word1.length + 1; ++i) {
      lcsarr[i] = new Array(word2.length + 1);
      for (var j = 0; j <= word2.length + 1; ++j) {
        lcsarr[i][j] = 0;
      }
    }
    for (var i = 1; i <= word1.length; ++i) {
      for (var j = 1; j <= word2.length; ++j) {
        if (word1[i - 1] == word2[j - 1]) {
          lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
        } else {
          lcsarr[i][j] = 0;
        }
        if (max < lcsarr[i][j]) {
          max = lcsarr[i][j];
          index = i;
        }
      }
    }
    var str = "";
    if (max == 0) {
      return "";
    } else {
      for (var i = index - max; i < index; ++i) {
        str += word1[i];
      }
    return str;
    }
}

经过实测，maxStr方法在计算长度为1000的字符串时，需要的时间为10s以上，而lcs方法在计算1000长度的字符串时，耗时在20毫秒级别，而在10000长度时，耗时3s左右。

关于优化（空间换时间）

所有针对时间上的优化，都可以归为用空间换时间，三个for循环的方法，虽然耗时长，但是中间环节不生成多余的数据。两个for循环的优化算法，虽然时间上短了，但是计算过程中，需要一个lcsarr二维数组，来存储计算过程中生成的每一个值，然后保存起来，以便后续查找使用。

这和平时用过的缓存思想极其相似，拿斐波那契数列来举例，常规的做法是通过递归调用，但是耗时会很长，如果在递归的过程中假如cache数组缓存，可以明显提高时间，但是多出来cache存储空间就是换取时间的代价。

这里我们顺便考虑下排序算法，初级排序（冒泡，插入，选择）时间复杂度为O(n^2)，高级排序算法（希尔，堆排序，快速）时间复杂度O(nlogn)，在不引入额外空间的条件下（事实上也没有额外办法引入），排序的时间复杂度最多限制在了nlogn这个数量级，之所以能从n^2缩减到n*logn也是因为在自身数组空间的基础上，充分利用了自身空间做的一个数据交换（比如快速排序，在自己内部通过二分法，每次处理一半数据）达到了时间上的缩减。

发表于 |

动态规划求最长公共子序列的js实现

动态规划类似于递推算法，典型的动态规划模型–斐波那契数列，可以用递归来实现，但是耗费内存空间比较大，如果不做任何缓存优化，计算1000个数的时候基本就很耗费时间了，尽管可以在递归的过程中，用一个cache数组缓存已经算出的值，但是函数的嵌套带来的内存开销也会影响，es6的尾调用优化很好的解决了函数嵌套带来的内存溢出问题。但是真正的精髓算法还是属于动态规划。

最长公共子序列也是如此，直接看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function lcs(word1, word2) {
  var max = 0;
  var index = 0;
  var lcsarr = new Array(word1.length + 1);
    for (var i = 0; i <= word1.length + 1; ++i) {
      lcsarr[i] = new Array(word2.length + 1);
      for (var j = 0; j <= word2.length + 1; ++j) {
        lcsarr[i][j] = 0;
      }
    }
    for (var i = 1; i <= word1.length; ++i) {
      for (var j = 1; j <= word2.length; ++j) {
        if (word1[i - 1] == word2[j - 1]) {
          lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
        } else {
          lcsarr[i][j] = 0;
        }
        if (max < lcsarr[i][j]) {
          max = lcsarr[i][j];
          index = i;
        }
      }
    }
    var str = "";
    if (max == 0) {
      return "";
    } else {
      for (var i = index - max; i < index; ++i) {
        str += word1[i];
      }
    return str;
    }
}

发表于 |

yarn start启动项目的时候一个报错

Fatal error in ../deps/v8/src/api.cc, line 1244

控制台报错信息太少，一度以为项目有问题，但是想想也不太可能，毕竟是线上运行的正式项目，不可能跑步起来，所以还是慢慢的摸索，找问题的根源。

因为错误信息实在是太少了，如果是以前的缺少模块 Cant resolve module... 这种应该很快能知道错误在哪，但是这次一开始报的错就看不太懂，错误信息少，而且错误说明模糊，就只有一个exit code 132，大概也猜到可能是yarn 版本，或者是node版本引起的，然后试着降低了node版本（从10.几 降到了 8.几）但是还是不行，大概有点放弃，然后降低了下yarn版本，（从1.几降到了0.23.0）。但是没什么卵用，后来终于在网上看到了一个靠谱的明确了node版本号的解答，然后试着再把node降到了6.11.2

终于，这次可以运行成功了~

然后，我刚准备在readme.md里面把这个注意点加上，防止后来的人重蹈覆辙，结果，我在readme的第一行，看到了

node 版本 6.13.0

内心一万匹曹尼玛略过