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

  algorithm, es6, javascript, node.js

Project address:Link description
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 rightfilemap.jsThe paper analyzes the code step by step and introduces its operation principle and optimization strategy in detail.

Preparation of knowledge points:

  1. NodeJSThe basic method of use (mainlyfsFile system);

  2. ES6Features 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 areFirst order,infix orderAndAfter the orderThe three traversal methods used in this example arePreorder traversalThe 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 analyzePreorder traversalThe principle of:
图片描述
The dotted line is the traversal order, as can be seenPreorder traversalWe 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 atraverseNode()Function that takes two objects as arguments.nodeParameter is the passed-in node.deepThe parameter is the starting depth of the node.
First useObject.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. ForBinary 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 putPreorder traversalThe idea of expanding toN-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 isdeep + 1The depth corresponding to each node can be known.

During the traversal of this example,nodeThey are all objects one by one, not strings. If it is detectednodeIt 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.jsBy traversing all sub-files and sub-folders within a folder, its directory structure is output. We usefsFile 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) => {
 let files = fs.readdirSync(path)
 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 treeN-fork treeThrough the previous example, it is not difficult to understand the principle of this code. First passfs.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 oneplaceHolder()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 aCaching Function Execution ResultsThe 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) => {
 let files = fs.readdirSync(path)
 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 directorynode 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.gitOr ..node_modulesHow 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[2] === '-i'){
 for (let i of process.argv.slice(3)) {
 ignoreCase[i] = true
 }
 }

ignoreCaseSave the folder name that needs to be ignored. The reason for using objects instead of arrays is that when judging aitemWhether it has been saved or not,item.indexOf(Array)The efficiency of the is notObject[item]Come high. Usefor...ofLoops 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 files = fs.readdirSync(path)
 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 completefilemap.jsCompleted, 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[2] === '-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 files = fs.readdirSync(path)
 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. Infilemap.jsThere 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!