子列表上的分区列表，其中相似的元素被分组

Question

我有一个

List<object>

元素。这个名单很大。列表大小约为 1M 条记录。我正在尝试对列表进行分区以获得每个分区的最小值和最大值，我会将它们传递给数据库查询。 我目前正在通过以下方式执行此操作：

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());
    //Do some processing on keys collected in the above list
    LongSummaryStatistics idStats = objects.stream().collect(Collectors.summarizingLong(e -> e));
    repo.callToDb(idStats.getMin(), idStats.getMax());
    //further processing
}

上面的代码工作正常，但我在我的对象中重复了键，如下所示：
输入：

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]

当我使用上面的代码进行分区时，块大小为：2，我得到的分区为：

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

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

相反，我希望第一个分区中的键不要在第二个分区上重复。

所以，本质上我希望分区看起来像这样：

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());
    //Do some processing on keys collected in the above list
    Pair<Long, Long> minMaxPair = minMaxPairMap.get(i);
    repo.callToDb(minMaxPair.getFirst(), minMaxPair.getSecond());
    //further processing
}

是否有更好的方法来实现这一目标，因为我觉得我已经将其复杂化以实现我想要的目标？

Answer 1

仅当数据按键排序或至少聚类时，移动分区边界才有意义，否则，任意其他分区中可能存在其他出现情况。

如果数据已排序，任务就相当简单了。执行像

ListUtils.partition

这样的方法，但添加一个检查分区的最后一个元素的键是否与下一个分区的第一个元素的键匹配，如果是，则增加分区的结束索引：

static <T, K extends Comparable<? super K>> List<List<T>> partition(
    List<T> data, int minSize, Function<T, K> keyFunction) {

    List<T> workingCopy = new ArrayList<>(data);
    workingCopy.sort(Comparator.comparing(keyFunction));

    List<List<T>> result = new ArrayList<>();
    for(int ix = 0, ix2; ix < data.size(); ix = ix2) {
        ix2 = Math.min(workingCopy.size(), ix + minSize);
        for(K lastKey = keyFunction.apply(workingCopy.get(ix2 - 1));
            ix2 < data.size()
            && Objects.equals(lastKey, keyFunction.apply(workingCopy.get(ix2)));) {
            ix2++;
        }
        result.add(workingCopy.subList(ix, ix2));
    }

    return result;
}

这可以像这样进行测试

record TestObj(int key, String name) {}

List<TestObj> objectList = IntStream.range('A', 'Z')
    .mapToObj(c -> new TestObj(ThreadLocalRandom.current().nextInt(0, 10),
                               "" + (char)c))
    .toList();

List<List<TestObj>> partitions = partition(objectList, 6, TestObj::key);

System.out.println(partitions.size() + " partitions");

for(List<TestObj> p: partitions) {
    System.out.println("(" + p.size() + " elements)");
    p.forEach(System.out::println);
    System.out.println();
}

在 jdoodle.com 上测试

请注意，如果键不是

Comparable

，您可以将排序操作变成聚类操作，例如

Map<Object, Integer> chunkID = new HashMap<>();
List<List<TestObj>> partitions = partition(objectList, 6,
    o -> chunkID.computeIfAbsent(o.key(), k -> chunkID.size()));

由于这会按照出现的顺序为每个不同的键分配一个升序数字，然后用于排序，因此它将最大限度地减少对遇到顺序所做的更改，如果元素已经聚类，则不会发生任何更改。