为什么我认为数据结构与算法对前端开发很重要？ #2
Comments
|
还能更加极致地让服务端通过 SQL 来实现了，这样传输给前端的数据量也大大减少了。 SQL 无法实现的话，建议这个trie树由服务端来实现数据的转换。 |
|
@fengmk2 如果只是这一个地方使用这一接口的话，传来的数据确实过多了。其实除了这个选择外，还有一个完整列表的展示需求，也就是说，完整的数据肯定是要发送过来的。这种情况下，转换的逻辑放在前端应该还是更合理一点，毕竟后端可以少一个接口。 |
|
对于整个页面来说，最好只请求服务端一次就将这个页面需要的数据都一次性返回了。 Sent from my iPhone
|
|
非常赞同你的看法，目前做的项目处处都是数据结构和算法，而且还有设计模式。 |
|
前端确实得学习一点儿算法的知识。 |
|
非常赞同！不把数据结构和算法当基础的，都是耍流氓 |
|
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 早上更新 为了体现上述方法论的普适性。用吃早饭的功夫，用相同的 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); |
|
瀑布流的思路跟楼主的思路一样，的确没有想更多，看来还是要加强算法的学习 |
|
算法对于前端开发重要程度应该是很低的，因为通常情况下用不到~ 前端通过ajax向后端获取数据，通常这个数据量非常小，为什么？因为考虑到网络开销和浏览器性能。数据量太大会导致前端页面加载速度慢，影响用户体验。 如果数据量大怎么办？分块加载，比如表单的分页。 算法更多地是用在对大量数据进行操作的时候，几十条数据你用排序算法和sort根本无差别。 在楼主这个例子中，如果后端把全国的地市数据都丢给你，你还能开开心心地在前端用算法去整理成树形解构吗？ 如果喜欢算法，建议从事后端开发~ |
|
很有收获，谢谢博主 |
|
很好奇那个瀑布流的动规式子是什么？想了半天想不出来，感觉把什么作为状态都不满足最优子结构……（如果只分两列的话倒是有动规解法，多列就不知道了。）觉得如果是日常应用的话，一个简单的贪心就足够了。 Update 1： 刚搜了一下，如果是大于两列的话，似乎是个 NP 问题……如果只有两列，那就只是一个装箱问题。 |
|
这么解决？大佬看一下 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)); |
|
了解了应用场景之后，更能有方向和动力学习算法了，给楼主点个赞 |
|
想请假一下,这个转换放在后端转换好呢还是在前端转换? |
|
@gaoshijun1993 个人感觉其实放在后端比较好 |
|
极度不理解作者 |
只是单纯的希望起个绝对不会冲突的名字，思考这个没啥意义啦~ |
|
前辈你好，我试着去实现这个“最小差”瀑布流，没有用到dp。 |
如下图所示，这个瀑布流有两列，如果之前已经有了一些图片（两列高度分别为 10 和 20），然后新请求到了三个高度分别为 30、18、15 的图片，就会出问题：
|
一直想着是初始化的时候如何做到高度差最小，如果要一直保持下去，就没思路了。 |
|
@iJinxin 我刚刚又想到，把一开始的 10 和 20 各自加上 100 后分别当作一张图片，就成了初始化的情况： 当获取的图片高度分别是 120、110、30、18、15 时，你的算法无法保证高度差最小。 |
|
@RexSkz 谢谢指正 |
|
很有收获，谢谢博主 |
|
@RexSkz 确实是np-hard问题，不是dp能解决的 |
233，其实博主现在算法也还是很菜的。本文下面评论的价值现在已经远远超过文章本身了。 |
|
也要考虑业务本身，这种瀑布流的实现，尤其是移动端一般就两列，可能不需要DP甚至更高深的算法，因为求出最小高度差对业务不一定有最高价值，这些数据是有原始顺序的！ 例如是一个店铺排行榜，或是热门推文的瀑布流，其本身顺序的价值也很重要，如果为了求出最小高度差，而打乱了整体的顺序，就跑偏啦。 因此可以退到最简单的思路，准备n个数组，遍历所有数据，计算n个数组的内容高度总和，哪个小，push到哪个数组… 既可以保证整体的顺序不被打乱太多，也可以保证所有列的高度差不会太极端。 |
|
大佬 第一个一维变多维 中 $$pos: len - 1 是什么意思？ 可以解答下吗？... |
$$pos就是他随便定义的一个key，你叫他abc也没关系 |
理想的情况是有一个后端组专门做数据的聚合和清洗，给前端干净的数据，然而通常这个没法由前端决定，取决于前端领导的做事风格以及前端组在公司的地位，有时候不可避免的需要前端来处理这些事情。前端最好做一个适配层专门做这种处理，逻辑集中便于查找，也便于迁移到node或者java后端 |
|
请问一下优化后的代码中，res是如何被赋值? 十分不理解let arr =res ；res能够被改变 |
时隔开帖这么多年，我也终于在一个偶然课程上面看到了这个问题的一种表现，负载平衡问题，并且理解了这个问题确实是 NP 问题，存在贪心的近似算法。也不知道面试官当时是想考啥，也许是漏掉了仅有两列这个条件？我发现手淘上是存在着两列的瀑布流的。 |
如果只有两列、每个元素的高度不高（可以先将所有元素高度除以 10 再上取整作为算法的输入），且只需要保证“高度差最小”而没有其它限制条件，那么多项式时间的动态规划确实可以完美解决。 如果是多列，或者需要使用元素的精确高度（总高度很可能超过一万 px），或者需要严格保证“新加载的元素一定要放在页面最下方，而不能插到现有元素的某个位置”（这在商品页面其实是个强制要求），此时就是一个 NP 问题。 |
|
@LeuisKen 博主你好，看到你在VScode的中提的一个关于skiplist跳表的bug，想了蛮久也不明白那里为啥要使用跳表呢？自己的理解那里使用set的数据结构也是能满足。 希望博主能够解答一下.😋 |
microsoft/vscode#93368 (comment) 看第三条。 |
谢谢 |
and others
从一个需求谈起
在我之前的项目中，曾经遇到过这样一个需求，编写一个级联选择器，大概是这样：
图中的示例使用的是Ant-Design的Cascader组件。
要实现这一功能，我需要类似这样的数据结构：
一个具有层级结构的数据，实现这个功能非常容易，因为这个结构和组件的结构是一致的，递归遍历就可以了。
但是，由于后端通常采用的是关系型数据库，所以返回的数据通常会是这个样子：
前端这边想要将数据转换一下其实也不难，因为要合并重复项，可以参考数据去重的方法来做，于是我写了这样一个版本。
还好keys的长度只有3，这种东西长了根本没办法写，很明显可以看出来这里面有重复的部分，可以通过循环搞定，但是想了很久都没有思路，就搁置了。
后来，有一天晚饭后不是很忙，就跟旁边做数据的同事聊了一下这个需求，请教一下该怎么用循环来处理。他看了一下，就问我：“你知道trie树吗？”。我头一次听到这个概念，他简单的给我讲了一下，然后说感觉处理的问题有些类似，让我可以研究一下trie树的原理并试着优化一下。
讲道理，trie树这个数据结构网上确实有很多资料，但很少有使用JavaScript实现的，不过原理倒是不难。尝试之后，我就将
transObject的代码优化成了这样。（关于trie树，还请读者自己阅读相关材料）这样，解决方案就和keys的长短无关了。
这大概是我第一次，真正将数据结构的知识和前端项目需求结合在一起。
再谈谈我在面试遇到的问题
目前为止我参加过几次前端开发方面的面试，确实有不少面试官会问道一些算法。通常会涉及的，是链表、树、字符串、数组相关的知识。前端面试对算法要求不高，似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分，但是仅凭常见的面试题，而不去联系需求，很难让人觉得，算法对于前端真的很重要。
直到有一天，有一位面试官问我这样一个问题，下面我按照自己的回忆把对话模拟出来，A指面试官，B指我：
A：你有写过瀑布流吗？
B：我写过等宽瀑布流。实现是当用户拉到底部的一定高度的时候，向后端请求一定数量的图片，然后再插入到页面中。
A：那我问一下，如何让几列图片之间的高度差最小？
B：这个需要后端发来的数据里面有图片的高度，然后我就可以看当前高度最小的是哪里列，将新图片插入那一列，然后再看看新的高度最小的是哪一列。
A：我觉得你没有理解我的问题，我的意思是如何给后端发来的图片排序，让几列图片之间的高度差最小？
B：（想了一段时间）对不起，这个问题我没有思路。
A：你是软件工程专业的对吧？你们数据结构课有没有学动态规划？
B：可能有讲吧，但是我没什么印象了。
对话大概就是这样，虽然面试最终还是pass了，但这个问题确实让我很在意，因为我觉得，高度差“最”小，真的能用很简单的算法就解决吗？
这个问题的实质，其实就是有一个数组，将数组元素分成n份，每份所有元素求和，如何使每份的和的差最小。
搜索上面这个问题，很快就能找到相关的解答，很基本的一类动态规划问题——背包问题。
之前我确实看过背包问题的相关概念（也仅仅是相关概念）。当时我看到这样一段话：
后面是一个用动态规划重写斐波那契数列的例子。我看到它只是将递归的结果，保存在了一个数组中，就天真的以为动态规划是优化递归的一种方法，并没有深入去理解。
不求甚解，确实早晚会出问题的。当时我虽然以为自己知道了算法的重要性，但其实还是太年轻。
动态规划可以求解一类“最优解”问题，这在某种程度上让我耳目一新。由于本文主要还是为了说明数据结构与算法对于前端的意义，关于动态规划的细节，本文也不会涉及，而且水平确实也不够。网上有许多非常好的博文，尤其推荐《背包九讲》。
多说两句——一道思考题
将如下扁平对象，转为树形对象。
parent字段为空字符串的节点为根节点：这个需求在前端其实也很实际，示例中的对象是一个公司组织结构图。如果需求是让你在前端用svg之类的技术画出这样一张图，就需要这个功能。（另外我想到的一种应用场景，就是在前端展示类似windows资源管理器的文件树）
我当时想了很久，没有想到一个循环解决的方法，后来在stackoverflow上找到了答案：
这段代码，就是利用了JavaScript里面的引用类型，之后的思路，和操作指针没什么区别，就是构造一棵树。
但对于我来说，从来都没有往树和指针的那方面思考，就很被动了。
结语
以上列举了三道题，希望可以引起大家对于在前端应用数据结构与算法相关知识的共鸣。
The text was updated successfully, but these errors were encountered: