leuisken.github.io 为什么我认为数据结构与算法对前端开发很重要？

从一个需求谈起

在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：

图中的示例使用的是Ant-Design的Cascader组件。

要实现这一功能，我需要类似这样的数据结构：

var data = [{
  "value": "浙江",
  "children": [{
    "value": "杭州",
    "children": [{
      "value": "西湖"
    }]
  }]
}, {
  "value": "四川",
  "children": [{
    "value": "成都",
    "children": [{
      "value": "锦里"
    }, {
      "value": "方所"
    }]
  }, {
    "value": "阿坝",
    "children": [{
      "value": "九寨沟"
    }]
  }]
}]

一个具有层级结构的数据，实现这个功能非常容易，因为这个结构和组件的结构是一致的，递归遍历就可以了。

但是，由于后端通常采用的是关系型数据库，所以返回的数据通常会是这个样子：

var data = [{
  "province": "浙江",
  "city": "杭州",
  "name": "西湖"
}, {
  "province": "四川",
  "city": "成都",
  "name": "锦里"
}, {
  "province": "四川",
  "city": "成都",
  "name": "方所"
}, {
  "province": "四川",
  "city": "阿坝",
  "name": "九寨沟"
}]

前端这边想要将数据转换一下其实也不难，因为要合并重复项，可以参考数据去重的方法来做，于是我写了这样一个版本。

'use strict'

/**
 * 将一个没有层级的扁平对象,转换为树形结构({value, children})结构的对象
 * @param {array} tableData - 一个由对象构成的数组,里面的对象都是扁平的
 * @param {array} route - 一个由字符串构成的数组,字符串为前一数组中对象的key,最终
 * 输出的对象层级顺序为keys中字符串key的顺序
 * @return {array} 保存具有树形结构的对象
 */

var transObject = function(tableData, keys) {
  let hashTable = {}, res = []
  for( let i = 0; i < tableData.length; i++ ) {
    if(!hashTable[tableData[i][keys[0]]]) {
      let len = res.push({
        value: tableData[i][keys[0]],
        children: []
      })
      // 在这里要保存key对应的数组序号,不然还要涉及到查找
      hashTable[tableData[i][keys[0]]] = { $$pos: len - 1 }
    }
    if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {
      let len = res[hashTable[tableData[i][keys[0]]].$$pos].children.push({
        value: tableData[i][keys[1]],
        children: []
      })
      hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]] = { $$pos: len - 1 }
    }
    res[hashTable[tableData[i][keys[0]]].$$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].$$pos].children.push({
      value: tableData[i][keys[2]]
    })
  }
  return res
}

var data = [{
  "province": "浙江",
  "city": "杭州",
  "name": "西湖"
}, {
  "province": "四川",
  "city": "成都",
  "name": "锦里"
}, {
  "province": "四川",
  "city": "成都",
  "name": "方所"
}, {
  "province": "四川",
  "city": "阿坝",
  "name": "九寨沟"
}]

var keys = ['province', 'city', 'name']

console.log(transObject(data, keys))

还好keys的长度只有3，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。

后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道trie树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下trie树的原理并试着优化一下。

讲道理，trie树这个数据结构网上确实有很多资料，但很少有使用JavaScript实现的，不过原理倒是不难。尝试之后，我就将transObject的代码优化成了这样。（关于trie树，还请读者自己阅读相关材料）

var transObject = function(tableData, keys) {
  let hashTable = {}, res = []
  for (let i = 0; i < tableData.length; i++) {
    let arr = res, cur = hashTable
    for (let j = 0; j < keys.length; j++) {
      let key = keys[j], filed = tableData[i][key]
      if (!cur[filed]) {
        let pusher = {
          value: filed
        }, tmp
        if (j !== (keys.length - 1)) {
          tmp = []
          pusher.children = tmp
        }
        cur[filed] = { $$pos: arr.push(pusher) - 1 }
        cur = cur[filed]
        arr = tmp
      } else {
        cur = cur[filed]
        arr = arr[cur.$$pos].children
      }
    }
  }
  return res
}

这样，解决方案就和keys的长短无关了。

这大概是我第一次，真正将数据结构的知识和前端项目需求结合在一起。

再谈谈我在面试遇到的问题

目前为止我参加过几次前端开发方面的面试，确实有不少面试官会问道一些算法。通常会涉及的，是链表、树、字符串、数组相关的知识。前端面试对算法要求不高，似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分，但是仅凭常见的面试题，而不去联系需求，很难让人觉得，算法对于前端真的很重要。

直到有一天，有一位面试官问我这样一个问题，下面我按照自己的回忆把对话模拟出来，A指面试官，B指我：

A：你有写过瀑布流吗？

B：我写过等宽瀑布流。实现是当用户拉到底部的一定高度的时候，向后端请求一定数量的图片，然后再插入到页面中。

A：那我问一下，如何让几列图片之间的高度差最小？

B：这个需要后端发来的数据里面有图片的高度，然后我就可以看当前高度最小的是哪里列，将新图片插入那一列，然后再看看新的高度最小的是哪一列。

A：我觉得你没有理解我的问题，我的意思是如何给后端发来的图片排序，让几列图片之间的高度差最小？

B：（想了一段时间）对不起，这个问题我没有思路。

A：你是软件工程专业的对吧？你们数据结构课有没有学动态规划？

B：可能有讲吧，但是我没什么印象了。

对话大概就是这样，虽然面试最终还是pass了，但这个问题确实让我很在意，因为我觉得，高度差“最”小，真的能用很简单的算法就解决吗？

这个问题的实质，其实就是有一个数组，将数组元素分成n份，每份所有元素求和，如何使每份的和的差最小。

搜索上面这个问题，很快就能找到相关的解答，很基本的一类动态规划问题——背包问题。

之前我确实看过背包问题的相关概念（也仅仅是相关概念）。当时我看到这样一段话：

许多使用递归去解决的编程问题，可以重写为使用动态规划的技巧去解决。动态规划方案通常会使用一个数组来建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解将会在这个表中很明显的地方被找到。

后面是一个用动态规划重写斐波那契数列的例子。我看到它只是将递归的结果，保存在了一个数组中，就天真的以为动态规划是优化递归的一种方法，并没有深入去理解。

不求甚解，确实早晚会出问题的。当时我虽然以为自己知道了算法的重要性，但其实还是太年轻。

动态规划可以求解一类“最优解”问题，这在某种程度上让我耳目一新。由于本文主要还是为了说明数据结构与算法对于前端的意义，关于动态规划的细节，本文也不会涉及，而且水平确实也不够。网上有许多非常好的博文，尤其推荐《背包九讲》。

多说两句——一道思考题

将如下扁平对象，转为树形对象。parent字段为空字符串的节点为根节点：

var input = {
  h3: {
    parent: 'h2',
    name: '副总经理(市场)'
  },
  h1: {
    parent: 'h0',
    name: '公司机构'
  },
  h7: {
    parent: 'h6',
    name: '副总经理(总务)'
  },
  h4: {
    parent: 'h3',
    name: '销售经理'
  },
  h2: {
    parent: 'h1',
    name: '总经理'
  },
  h8: {
    parent: 'h0',
    name: '财务总监'
  },
  h6: {
    parent: 'h4',
    name: '仓管总监'
  },
  h5: {
    parent: 'h4',
    name: '销售代表'
  },
  h0: {
    parent: '',
    name: 'root'
  }
};

这个需求在前端其实也很实际，示例中的对象是一个公司组织结构图。如果需求是让你在前端用svg之类的技术画出这样一张图，就需要这个功能。（另外我想到的一种应用场景，就是在前端展示类似windows资源管理器的文件树）

我当时想了很久，没有想到一个循环解决的方法，后来在stackoverflow上找到了答案：

var plain2Tree = function (obj) {
  var key, res
  for(key in obj) {
    var parent = obj[key].parent
    if(parent === '') {
      res = obj[key]
    } else {
      obj[parent][key] = obj[key]
    }
  }
  return res
}

这段代码，就是利用了JavaScript里面的引用类型，之后的思路，和操作指针没什么区别，就是构造一棵树。

但对于我来说，从来都没有往树和指针的那方面思考，就很被动了。

结语

以上列举了三道题，希望可以引起大家对于在前端应用数据结构与算法相关知识的共鸣。

May 13 '16 10:05 LeuisKen

还能更加极致地让服务端通过 SQL 来实现了，这样传输给前端的数据量也大大减少了。

SQL 无法实现的话，建议这个trie树由服务端来实现数据的转换。

Jun 17 '16 12:06 fengmk2

@fengmk2 如果只是这一个地方使用这一接口的话，传来的数据确实过多了。其实除了这个选择外，还有一个完整列表的展示需求，也就是说，完整的数据肯定是要发送过来的。这种情况下，转换的逻辑放在前端应该还是更合理一点，毕竟后端可以少一个接口。

Jun 18 '16 10:06 LeuisKen

对于整个页面来说，最好只请求服务端一次就将这个页面需要的数据都一次性返回了。

Sent from my iPhone

On Jun 18, 2016, at 6:10 PM, 魏嘉汛 [email protected] wrote:

@fengmk2 如果只是这一个地方使用这一接口的话，传来的数据确实过多了。其实除了这个选择外，还有一个完整列表的展示需求，也就是说，完整的数据肯定是要发送过来的。这种情况下，转换的逻辑放在前端应该还是更合理一点，毕竟后端可以少一个接口。

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

Jun 19 '16 01:06 fengmk2

非常赞同你的看法，目前做的项目处处都是数据结构和算法，而且还有设计模式。

Mar 19 '17 05:03 majunbao

前端确实得学习一点儿算法的知识。

Jun 22 '17 03:06 yhhwpp

非常赞同！不把数据结构和算法当基础的，都是耍流氓

Jun 22 '17 04:06 jinyang1994

listToTree 的，可以用递归组合的方式来处理。

var data = [
  {
    province: "浙江",
    city: "杭州",
    name: "西湖",
    area: 'A区'
  },
  {
    province: "四川",
    city: "成都",
    name: "锦里",
    area: 'D区'
  },
  {
    province: "四川",
    city: "成都",
    name: "方所",
    area: 'B区'
  },
  {
    province: "四川",
    city: "阿坝",
    name: "九寨沟",
    area: 'C区'
  }
];

// 将一个扁平对象，根据 keys 树形化
function toTree(obj, [key, ...rest], result = {}) {
    if (result.value == null) {
        result.value = obj[key]
        if (rest.length) {
            result.children = toTreeList(obj, rest)
        }
    } else if (result.value === obj[key] && rest.length) {
        toTreeList(obj, rest, result.children)
    }
    return result
}

// 将一个扁平对象的树形化产物，不重复地放到 list 里
function toTreeList(obj, keys, list = []) {
    let value = obj[keys[0]]
    let target = list.find(item => item.value === value)
    if (target) {
        toTree(obj, keys, target)
    } else {
        list.push(toTree(obj, keys))
    }
    return list
}

// 将一个扁平化对象组成的列表，变成树形化的列表
function listToTree(list=[], keys=[]) {
    return list.reduce(
        (result, obj) => toTreeList(obj, keys, result),
        []
    )
}

console.log('result', listToTree(data, ['province', 'city', 'name', 'area']))

这个做法，更加语义化，也可以得到多个可复用的工具函数。

解决这类问题，也有一个统一的思路：先解决能解决的子问题和简单问题，在此基础上再审视，根据现有工具，还可以进一步的解决哪些问题，直到所有问题被解决。这个做法，一来可以不必等某个数据结构和算法被发明，二来甚至可以在这个过程中发明新的数据结构和算法。

---- 2017/09/08 早上更新

为了体现上述方法论的普适性。用吃早饭的功夫，用相同的递归组合思路写了一个 treeToList 的逆运算。把一个树形结构，变成扁平化列表。当树形结构不仅仅是省市区这类选择题，而是可编辑的文件目录时，互相转换就很有用。

var data = [
  {
    value: "浙江",
    children: [
      { value: "杭州", children: [{ value: "西湖", children: [{ value: "A区" }] }] }
    ]
  },
  {
    value: "四川",
    children: [
      {
        value: "成都",
        children: [
          { value: "锦里", children: [{ value: "D区" }] },
          { value: "方所", children: [{ value: "B区" }] }
        ]
      },
      { value: "阿坝", children: [{ value: "九寨沟", children: [{ value: "C区" }] }] }
    ]
  }
];

// 把一个树形结构，变成扁平化列表
function toFlat(tree, [key, ...rest], result = {}) {
  if (result[key] == null) {
    result[key] = tree.value;
  } else if (result[key] !== tree.value) {
    result = {
      ...result,
      [key]: tree.value
    };
  }
  return rest.length ? toFlatList(tree.children, rest, result) : [result];
}

// 把一个树形结构的列表，变成扁平化列表
function toFlatList(treeList, keys, result = {}) {
  return treeList.reduce(
    (list, tree) => list.concat(toFlat(tree, keys, result)),
    []
  );
}

// 转换树形结构为列表结构
function treeToList(treeList = [], keys) {
  return toFlatList(treeList, keys);
}

var result = treeToList(data, ["province", "city", "name", "area"]);
console.log("result", result);

Sep 07 '17 00:09 Lucifier129

瀑布流的思路跟楼主的思路一样，的确没有想更多，看来还是要加强算法的学习

Sep 07 '17 00:09 huigeek

算法对于前端开发重要程度应该是很低的，因为通常情况下用不到~

前端通过ajax向后端获取数据，通常这个数据量非常小，为什么？因为考虑到网络开销和浏览器性能。数据量太大会导致前端页面加载速度慢，影响用户体验。

如果数据量大怎么办？分块加载，比如表单的分页。

算法更多地是用在对大量数据进行操作的时候，几十条数据你用排序算法和sort根本无差别。

在楼主这个例子中，如果后端把全国的地市数据都丢给你，你还能开开心心地在前端用算法去整理成树形解构吗？

如果喜欢算法，建议从事后端开发~

Sep 07 '17 00:09 yalishizhude

很有收获，谢谢博主

Oct 29 '17 01:10 RayJune

很好奇那个瀑布流的动规式子是什么？想了半天想不出来，感觉把什么作为状态都不满足最优子结构……（如果只分两列的话倒是有动规解法，多列就不知道了。）觉得如果是日常应用的话，一个简单的贪心就足够了。

Update 1：

刚搜了一下，如果是大于两列的话，似乎是个 NP 问题……如果只有两列，那就只是一个装箱问题。

Oct 29 '17 10:10 RexSkz

这么解决？大佬看一下

const R = require('ramda');

const data = [{
    province: '浙江',
    city: '杭州',
    name: '西湖'
}, {
    province: '四川',
    city: '成都',
    name: '锦里'
}, {
    province: '四川',
    city: '成都',
    name: '方所'
}, {
    province: '四川',
    city: '阿坝',
    name: '九寨沟'
}];
const keys = ['province', 'city', 'name'];

/**
 * 将对象数组转换为字典数组
 * @param {Array} arr
 * @return {Array}
 */
const transObjToDict = function (arr, keys) {
    return arr.map(item => R.compose(R.join('|'), R.props(keys))(item));
};

function Trie() {
    this.trie = {};
}
Trie.prototype.add = function(str) {
    let trie = this.trie;
    R.compose(
        R.map(function (item, i) {
            if (trie[item] == null) {
                trie[item] = {};
                trie = trie[item];
            }
            else {
                trie = trie[item];
            }
        })
        , R.split('|')
    )(str);
}

function formatTree(trie) {
    const keys = Object.keys(trie);
    let res = [];
    for (let i = 0, len = keys.length; i < len; i++) {
        let temp = {
            value: keys[i],
            children: formatTree(trie[keys[i]])
        }
        if (temp.children.length === 0) {
            delete temp.children;
        }
        res.push(temp);
        
    }
    return res;
}

const newTrans = function (data, keys) {
    const dicts = transObjToDict(data, keys);
    let tree = new Trie();
    for (let i = 0, len = dicts.length; i < len; i++) {
        tree.add(dicts[i]);
    }
    return formatTree(tree.trie);
};

const result = newTrans(data, keys);
console.log(JSON.stringify(res));

Mar 08 '18 07:03 zhanfang

了解了应用场景之后，更能有方向和动力学习算法了，给楼主点个赞

Apr 21 '18 02:04 jessiezhudev

想请假一下,这个转换放在后端转换好呢还是在前端转换?

May 09 '18 03:05 reuwi

@gaoshijun1993 个人感觉其实放在后端比较好

May 09 '18 04:05 LeuisKen

极度不理解作者$$pos是什么意思，为什么要这么命名？

Jan 02 '19 03:01 edgexie

极度不理解作者$$pos是什么意思，为什么要这么命名？

只是单纯的希望起个绝对不会冲突的名字，思考这个没啥意义啦~

Jan 02 '19 04:01 LeuisKen

前辈你好，我试着去实现这个“最小差”瀑布流，没有用到dp。 https://github.com/iJinxin/funnyCoding/blob/master/src/components/waterfall/AequilateWaterfall.vue https://github.com/iJinxin/funnyCoding/blob/master/src/service/Waterfall.js 问题是我无法在理论上证明这种思路是否正确的，你要是有空希望能指点一下，thanks。

Jan 04 '19 02:01 iJinxin

前辈你好，我试着去实现这个“最小差”瀑布流，没有用到dp。 https://github.com/iJinxin/funnyCoding/blob/master/src/components/waterfall/AequilateWaterfall.vue https://github.com/iJinxin/funnyCoding/blob/master/src/service/Waterfall.js 问题是我无法在理论上证明这种思路是否正确的，你要是有空希望能指点一下，thanks。

如下图所示，这个瀑布流有两列，如果之前已经有了一些图片（两列高度分别为 10 和 20），然后新请求到了三个高度分别为 30、18、15 的图片，就会出问题：

Jan 04 '19 04:01 RexSkz

前辈你好，我试着去实现这个“最小差”瀑布流，没有用到dp。 https://github.com/iJinxin/funnyCoding/blob/master/src/components/waterfall/AequilateWaterfall.vue https://github.com/iJinxin/funnyCoding/blob/master/src/service/Waterfall.js 问题是我无法在理论上证明这种思路是否正确的，你要是有空希望能指点一下，thanks。

如下图所示，这个瀑布流有两列，如果之前已经有了一些图片（两列高度分别为 10 和 20），然后新请求到了三个高度分别为 30、18、15 的图片，就会出问题：

一直想着是初始化的时候如何做到高度差最小，如果要一直保持下去，就没思路了。

Jan 04 '19 07:01 iJinxin

@iJinxin 我刚刚又想到，把一开始的 10 和 20 各自加上 100 后分别当作一张图片，就成了初始化的情况：

当获取的图片高度分别是 120、110、30、18、15 时，你的算法无法保证高度差最小。

Jan 04 '19 07:01 RexSkz

@RexSkz 谢谢指正

Jan 04 '19 08:01 iJinxin

很有收获，谢谢博主

Jan 09 '19 03:01 ShinyRaine

@RexSkz 确实是np-hard问题，不是dp能解决的 https://en.wikipedia.org/wiki/Partition_problem 没想到误打误撞用到了 Approximation algorithm approaches - The greedy algorithm。 anyway，谢谢博主分享。

Jan 09 '19 06:01 iJinxin

@RexSkz 确实是np-hard问题，不是dp能解决的 https://en.wikipedia.org/wiki/Partition_problem 没想到误打误撞用到了 Approximation algorithm approaches - The greedy algorithm。 by the way，谢谢博主分享。

233，其实博主现在算法也还是很菜的。本文下面评论的价值现在已经远远超过文章本身了。

Jan 09 '19 06:01 LeuisKen

也要考虑业务本身，这种瀑布流的实现，尤其是移动端一般就两列，可能不需要DP甚至更高深的算法，因为求出最小高度差对业务不一定有最高价值，这些数据是有原始顺序的！

例如是一个店铺排行榜，或是热门推文的瀑布流，其本身顺序的价值也很重要，如果为了求出最小高度差，而打乱了整体的顺序，就跑偏啦。

因此可以退到最简单的思路，准备n个数组，遍历所有数据，计算n个数组的内容高度总和，哪个小，push到哪个数组… 既可以保证整体的顺序不被打乱太多，也可以保证所有列的高度差不会太极端。

Apr 10 '19 07:04 pujiaxun

大佬第一个一维变多维中 $$pos: len - 1 是什么意思？可以解答下吗？...

May 08 '19 15:05 wymloveyou

大佬第一个一维变多维中 $$pos: len - 1 是什么意思？可以解答下吗？...

$$pos就是他随便定义的一个key，你叫他abc也没关系

Jul 03 '19 08:07 jonyjayang

@gaoshijun1993 个人感觉其实放在后端比较好

理想的情况是有一个后端组专门做数据的聚合和清洗，给前端干净的数据，然而通常这个没法由前端决定，取决于前端领导的做事风格以及前端组在公司的地位，有时候不可避免的需要前端来处理这些事情。前端最好做一个适配层专门做这种处理，逻辑集中便于查找，也便于迁移到node或者java后端

Jul 23 '19 03:07 STLighter

请问一下优化后的代码中，res是如何被赋值? 十分不理解let arr =res ；res能够被改变 @LeuisKen

Jan 17 '20 06:01 Donwy

@RexSkz 确实是np-hard问题，不是dp能解决的 https://en.wikipedia.org/wiki/Partition_problem 没想到误打误撞用到了 Approximation algorithm approaches - The greedy algorithm。 anyway，谢谢博主分享。

时隔开帖这么多年，我也终于在一个偶然课程上面看到了这个问题的一种表现，负载平衡问题，并且理解了这个问题确实是 NP 问题，存在贪心的近似算法。也不知道面试官当时是想考啥，也许是漏掉了仅有两列这个条件？我发现手淘上是存在着两列的瀑布流的。

Jul 15 '20 02:07 LeuisKen

时隔开帖这么多年，我也终于在一个偶然课程上面看到了这个问题的一种表现，负载平衡问题，并且理解了这个问题确实是 NP 问题，存在贪心的近似算法。也不知道面试官当时是想考啥，也许是漏掉了仅有两列这个条件？我发现手淘上是存在着两列的瀑布流的。

如果只有两列、每个元素的高度不高（可以先将所有元素高度除以 10 再上取整作为算法的输入），且只需要保证“高度差最小”而没有其它限制条件，那么多项式时间的动态规划确实可以完美解决。

如果是多列，或者需要使用元素的精确高度（总高度很可能超过一万 px），或者需要严格保证“新加载的元素一定要放在页面最下方，而不能插到现有元素的某个位置”（这在商品页面其实是个强制要求），此时就是一个 NP 问题。

Jul 15 '20 02:07 RexSkz

@LeuisKen 博主你好，看到你在VScode的中提的一个关于skiplist跳表的bug，想了蛮久也不明白那里为啥要使用跳表呢？自己的理解那里使用set的数据结构也是能满足。希望博主能够解答一下.😋

Jul 26 '21 15:07 bigHippoZz

@LeuisKen 博主你好，看到你在VScode的中提的一个关于skiplist跳表的bug，想了蛮久也不明白那里为啥要使用跳表呢？自己的理解那里使用set的数据结构也是能满足。希望博主能够解答一下.😋

https://github.com/microsoft/vscode/issues/93368#issuecomment-638903850

看第三条。

Jul 29 '21 08:07 LeuisKen

@LeuisKen 博主你好，看到你在VScode的中提的一个关于skiplist跳表的bug，想了蛮久也不明白那里为啥要使用跳表呢？自己的理解那里使用set的数据结构也是能满足。希望博主能够解答一下.😋

microsoft/vscode#93368 (comment)

看第三条。

谢谢

Aug 01 '21 14:08 bigHippoZz

leuisken.github.io leuisken.github.io copied to clipboard

为什么我认为数据结构与算法对前端开发很重要？

从一个需求谈起

再谈谈我在面试遇到的问题

多说两句——一道思考题

结语

leuisken.github.io
leuisken.github.io copied to clipboard