并行排序顺序

Question

我正在实现一个分页器（在Java），它应该允许并行访问。

我有以下测试用例（测试在Groovy中，带有Spock）：

def 'parallel, two pages'()
{
    when: 'a sorted range from 0 to 6'
    def fetcher = new IntegerRangePageFetcher(6)

    and: 'a spliterator with a page size of 5'
    def spliterator = new PagedSpliterator(fetcher, 5)

    and: 'a stream with the given range is collected to a list'
    def result = StreamSupport
            .stream(spliterator, true)
            .collect(Collectors.toList())

    then: 'the sort order is obeyed'
    expect result, contains(0, 1, 2, 3, 4, 5)
}

此testcase失败,出现以下错误：

Condition not satisfied:

expect result, contains(0, 1, 2, 3, 4, 5)
|      |
false  [5, 0, 1, 2, 3, 4]

Expected: iterable containing [<0>, <1>, <2>, <3>, <4>, <5>]
     but: item 0: was <5>

拆分器具有特性()

return IMMUTABLE | ORDERED | SIZED | SUBSIZED | NONNULL;

当我不使用并行时，代码可以工作。所以我不理解ordered:

• 如果设置了，流框架是否应该保证顺序，并且应该在使用并行生成的块时对结果进行排序？如果是，为什么不在我的情况下排序？
• 还是我的trysplit实现中有错误，必须按照给定的顺序拆分？（当前我在打开页面的中间进行拆分，0-mid保留在当前的拆分器中，mid-end保留在新创建的拆分器中）
• 还是应该在collection()之前调用sort()因为框架根本不保证任何顺序？

---根据反馈进行更新---

谢谢你的回答，我的代码中有两个逻辑错误。首先，请求的代码段：

@Override
public Spliterator<T> trySplit()
{
    // first query
    if (pageIterator == null) {
        pageIterator = pageFetcher.fetchNextPage(paginationInfo);
    }

    // delegate split decision
    var newPaginationInfo = paginationInfo.split();
    if (newPaginationInfo == null) {
        log.info("* Spliterator returns null");
        return null;
    }

    // now we split
    var newSpliterator = new PagedSpliterator<>(pageFetcher, newPaginationInfo);
    return newSpliterator;
}

public PaginationInfo split()
{
    // when open range or nothing left we don't split
    if ((endElementIndex == -1) || !hasNextPage()) {
        return null;
    }

    // calculate the splitting position
    var firstHalfPages = (getEndPageIndex() - getNextPageIndex()) / 2;
    var midElementIndex = (getNextPageIndex() + firstHalfPages) * pageSize;

    // create an additional PaginationInfo and set the ranges according to the split position
    var newPaginationInfo = new PaginationInfo(this);
    newPaginationInfo.firstElementOnNextPageIndex = midElementIndex;
    newPaginationInfo.nextElementIndex = midElementIndex;

    endElementIndex = midElementIndex;

    return newPaginationInfo;
}

第一个错误：

新创建的拆分器被设置为第二个半范围，而不是第一个半范围。我在文档中读到了关于前缀的内容，但它对我来说感觉非常笨拙。我按页面大小拆分以有多个并行请求。在开始时（第一个spliterator实例），我必须获取第一个页面以获得页面和元素计数器。因此，为了解决顺序问题，我必须将从第一个拆分器获取的数据分发到第二个拆分器以服从顺序，这对我来说感觉很奇怪，也不直观。

第二个错误：

    // first query
    if (pageIterator == null) {
        pageIterator = pageFetcher.fetchNextPage(paginationInfo);
    }

所有后续创建的拆分器都将从框架接收EstimateSize()和TrySplit()调用。在此调用期间，当前我提取一个页面，但这将阻止并行性，该提取必须在TryAdvance()调用的稍后时间发生。

我会实现这些更改，然后再回到你身边。

Answer 1

从trysplit的文档中可以看到：

如果对此拆分器进行排序，则返回的拆分器必须覆盖元素的严格前缀。

您的实现：

...0-MID保留在当前的分裂器中，mid-end保留在新创建的分裂器中

你可以从这里连接适当的点。

Answer 2

是的，你的试玩中有个漏洞。spliterator.trysplit的文档指定，如果您具有ORDERED特性，则返回的spliterator必须包含元素的前缀。切换返回的拆分器和拆分器的剩余内容。