VLeeDesignTheory

# 数据结构算法在专网项目中的实践

# 前言

数据结构与算法作为计算机学科中至关重要的一门课程，在日常业务代码中常常很难用到或者说很难进行相关的实践，我们常常在leetcode中练习的习题感到没有用武之地。实际上，我们可以通过优化页面中的一些代码及在需求实现过程中对之前阅读过的源码或者之前练习过的习题进行相关的举一反三和触类旁通。本文列举了一些作者在日常业务代码书写过程中进行的一些相关数据结构算法的实践以及对于算法与数据结构练习的思考。

# 业务需求

  • 自定义优先级规则展示
  • 切换时间粒度字段映射

# 探索方案

# 自定义优先级规则展示

在前端页面中，我们经常会遇到需要一排展示数量或者不同维度属性的需求，通常来说我们会将后端所有返回的字段都进行相关的展示，但是在一些轻交互重展示的场景中，比如可视化大屏，就需要我们对展示的内容进行取舍，而这个取舍就需要我们能够根据需求或者说产品数据的反馈进行优先级的选择排布，这里就会涉及到优先级的动态调整过程，也就是能够根据数据或者需求来自定义展示优先级。

# 方案一：函数式编程

图片

第一个比较简单的想法就是根据产品需求进行数组的分流，然后合并数组进行截取展示

fn(arr) {
  let r = [], _r = [];
  for(let i=0; i < arr.length; i++) {
    // 数量展示优化
    if( 达到某个数量 ) return r;
    if(// 根据产品需求对数组进行分流) {
      r.push(arr[i])
    } else {
      _r.push(arr[i])
    }
  }

  return r.length > 5 ? r.slice(0,5) : r.concat(_r).slice(0,5);
};

gn() {
  this.resourceConfig.map(// 业务逻辑).sort((a,b) => a.structure - b.structure));
}

最后 fn(gn())

# 方案二：链表

图片

方案二来源于链表的删除更新方便的特点，通过一个链表将所有的优先级进行串联起来，通过使用update操作进行相关的业务更新操作

// 构造一个节点
class Node {
  constructor(v, next){
    this.value = v;
    this.next = next;
  }
}
 
class LinkList {
  constructor(){
    // 链表的属性，长度和头部
    this.size = 0
    this.head = new Node(null, null)
  }
    
  // 是否为空
  isEmpty() {
    return this.size === 0
  }
  
  // 更新链表，进行相关业务的操作
  update() {

  }
}

# 方案三：优先队列

图片

本方案来源于react的fiber的优先级调度，通过优先队列进行相关的操作

class PriorityQueue{
    // 取父节点索引 ~~((index - 1) / 2)
    constructor(arr){
        if (arr.length){
            this.tree = []
            this._build_tree(arr);
            return;
        }
        this.tree = [];
    }

    // 入队
    enqueue(val){
        this.tree.push(val);
        // 上浮
        this._up(this.tree.length - 1);
    }

    // 出队
    dequeue(){
        // 取树根元素
        this.tree.shift();
        // 最后一个元素放树根，进行下沉
        let last = this.tree.pop();
        this.tree.unshift(last);
        // log(n)下沉
        this._down(0);
    }

    // 取队首的值
    getFirst(){
        return this.tree[0];
    }

    _build_tree(arr){
        let tree = this.tree;
        tree.push(arr[0]);
        for (let i = 1; i < arr.length; i++){
            tree.unshift(arr[i]);
            this._down(0);
        }
    }

    // 对index号元素执行下沉操作. 也叫heapify
    _down(index){
        let tree = this.tree;
        // 本身就是叶子节点，无需下沉
        let last_no_leaf = ~~((tree.length - 2) / 2);
        if (index > last_no_leaf) return;
        while(index <= last_no_leaf){
            let l = tree[index * 2 + 1];
            let r = tree[index * 2 + 2] || tree[index * 2 + 1]; // 有可能没有右儿子
            let max = l >= r ? l : r;
            let maxIndex = l >= r ? index * 2 + 1: index * 2 + 2
            if (tree[index] < max){
                [tree[index], tree[maxIndex]] = [tree[maxIndex], tree[index]]
                index = index * 2 + 1
            }else{
                return;
            }
        }
    }

    // 对index号元素执行上浮操作
    _up(index){
        let tree = this.tree;
        while(index !== 0){
            let p = ~~((index - 1) / 2);
            if (tree[index] > tree[p]){
                [tree[index], tree[p]] = [tree[p], tree[index]];
                // let tmp = index;
                // this._down(tmp);
                index = p;
            } else {
                return;
            }
        }
    }
}

# 切换时间粒度字段映射

在前端页面中，对于动态下拉选择框选项，我们通常通过接口进行获取，但是对于多级联动的下拉选择选项，对于不同的时间粒度选择通常返回的数据名称相同但是id确实不同的，这时通常需要对数据进行映射处理

# 方案：栈

图片

在时间粒度进行切换时，需要记录前后最终前后两个时间粒度的值，通过接口进行时间粒度的数据映射，这里可以通过栈进行时间粒度的记录，获取最初和最后的时间粒度，最后进行数据映射

const timeSizeList = [];

// 进行入栈操作
timeSizeList.push(...)

# 总结

日常进行数据结构习题练习或者阅读源码过程中，除了为了应付面试之外，最重要的还是要学习源码或者习题中解决问题的思路以及想法，在日常的业务代码中，虽然很难写出框架代码那种优雅简洁的实现方案，但是也应该在日常工作中多思考如何利用数据结构与算法来优化代码的时空复杂度，更好的优化代码的执行，从而提升用户体验，这才是一个高级工程师应该关注的细节点，不能只是为了完成业务代码而完成业务代码，这样虽然写了很多代码，但其实其对个人代码能力及计算机素养的提升都是很有限的，事倍却工半，希望在重复的业务代码书写过程中，也能做到优雅与高效并存，共勉！！！

# 参考

← postMessage踩坑实践 →