如何按不重复Key分组拆分List？优化百万级数据分区方案

我有一个约100万条记录的List<object>，需要将其分区，获取每个分区的min和max值传入DB查询。

当前实现代码 #

int gridSize = 6;
List<object> objectList = findAll();
List<List<object>> partitionedList = ListUtils.partition(objectList, (objectList.size() + gridSize - 1) / gridSize);
for(List<object> objects : partitionedList) {
    List<Long> keys = objects.stream().map(x -> x.getKey()).collect(Collectors.toList());
    // 对收集到的keys做处理
    LongSummaryStatistics idStats = objects.stream().collect(Collectors.summarizingLong(e -> e));
    repo.callToDb(idStats.getMin(), idStats.getMax());
    // 后续处理
}

存在的问题 #

数据中存在重复Key的元素，示例输入如下：

Car[id: 1, name:Tesla, Key: 1]
Car[id: 2, name:Tesla-3, Key: 2]
Car[id: 3, name:Tesla-Y, Key: 2]
Car[id: 4, name:Tesla-S, Key: 3]

按当前代码以chunk size=2分区时，同一Key的元素会被分到不同分区（比如Key=2的元素会跨两个分区）。

期望的分区结果 #

相同Key的元素必须在同一分区，示例分区结果应为：

Partition-1:
Car[id: 1, name:Tesla, Key: 1]
Car[id: 2, name:Tesla-3, Key: 2]
Car[id: 3, name:Tesla-Y, Key: 2]

Partition-2:
Car[id: 4, name:Tesla-S, Key: 3]

自行实现的代码 #

我自己写了一段实现，但感觉过于复杂，想咨询是否有更优的方式：

int gridSize = 6;
List<List<object>> partitionedList = new ArrayList<>();
Map<Integer, Pair<Long, Long>> minMaxPairMap = new HashMap<>();
List<object> objectList = findAll();
List<object> uniqueKeys = objectList.stream()
                .filter(distinctByKey(x -> x.getKey())).collect(Collectors.toList());
List<List<object>> uniqueKeysPartition = ListUtils.partition(uniqueKeys,
                (uniqueKeys.size() + gridSize - 1) / gridSize);
for (int i = 0; i < uniqueKeysPartition.size(); i++) {
    List<object> ojList = uniqueKeysPartition.get(i);
            LongSummaryStatistics longSummaryStatistics = ojList.stream().map(object::getKey).collect(Collectors.toList()).stream().collect(Collectors.summarizingLong(e -> e));
    minMaxPairMap.put(i, Pair.of(longSummaryStatistics.getMin(), longSummaryStatistics.getMax()));
    partitionedList.add(objectList.subList(
                    getFirstIndexOf(objectList, longSummaryStatistics.getMin()),
                    getLastIndexOf(objectList, longSummaryStatistics.getMax()) + 1));
}
for (int i = 0; i < partitionedList.size(); i++) {
    List<Long> keys = objects.stream().map(x -> x.getKey()).collect(Collectors.toList());
    // 对收集到的keys做处理
    Pair<Long, Long> minMaxPair = minMaxPairMap.get(i);
    repo.callToDb(minMaxPair.getFirst(), minMaxPair.getSecond());
    // 后续处理
}

优化实现方案 #

假设原objectList是按Key升序排列的（从你的实现逻辑来看应该满足这个前提），可以采用更简洁的遍历拆分方式，无需额外处理唯一Key的分区和索引查找：

int gridSize = 6;
List<object> objectList = findAll();
List<List<object>> partitionedList = new ArrayList<>();

// 统计唯一Key的数量
Set<Long> uniqueKeys = objectList.stream().map(obj -> obj.getKey()).collect(Collectors.toSet());
int uniqueKeyCount = uniqueKeys.size();
int targetKeysPerPartition = (uniqueKeyCount + gridSize - 1) / gridSize; // 向上取整

if (objectList.isEmpty()) {
    return;
}

int startIndex = 0;
long currentKey = objectList.get(0).getKey();
int keyCountInCurrentPartition = 1;

for (int i = 1; i < objectList.size(); i++) {
    long nextKey = objectList.get(i).getKey();
    if (nextKey != currentKey) {
        keyCountInCurrentPartition++;
        currentKey = nextKey;
        // 当当前分区的Key数量达到目标值时，拆分分区
        if (keyCountInCurrentPartition > targetKeysPerPartition) {
            partitionedList.add(objectList.subList(startIndex, i));
            startIndex = i;
            keyCountInCurrentPartition = 1;
        }
    }
}
// 处理最后一个分区
partitionedList.add(objectList.subList(startIndex, objectList.size()));

// 遍历分区进行后续处理
for (List<object> partition : partitionedList) {
    List<Long> keys = partition.stream().map(obj -> obj.getKey()).distinct().collect(Collectors.toList());
    // 对keys做处理
    long minKey = partition.get(0).getKey();
    long maxKey = partition.get(partition.size() - 1).getKey();
    repo.callToDb(minKey, maxKey);
    // 后续处理
}

方案优势 #

1. 只需要一次遍历原List即可完成分区，避免了多次流操作和索引查找，性能更优（适合百万级数据）
2. 逻辑简洁直观，利用原List的有序性，保证同Key元素不会跨分区
3. 自动控制每个分区包含的Key数量接近目标值，符合gridSize的分区需求

内容的提问来源于stack exchange，提问作者Vamsi