震惊！我竟然在伙伴匹配系统....

（手动狗头）抱歉鱼友们，因为这是本人第一次发学习帖子，所以只能以这种方式博眼球了。

其实这个帖子，是分享一下我对 伙伴匹配系统中的编辑距离算法使用上的一个优化。

为什么想写这篇文章？

其实是在上次面试时被面试官问到这个编辑距离算法了。

我说通过定时任务，计算所有人的匹配用户(所以需要双层循环，每一个都要计算)。

面试官：你在这个项目中用了编辑距离算法，你说说怎么实现的。

我：(随便说了一通)......总之就是涉及了双层循环遍历。

面试官：那你有没有想过，这样写的话时间复杂度就太高了，你该怎么优化。

我：嗯.....不太会(我真的比较菜，想不出优化方法，当时我已经蒙圈了)

面试官：如果让你多线程，你该怎么优化。

我：额......就是......可以实现Callable接口，额....然后实现它的call方法，外层循环获取列表，然后多线程执行编辑距离算法（实际上应该是使用线程池比较好一点）

虽然最后面试通过了，但这个问题确实是我不太会的点，多线程我也不是很熟练，借此机会学习一下。

（以下所有业务场景，都是获取每一个用户的最匹配的用户，所以要进行双层循环，每个列表都要在内部循环计算一次）

原版编辑距离算法

原本的编辑距离算法是比较两个字符串的距离，在循环中判断字符是否相等。

但是稍微修改，就可以用于计算两个字符串列表的距离，在循环中直接判断字符串是否相等。但是这样有一个弊端，字符串列表内容的顺序不同，得出的结果有可能不同(比如**["张三","李四"]与["李四","张三"]，这两个顺序不同但内容相同**的列表在匹配同一个列表时得到的答案可能不一样)

▼
java
复制代码
 public static int minDistance(List<String> tagList1, List<String> tagList2){
        int n = tagList1.size();
        int m = tagList2.size();

        if(n * m == 0)
            return n + m;

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++){
            d[i][0] = i;
        }

        for (int j = 0; j < m + 1; j++){
            d[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (!Objects.equals(tagList1.get(i - 1), tagList2.get(j - 1)))
                    left_down += 1;
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }

通过多线程优化后

创建线程池并分配线程数，不推荐给太多，因为cpu真的会起飞的。

总体思路：将数据分批次处理，每个线程处理一部分数据，提高cpu利用率，减少计算时间。当然，最后的编辑距离算法还是单线程执行的，这里的优化只是把原来所有数据交给一个线程，变为了把所有数据交给多个线程处理

▼
java
复制代码
 public static List<Integer> getCloseDistance(List<List<String>> list) throws ExecutionException, InterruptedException {
        int size = list.size();
     
//        存放结果
        List<Integer> result = new ArrayList<>(Collections.nCopies(size, Integer.MAX_VALUE));
//        获取当前线程数
        int cors = Runtime.getRuntime().availableProcessors();

//        创建线程池（如果这里设置线程数为最大的话，运行起来cpu会直接起飞，物理意义上的起飞）
        ExecutorService executorService= Executors.newFixedThreadPool(cors-5);
        List<Future<?>> futureList=new ArrayList<>();
     
//        设置块大小
        int batch=100;
     
//        创建任务
        for(int start=0;start<size;start+=batch){
            final int shunkStart=start;
            final int shunkEnd=Math.min(start+batch,size);
         //	每个线程执行100条数据，当然，每次都需要遍历所有元素
            futureList.add(executorService.submit(()->{
                for(int i=shunkStart;i<shunkEnd;i++){
                    int min=Integer.MAX_VALUE;
                    for(int j=0;j<size;j++){
                        if(i!=j){
                            int distance = Distance(list.get(i), list.get(j));
                            min= Math.min(min, distance);
                        }
                    }
                    result.set(i,min);
                }
            }));
        }
        for(Future<?>future :futureList){
            future.get();
        }
        executorService.shutdown();
        return result;
    }

//单线程编辑距离算法
 public static  int Distance(List<String> temp,List<String> target){
        int m=temp.size();
        int n=target.size();
        if(m*n==0){
            return m+n;
        }
        int[][] d=new int[m+1][n+1];
        for(int i=0;i<m+1;i++){
            d[i][0]=i;
        }
        for(int j=0;j<n+1;j++){
            d[0][j]=j;
        }

        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                if(temp.get(i-1).equals(target.get(j-1))){
                    d[i][j]=d[i-1][j-1];
                }else{
                    d[i][j]=1+Math.min(d[i-1][j],Math.min(d[i][j-1],d[i-1][j-1]));
                }
            }
        }
        return d[m][n];
    }

测试结果

原版：

处理一万条数据(因为是双层循环，所以实际计算是1e次)，需要时间为13262毫秒

优化后：

只需要1710毫秒，大大提高计算效率！

其余代码

▼
java
复制代码
//    生成随机的3个数据
    public static  List<String> getRandom(){
//        打乱顺序
        Collections.shuffle(PGL_LIST);
//        打乱后截取前三个，某种意义上也是随机了吧
        return PGL_LIST.stream().limit(3).collect(Collectors.toList());
    }
//    生成指定数量的列表
    public static  List<List<String>> getList(int count){
        return IntStream.range(0, count).mapToObj(obj -> getRandom()).collect(Collectors.toList());
    }

但实际业务上，我们需要的应该是最匹配的用户的id或者是最匹配的一些用户的id，而不仅仅是最小的距离，这个数据并没什么意义。所以还要在此基础上做一些修改。在这里就不赘述了。

其他优化思路

最好是在计算时，获取前100位(数字随意)用户或队伍，然后缓存到Redis，之后用户在心动模式下进行匹配时，可以直接从缓存的心动用户列表中随机获取某一位用户。

当用户量大时，计算所有用户的心动用户，计算量就有点大了。可以考虑筛选出 近七天活跃用户，在此基础上再做计算。或者是 标记重点用户，对重点用户的心动用户提前计算，而非重点用户则是点击后再单独计算。

以上仅本人浅薄的观点(本人确实比较菜)，可能有很多不对的地方，还希望大家发现后指点一二(抱拳)。

震惊！我竟然在伙伴匹配系统项目中优化了编辑距离算法的打开方式！