每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文，欢迎关注开源日报。交流QQ群：202790710；微博：https://weibo.com/openingsource；电报群 https://t.me/OpeningSourceOrg
今日推荐开源项目：《JS 验证库 v8n》传送门：GitHub链接
推荐理由：这是一个可以用来做各种各样细的验证的库，它里面的语法看起来和普通的语法很像所以很容易就能理解，而且它的确提供了各种各样方面的验证方式，从检查所有的字母是不是都是小写到字符串的开头结尾，有兴趣的朋友可以尝试一下。
今日推荐英文原文：《Algorithms: Common edge cases in JS》作者：Jeremy Gottfried
原文链接：https://medium.com/jeremy-gottfrieds-tech-blog/algorithms-common-edge-cases-in-js-ce35a2d47674
推荐理由：极端情况，有的情况兴许你的程序一百年也见不到一次，但是为了预防可能出现的各种情况，我们还是应当改进程序以应对极端情况
Algorithms: Common edge cases in JS
Algorithms are the bedrock of computer programming. Algorithms are built to handle specific data structures with a range of accepted parameters. An edge case is a problem or situation that occurs only at an extreme (maximum or minimum) operating parameter. As programmers, how can we predict these cases in order to protect our app from breaking?
I will demonstrate some common edge cases in a basic bubble sort algorithm:
// bubbleSort.js
function bubbleSort(array) {
var swapped;
do {
swapped = false;
for(var i = 0; i < array.length; i++) {
if(array[i] > array[i + 1]) {
swap(array, i, i + 1);
swapped = true;
}
}
} while(swapped);
return array;
}function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}1. Accepted data structure
The first major edge case is the unaccepted data structure. My bubble sort algorithm only works predictably for arrays. Javascript will not prevent you from inputting other data structures in the function, such as normal objects. For example, what happens if I input this object:
var obj = {0: 0,
1: 1,
2: 2,
3: 3}
This will do some very strange things inside the for loop, but ultimately, our algorithm will return the original object.
--> obj
That may not be what we want! If the algorithm is going to be truly fool proof, we should test that our data structure is an array, and handle it somehow. Here I will return false so that we can handle unwanted data structures as an error in our program:
if (!Array.isArray(arr)) {
return false
}
This will also return false for falsey values like null or undefined.
2. Emptiness
An empty array would not break this specific sorting algorithm, but empty values are something important to look out for:
bubbleSort([]) --> []
In the context of many programs, we want to handle an empty array differently so that it doesn’t break something in our program further down the line:
if (!arr[0]) {
return false
}
or
if (arr.length === 0) {
return false
}
For algorithms that accept different data structures and types, we should also look out for emptiness. Here are some common ones:
var str = ''
var obj = {}
var arr = []
var num = 0
If our algorithm iterates through nested data structures, we may also want to check for nested emptiness like this:
[[],[],[],[[]],[[[]]]]
3. Accepted types
The next big case to test for is accepted types inside our array. Our bubbleSort algorithm sorts strings based on their Unicode values. That means that capital letters will go before lowercase:
bubbleSort([a,A,b,B]) ---> [A,B,a,b]
If we want the algorithm to sort strings independent of capitalization, we may want to handle that:
if (arr[j-1].toLowerCase > arr[j].toLowerCase) {
var temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
Another case you may want to handle are string numbers vs normal numerical values. Here is one strange example of this:
2 > '2' ---> false 2 < '2' ---> false 2 === '2' ---> false 2 == '2' ---> true
In the case of two equal numbers, where one is a string, the only operator that evaluates to true is == . It gets even more tricky if there is a letter in the numerical string.
1 > '1a' ---> false 1 < '1a' ---> false 1 === '1a' ---> false 1 == '1a' ---> false 2 > '1a' ---> false 2 < '1a' ---> false
This could lead to some strange results in our sorting algorithm. Therefore, we may want to only accept numbers and not strings, or handle the different types separately.
Another type to be aware of is the boolean value. true is loosely equal to 1 while false is loosely equal to 0 .
true == 1 ---> true false == 0 ---> true true > false ---> true true < 2 ---> true true < 'a' ---> false false < 'a' ---> false
We may not want to allow boolean values in our algorithm, especially if we are sorting an array of strings. This includes falsey values like null, undefined and NaN , which will all act strange when passed into a comparison operator.
The falsey data types all act differently in the comparison operators:
null < 2 ---> true null == 1 ---> false null > 0 ---> false null === null ---> true undefined < 2 ---> false undefined > 0 ---> false undefined == 1 --> false undefined === undefined ---> true NaN === NaN ---> false NaN > 0 ---> false NaN < 2 ---> false NaN == 1 ---> false
You may want to exclude these from your sorting algorithm.
4. Large Values
In our case, we should be looking out for extremely large arrays. What happens if our function is given an array with length greater than 1 x 10¹⁰⁰?
Here is where Big O notation comes in.
Big O complexity
Big O complexity is a measure of algorithm efficiency. It makes a big difference when we are dealing with large data sets. Big O has two variables — time and memory space. Memory is important because it can be break our algorithm if large amounts of data are passed as parameters. Every computer program stores data in stack and heap memory. Stack memory is much faster to access but there’s less of it. How does this relate to algorithms?
Let’s answer this with two versions of bubble sort, recursive and iterative —
// bubbleSort.js
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}/// Bubble Sort using for loops
function bubbleSort(array) {
var swapped;
do {
swapped = false;
for(var i = 0; i < array.length; i++) {
if(array[i] > array[i + 1]) {
swap(array, i, i + 1);
swapped = true;
}
}
} while(swapped);
return array;
}// Bubble sort using recursion
var swapped = true
function recursiveSwapping(arr, i = 0) {
var len = arr.length;
if (i >= len) {
return arr
}
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true
}
return recursiveSwapping(arr, i + 1)
}
function recursiveBubbleSort(arr) {
if (!swapped) {
return arr
}
swapped = false
recursiveSwapping(arr, i = 0)
return recursiveBubbleSort(arr)
}
These two examples use the same exact algorithm, but the memory is handled differently. The recursive version of the algorithm uses stack memory, and will therefore break with a stack overflow error if the length of the array is very large. This is because the stack keeps track of every call of recursiveSwappinguntil the original call resolves. The iterative version of the function doesn’t face stack overflow issues.
In theory, the recursive version shouldn’t face memory issues either. Many lower level languages allow something called tail-call optimization, which makes it possible to to write recursive functions with 0(1) memory complexity. Until recently, JS did not allow tail call optimization, but in ECMAScript 6 you can enable it in strict mode. Simply type 'use strict’ at the top of the file, and you will be able to write recursively without running into stack overflow errors.
'use strict'
Just make sure that your recursive function calls are written in the last line, or tail, of your function like in the function below.
function recursiveSwapping(arr, i = 0) {
var len = arr.length;
if (i >= len) {
return arr
}
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true
}
// tail call below
return recursiveSwapping(arr, i + 1)
}
5. Some other edge cases to keep in mind
- Odd/even — numbers and string length
- Negative numbers
- Special characters
- Duplicate elements
- Length of 1
- Long string or large number
- Null or Falsey values
每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文，欢迎关注开源日报。交流QQ群：202790710；微博：https://weibo.com/openingsource；电报群 https://t.me/OpeningSourceOrg
