匹配算法的优化

编辑距离算法

• 可查看之前的文档: 匹配算法

项目中使用

1. 使用场景: 匹配用户, 推荐用户
   • 根据用户标签推荐用户
2. 代码实现

    @Override
    public List<UserVO> matchUser(long num, User loginUser) {
        // 所有用户
        List<User> userList = this.list();
        // 登录用户的标签
        String loginUserTags = loginUser.getTags();
       
        // 将用户标签序列化
        Gson gson = new Gson();
        List<String> tagList = gson.fromJson(loginUserTags, new TypeToken<List<String>>() {
        }.getType());
       
        // 用户列表的下表 => 相似度
        SortedMap<Integer, Long> indexDistanceMap = new TreeMap<>();
        // 遍历所有用户, 获取标签, 计算相似度
        for (int i = 0; i < userList.size(); i++) {
            User user = userList.get(i);
            String userTags = user.getTags();
            //无标签的
            if (StringUtils.isBlank(userTags)) {
                continue;
            }
            List<String> userTagList = gson.fromJson(userTags, new TypeToken<List<String>>() {
            }.getType());
            //计算分数
            long distance = AlgorithmUtils.minDistance(tagList, userTagList);
            indexDistanceMap.put(i, distance);
        }
        //下面这个是打印前num个的id和分数
        List<UserVO> userListVo = new ArrayList<>();
        int i = 0;
        for (Map.Entry<Integer, Long> entry : indexDistanceMap.entrySet()) {
            if (i >= num) {
                break;
            }
            UserVO userVO = getUserVO(userList.get(entry.getKey()));
            userListVo.add(userVO);
            i++;
        }
        return userListVo;
    }
   

3. 存在问题
   • 时间复杂度: O(n^2), 遍历所有用户, 计算相似度, 时间复杂度为 O(n^2)
   • 实际测试 283万 用户, 响应时间要 64s, 速度极慢
   • 
4. 优化思路
   • 优化日志输出: 切忌不要在数据量大的时候循环输出日志
   • Map 存了所有的分数信息,占用内存
     • 思路: 维护一个固定长度的有序集合(sortedSet), 只保留分数最高的几个用户(时间换空间)
     • 比如: 要匹配5名相似度最高的用户, 现有集合中已经存在5个计算匹配分数最高的用户了, [3, 4, 5, 6, 7], 如果计算出来分数为3的用户, 就把3号用户替换掉集合中的4号用户, 再把3号用户放进去, 这样, 集合中就只保留5个分数最高的用户了.
   • 尽量只查需要的数据:
     • 过滤掉标签为空的用户
     • 根据部分标签取用户(前提是能区分出来哪个标签比较重要)
     • 只查需要的数据(比如 id 和 tags)
   • 提前查(定时任务)
     • 提前把所有用户给缓存(不适用于经常更新的数据)
     • 提前运算出来结果, 缓存(针对一些重点用户, 提前缓存)
5. 优化后代码

    @Override
    public List<UserVO> matchUser(long num, User loginUser) {
        QueryWrapper<User> queryWrapper = new QueryWrapper<>();
      
        // 只查询有标签的用户
        queryWrapper.isNotNull("tags");
        queryWrapper.select("id", "tags");
        List<User> userList = this.list(queryWrapper);
      
        // 序列化登录用户的标签
        String loginUserTags = loginUser.getTags();
        Gson gson = new Gson();
        List<String> tagList = gson.fromJson(loginUserTags, new TypeToken<List<String>>() {
        }.getType());
      
        // 用户列表的下标 => 相似度
        List<Pair<User, Long>> list = new ArrayList<>();
        // 依次计算当前用户和所有用户的相似度
        for (int i = 0; i < userList.size(); i++) {
            User user = userList.get(i);
            String userTags = user.getTags();
            //无标签的 或当前用户为自己
            if (StringUtils.isBlank(userTags) || Objects.equals(user.getId(), loginUser.getId())) {
                continue;
            }
            List<String> userTagList = gson.fromJson(userTags, new TypeToken<List<String>>() {
            }.getType());
            //计算分数
            long distance = AlgorithmUtils.minDistance(tagList, userTagList);
            list.add(new ImmutablePair<>(user, distance));
        }
        // 按编辑距离由小到大排序
        List<Pair<User, Long>> topUserPairList = list.stream()
                .sorted((a, b) -> (int) (a.getValue() - b.getValue()))
                .limit(num)
                .toList();
      
        // 有顺序的userID列表
        List<Long> userIdList = topUserPairList.stream().map(pari -> pari.getKey().getId()).toList();
      
        //根据id查询user完整信息
        QueryWrapper<User> userQueryWrapper = new QueryWrapper<>();
        userQueryWrapper.in("id", userIdList);
        Map<Long, List<UserVO>> userIdUserListMap = this.list(userQueryWrapper).stream()
                .map(this::getUserVO)
                .collect(Collectors.groupingBy(UserVO::getId));
      
        // 因为上面查询打乱了顺序，这里根据上面有序的userID列表赋值
        List<UserVO> finalUserListVO = new ArrayList<>();
        for (Long userId : userIdList) {
            finalUserListVO.add(userIdUserListMap.get(userId).getFirst());
        }
        return finalUserListVO;
    }
   

6. 优化后测试结果
   • 耗时减少到23s
   • 
   • 优化后, 速度提升了, 但还是有点慢, 后续可以考虑使用缓存优化