每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,欢迎关注开源日报。交流QQ群:202790710;微博:https://weibo.com/openingsource;电报群 https://t.me/OpeningSourceOrg

2018年8月29日:开源日报第174期

今日推荐开源项目:《JS 验证库 v8n》传送门:GitHub链接

推荐理由:这是一个可以用来做各种各样细的验证的库,它里面的语法看起来和普通的语法很像所以很容易就能理解,而且它的确提供了各种各样方面的验证方式,从检查所有的字母是不是都是小写到字符串的开头结尾,有兴趣的朋友可以尝试一下。

2018年8月29日:开源日报第174期

今日推荐英文原文:《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:

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:

This will do some very strange things inside the for loop, but ultimately, our algorithm will return the original object.

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:

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:

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:

For algorithms that accept different data structures and types, we should also look out for emptiness. Here are some common ones:

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:

If we want the algorithm to sort strings independent of capitalization, we may want to handle that:

Another case you may want to handle are string numbers vs normal numerical values. Here is one strange example of this:

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.

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 .

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:

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 —

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.

Just make sure that your recursive function calls are written in the last line, or tail, of your function like in the function below.

5. Some other edge cases to keep in mind

  1. Odd/even — numbers and string length
  2. Negative numbers
  3. Special characters
  4. Duplicate elements
  5. Length of 1
  6. Long string or large number
  7. Null or Falsey values

每天推荐一个 GitHub 优质开源项目和一篇精选英文科技或编程文章原文,欢迎关注开源日报。交流QQ群:202790710;微博:https://weibo.com/openingsource;电报群 https://t.me/OpeningSourceOrg