#### Deep Analysis of FileMap. JS-On JS Algorithm and Optimization Practice

Project description:https://segmentfault.com/a/1190000005968734

About the usage and introduction of the project, you can see the above two links. The main content of this article is right`filemap.js`The paper analyzes the code step by step and introduces its operation principle and optimization strategy in detail.

## Preparation of knowledge points:

1. `NodeJS`The basic method of use (mainly`fs`File system);

2. `ES6`Features and Grammar (`let`,`const`,`for...of`,`arrow function`…）

3. `N-fork Tree Preorder Traversal Algorithm`.

Knowledge points 1 and 2 please consult the data yourself, and now analyze knowledge point 3.

## N-fork Tree Preorder Traversal Algorithm

First understand what is a tree. QuoteJavaScript Description of Data Structure and Algorithm

A tree structure contains a series of nodes with parent-child relationships. Each node has a parent node (except the top first node) and zero or more child nodes: The node at the top of the tree is called the root node (11). It has no parent node. Each element in the tree is called a node. Nodes are divided into internal nodes and external nodes. Nodes with at least one child node are called internal nodes (7, 5, 9, 15, 13, and 20 are internal nodes). Nodes without child elements are called external nodes or leaf nodes (3, 6, 8, 10, 12, 14, 18, and 25 are leaf nodes).
A node can have ancestors and descendants. The ancestors of a node (except the root node) include a parent node, a grandfather node, a great grandfather node, etc. Descendants of a node include child nodes, grandson nodes, great-grandson nodes, etc. For example, the ancestor of node 5 has node 7 and node 11, and the descendant has node 3 and node 6.
Another term for trees is subtree. A subtree consists of nodes and their descendants. For example, nodes 13, 12, and 14 form a subtree of the tree in the above figure.
One attribute of a node is its depth, which depends on the number of its ancestor nodes. For example, node 3 has three ancestor nodes (5, 7, and 11) with a depth of 3.
The height of the tree depends on the maximum depth of all nodes. A tree can also be broken down into levels. The root node is at level 0, its children are at level 1, and so on. The height of the tree in the above figure is 3 (the maximum height is shown in the figure-layer 3).

For the traversal of a tree, there are`First order`,`infix order`And`After the order`The three traversal methods used in this example are`Preorder traversal`The way. As for the similarities and differences of the three traversal methods, please readJavaScript Description of Data Structure and Algorithm, there is a detailed introduction.

First we create a tree:

``````let treeObj = {
'1': [
{ '2': [{ '5': [{ '11': '11' }, { '12': '12' }, { '13': '13' }, { '14': '14' }] }] },
{ '3': [{ '6': '6' }, { '7': '7' }] },
{ '4': [{ '8': '8' }, { '9': '9' }, { '10': '10' }] }
]
}``````

For simplicity and convenience, I set its key and value to the same value. In the example, we all use the key value.
Then analyze`Preorder traversal`The principle of: The dotted line is the traversal order, as can be seen`Preorder traversal`We can get the structure of the whole tree, which is exactly what we need. Next, let’s look at how the code is implemented. First look at the complete code:

``````let traverseNode = (node, deep) => {
if (typeof node !  == 'string') {
let key = Object.keys(node)
console.log(key, deep)
for (let i = 0;   i < node[key].length;  i++) {
traverseNode(node[key][i], deep + 1)
}
}
}

traverseNode(treeObj, 1)``````

We created a`traverseNode()`Function that takes two objects as arguments.`node`Parameter is the passed-in node.`deep`The parameter is the starting depth of the node.
First use`Object.keys(obj)`The method obtains the key value of the node and outputs the depth value at the same time:

``````let key = Object.keys(node)
console.log(key, deep)``````

Run, will be output in the console`[ '1' ] 1`. Next, we use recursion to repeat this process and complete the traversal operation:

``````for (let i = 0;   i < node[key].length;  i++) {
traverseNode(node[key][i], deep + 1)
}``````

This recursion is what we have been saying before.`Preorder traversal`. For`Binary tree`

First-order traversal accesses each node in order of precedence over the descendant nodes. One application of first-order traversal is to print a structured document.
Sequential traversal first accesses the node itself, then its left child node, and finally its right child node. After understanding the above passage, it is not difficult to put`Preorder traversal`The idea of expanding to`N-fork tree`: Access the node itself first and then its N child nodes from left to right.
Each complete for loop means “go down one level,” so all you need is`deep + 1`The depth corresponding to each node can be known.

During the traversal of this example,`node`They are all objects one by one, not strings. If it is detected`node`It is a string, proving that it has reached the last layer and needs to be stopped, otherwise it will cause overflow in infinite loop, so we need to add a judgment:

``if (typeof node !  == 'string')``

We’re done. Now let’s try to run it:

``````[ '1' ] 1
[ '2' ] 2
[ '5' ] 3
[ '11' ] 4
[ '12' ] 4
[ '13' ] 4
[ '14' ] 4
[ '3' ] 2
[ '6' ] 3
[ '7' ] 3
[ '4' ] 2
[ '8' ] 3
[ '9' ] 3
[ '10' ] 3``````

Perfect.

## Js principle

`filemap.js`By traversing all sub-files and sub-folders within a folder, its directory structure is output. We use`fs`File system.

``const fs = require('fs')``

Then to construct the core code:

``````//Determine the type.  Returns true if the path corresponds to a folder, otherwise returns false
let isDic = (url) => fs.statSync(url).isDirectory()

const traverseFiles = (path, deep) => {
for (let i = 0, len = files.length;   i < len;  i++) {
if (files[i] !  = =' filemap.js') console.log (deep, files [i],' \ n')//ignore filemap.js itself
let dirPath = path + '\\' + files[i]
//The next round of traversal will only take place if and only if it is a folder.
if (isDic(dirPath)) traverseFiles(dirPath, deep + 1)
}
}``````

The file directory structure is actually a typical tree`N-fork tree`Through the previous example, it is not difficult to understand the principle of this code. First pass`fs.readdirSync(path)`All files (folders) corresponding to a certain path are synchronously acquired, and then recursion is performed. It can be understood as traversing from the second layer, so it is slightly different in writing from the previous example.

Now that we can get the file and its depth, the next step is to format the information to make its output more intuitive. In order to output similar

``````|__folder
|__file1
|__file2``````

For such a tree structure, we need to judge the indentations corresponding to different depths, so we will define one`placeHolder()`Functions:

``````const placeHolder = (num) => {
if (placeHolder.cache[num]) return placeHolder.cache[num] + '|__'
placeHolder.cache[num] = ''
for (let i = 0;   i < num;  i++) {
placeHolder.cache[num] += '  '
}
return placeHolder.cache[num] + '|__'
}
placeHolder.cache = {}``````

This involves a`Caching Function Execution Results`The optimization strategy of. Since this function is used many times, if you start the for loop from scratch every time, there is a huge waste of performance. Therefore, we can cache its execution results. When we encounter the same situation in the future, we only need to fetch the cached results without recalculation, thus greatly improving the performance.

Now let’s rewrite the core code:

``````let isDic = (url) => fs.statSync(url).isDirectory()

const traverseFiles = (path, deep) => {
for (let i = 0, len = files.length;   i < len;  i++) {
if (files[i] !  = =' filemap.js') console.log (placeholder (deep), files [I],' \ n')//ignore filemap.js itself
let dirPath = path + '\\' + files[i]
if (isDic(dirPath)) traverseFiles(dirPath, deep + 1)
}
}

traverseFiles('./', 1)``````

Run in root directory`node filemap.js`, we can get the perfect file directory tree structure diagram.

## Further expansion of functions

Now all folders are expanded “indiscriminately”. If you want to ignore some folders, such as`.git`Or ..`node_modules`How should folders like this be done? This requirement is not difficult to implement by referring to the command line input method.
First get the folder name to ignore:

``````let ignoreCase = {}
if(process.argv === '-i'){
for (let i of process.argv.slice(3)) {
ignoreCase[i] = true
}
}``````

`ignoreCase`Save the folder name that needs to be ignored. The reason for using objects instead of arrays is that when judging a`item`Whether it has been saved or not,`item.indexOf(Array)`The efficiency of the is not`Object[item]`Come high. Use`for...of`Loops can get objects directly.

Next, we can add one more judgment to the core code:

``````let isDic = (url) => fs.statSync(url).isDirectory()

const traverseFiles = (path, deep) => {
let con = false
for (let i = 0, len = files.length;   i < len;  i++) {
if (files[i] !  == 'filemap.js') console.log(placeHolder(deep), files[i], '\n')
con = ignoreCase[files[i]] === undefined?  true: false
let dirPath = path + '\\' + files[i]
if (isDic(dirPath) && con) traverseFiles(dirPath, deep + 1)
}
}``````

Ignored folders will not be recursively computed.
Finally, don’t forget to quit the process:

``process.exit()``

At this point, the complete`filemap.js`Completed, all codes are as follows:

``````/**
* @author Jrain Lau
* @email  jrainlau@163.com
* @date 2016-07-14
*/

'use strict'
const fs = require('fs')

let ignoreCase = {}
if(process.argv === '-i'){
for (let i of process.argv.slice(3)) {
ignoreCase[i] = true
}
}

console.log('\n\nThe files tree is:\n=================\n\n')

const placeHolder = (num) => {
if (placeHolder.cache[num]) return placeHolder.cache[num] + '|__'
placeHolder.cache[num] = ''
for (let i = 0;   i < num;  i++) {
placeHolder.cache[num] += '  '
}
return placeHolder.cache[num] + '|__'
}
placeHolder.cache = {}

let isDic = (url) => fs.statSync(url).isDirectory()

const traverseFiles = (path, deep) => {
let con = false
for (let i = 0, len = files.length;   i < len;  i++) {
if (files[i] !  == 'filemap.js') console.log(placeHolder(deep), files[i], '\n')
con = ignoreCase[files[i]] === undefined?  true: false
let dirPath = path + '\\' + files[i]
if (isDic(dirPath) && con) traverseFiles(dirPath, deep + 1)
}
}

traverseFiles('./', 1)

process.exit()``````

When in use, only parameters are needed`-i folder 1 folder 2 ...`You can control whether the folder is expanded or not.

## Postscript

StudyingJavaScript Description of Data Structure and AlgorithmIn the process, sometimes I really feel very sleepy, then I play my favorite personality and find ways to put boring things into practice, which will become interesting unconsciously. In`filemap.js`There are many bugs and performance problems in the earlier versions of, such as unreasonable use of ternary expressions, no caching of function execution results, and poor consideration in judging file types. Many of the optimization strategies involved in this article were finally obtained through advice and revision from others. I am very grateful to those who helped me.

Finally, thank you for reading. I am Jrain, welcome to pay attention.My column, will not regularly share their learning experience, development experience, carrying dry goods outside the wall. See you next time!