算法 - 对象分组

亦凉 2022-03-22 01:55 198阅读 0赞

我不清楚这是不是一个“算法”，但优化了分组逻辑，所以值得一记！

### 场景描述 ###

我们拥有一定数量的用户数据，需要根据地区、性别、年龄、职业来进行分组，对象类如下：

public class Person { 
      private String area;
      private String sex;
      private String age;
      private String job;
      ...
    }

如果使用java8提供的`Collectors.groupingBy`进行分组，我们需要四层循环  
**代码如下（仅供参考）**

public static void main(String args){ 
      // 假设为10W条记录
      List<Person> persons = Arrays.toList(...);
      // 根据地区分组
      Map<String, String> areaUserMap = persons.stream().collect(Collectors.groupingBy(Person::getArea));
      for(Map.Entry<String,String> areaUserEntry: areaUserMap.entrySet()){ 
        // 根据性别分组
        Map<String, String> sexUserMap = areaUserEntry.getValue().stream().collect(Collectors.groupingBy(Person::getSex));
        for(Map.Entry<String,String> sexUserEntry: sexUserMap.entrySet()){ 
          // 根据年龄分组
          Map<String, String> ageUserMap = sexUserEntry.getValue().stream().collect(Collectors.groupingBy(Person::getAge));
          for(Map.Entry<String,String> ageUserEntry: ageUserMap.entrySet()){ 
            // 根据职业分组
            Map<String, String> jobUserMap = ageUserEntry.getValue().stream().collect(Collectors.groupingBy(Person::getJob));
            for(Map.Entry<String,String> ageUserEntry: ageUserMap.entrySet()){ 
              // 最终得到ageUserEntry.getValue这个集合为一组
              // 业务实现（省略）
            }
          }
        }
      }
    }

**可读性**  
这么写代码无疑是会被骂娘的，而且性能低下

**性能分析（仅供参考）**

1.  首先分析这四层循环的次数，如果每层被分成了10组，那么就是10^4次方为1W次，分成了1W组，每组10个用户
2.  再分析4条Collectors.groupingBy语句，第一处groupingBy操作循环了10W次，将用户根据地区划分开；第二处groupingBy被循环调用10次，每次执行1W次，最终还是循环10W次；第三处第四处都是10W次，最终统计为40万+1W=41W次

### 分组优化 ###

**思路**  
1. 构造一个Map用于存储组，key为组ID（根据地区、性别、年龄和职业生成），value为List<用户>  
2. 为每一个用户虚拟一个组ID，如果根据组ID在Map中找到了组记录，则将当前用户纳入组内，否则创建一个新组。

**代码如下（仅供参考）**

public class Person { 
      private String area;
      private String sex;
      private String age;
      private String job;
      ...
      // 获取用户所属组ID
      public String getGroupId(){ 
        return area + "_" + sex + "_" + age + "_" + job;
      }
    }

public static void main(String[] args){ 
      List<Person> persons = Arrays.asList(...);
      Map<String, List<Person>> personGroup = new HashMap<>();
      for(Person person: persons){ 
        String groupId = person.getGroupId();
        if(personGroup.get(groupId) == null){ 
          personGroup.put(groupId, new ArrayList<>(Arrays.asList(person)));
          continue;
        }
        personGroup.get(groupId).add(person);
      }
    }

**可读性**  
代码简介，层次分明

**性能**  
10W条记录则循环10W次

### 总结（仅供参考） ###

使用Collectors.groupingBy进行分组时，如果根据一个条件分组还行，如果需要根据多条件分组，性能堪忧。

（完）