🎉学算法在业务开发中到底有没有用？

前言

作为一名大学多次打铁的前ACM-ICPC竞赛选手，对这个问题应该算多少有点话语权，首先先说一下结论：有用。抛开面试不谈，算法的收益可能没有学某项技术那么明显，它算是潜移默化的增强你的思维方式，拓展思路，分析业务逻辑的时候可能会更加迅速，处理起复杂业务相对更加得心应手一些。

如果要说在业务开发中使用过哪些算法，那基本可以说是使用不上，使用上的也是一些相对基础的算法，像什么并查集、最小生成树、最短路径、图论等等当时学的时候抓耳挠腮的高级算法基本都用不到。

一些基础的算法还是能够经常遇到的，今天来盘一下业务开发中常见的算法。

桶排序

维基百科上的解释为，桶排序是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间O(n)

可以说是一堆废话了，根本看不懂，翻译成人话就是利用数组下标的有序性，通过空间换时间的思想，只要出现一次数就在数组对应的下标上+1，然后遍历数组中那些大于1即可。

public static void main(String[] args) {
    int[] source = new int[]{8,3,7,12,5,6,9};
    bucketSort(source);
}

public static void bucketSort(int[] array){
    int[] reslut = new int[13];
    for (int i = 0; i < array.length; i++) {
        reslut[array[i]]++;
    }

    for (int i = 0; i < reslut.length; i++) {
        for (int j = 1; j <= reslut[i]; j++) {
            System.out.println(i);
        }
    }
}

这种思想在业务开发中经常会用到，可能不是在排序的场景，由于本身就很简单就不再举例子了。

DFS

Depth First Search深度优先搜索，简称DFS，通常会把数据抽象为一个树形结构，从根节点出发，按预定的顺序扩展到子节点，如果子节点还有子节点则继续递归这个过程，直到当前节点没有子节点。当到达最深的一个叶子结点后处理完当前节点逻辑，则需要返回上一个节点重新寻找一个新的扩展节点。如此搜索下去，直到找到目标节点，或者搜索完所有节点为止。

以这个树为例。假如要找的值为节点2，DFS会首先按一个路线走到不能再走，也就是0 -> 1 -> 3。因为节点3没有子节点了，DFS会回到上一级，也就是节点1的位置，然后按照另一条路走到黑。也就是0 -> 1 -> 3 -> 4。由于4没有子节点，DFS会回到节点1，然后节点1所有的子节点都已经去过了，于是乎再回到节点0，然后去到节点2，最终找到它，路线就是0 -> 1 -> 3 -> 4 -> 2。

我们可以用在一个真实的场景里，就拿文件夹与文件的结构，根据数据库三范式，我们简单定义一下文件夹与文件和文件夹关联关系

// 文件夹
public class Folder {
    private String folderId;
    private String parentId;
}

// 文件
public class File {
    private String fileId;
    private String fileName;
}

// 文件夹关联关系
public class FolderFielRel {
    private String folderId;
    private String fileId;
}
 

这样就定义出一个简单的文件夹结构实体，从结构上来看实现一个树形的逻辑还是很简单的。联表查询即可，用FolderFielRel关联出每个文件夹的文件，然后文件夹通过parentId组成树。

逻辑很清晰，但是如果产品老哥说每一层文件夹需要展示当前文件夹数量。很多同学肯定会脱口而出，让前端拿每一层的文件数量不完了吗。但如果老哥拿出不仅要当前文件夹的数量，还要知道本级文件夹及子级文件夹的文件数量，阁下应该怎么应对呢。

这时候就要DFS出手了，按照DFS的思路，如果要求文件夹本级及子级的文件数量，我们需要从以这个文件夹为根节点的子树的叶子结点开始处理。

我们假设最终VO为FolderTreeModel，并且已经组成了一个完整的树

public class FolderTreeModel {
    private String folderId;
    private String parentId;
    private Integer fileCount;
    private List<File> fileList;
    private List<FolderTreeModel> subFolders;
}

dfs

private void dfsBuildFolderFileCount(Map<String, Integer> statBook,
                        FolderTreeModel rootTreeNode) {

   List<Folder> sonTopicTrees = rootTreeNode.getSubFolders;
   for (FolderTreeModel folderTreeModel : sonTopicTrees) {

      this.dfsBuildFolderFileCount(statBook, folderTreeModel);
   }

   rootTreeNode.setFileCount(statBook.getOrDefault(rootTreeNode.getFolderId(), 0) + rootTreeNode.getFileCount());
   statBook.put(rootTreeNode.getParentId(), statBook.getOrDefault(rootTreeNode.getParentId(), 0) + rootTreeNode.getFileCount());
}

statBook为记录每个文件夹的文件树，通过folder_id映射，当我们dfs到第一个叶子节点，我们把当前节点的文件数累加到当前节点的父级节点的id对应的文件数上。当整个dfs搜索结束之后每个节点的本级及子级的文件数都存在了statBook中。

BFS

bfs虽然好用，但他有个致命的弱点，时间复杂度高，按刚才的文件夹例子需要n*logn的复杂度。在一些性能要求较高的查询场景下基本上都不会用。

既然有深度优先搜索，那当然就得有广度优先搜索，广度优先搜索，顾名思义，跟深度的区别为处理数据以广度往外扩散，通常会借助队列先进先出的数据结构。

以上图为例也就是说，访问数据的过程为，1 -> 2,3 -> 4,5 -> 6。那么我们使用bfs来改写dfs中的统计文件夹树的代码。

private void buildFolderFileCount(Map<String, Integer> statBook,
                        FolderTreeModel rootTreeNode) {

    LinkedBlockingQueue<FolderTreeModel> bfsQueue = new LinkedBlockingQueue<>(rootTreeNode.getSubFolders());

   while (!bfsQueue.isEmpty()) {
       FolderTreeModel firstObj = bfsQueue.poll();
       statBook.put(firstObj.getParentId(), statBook.getOrDefault(firstObj.getParentId(), 0) + firstObj.getFileCount());
       bfsQueue.addAll(firstObj.getSubFolders());
   }
}

一波BFS下来，statBook的结果与DFS的结果一样。效率从n*logn直接飙升到n。除了这三个简单的算法之外实在想不到还有什么算法在日常的业务开发中使用的了。

算法的魅力还是很大的，大就大在学的时候难受的一比，用的时候拍案称奇，有时候在代码里露两手心里的成就感直接彪到Integer.MAX_VALUE。