41

リストを値として並べ替えたストリーム (またはコレクター) に既に実装されている機能があるかどうか疑問に思っています。たとえば、次のコードは両方とも、年齢でソートされた、性別でグループ化された人物のリストを作成します。最初の解決策には、いくつかのオーバーヘッドの並べ替えがあります (そして少しだらしないように見えます)。2 番目の解決策は、すべての人を 2 回見る必要がありますが、きれいな方法で仕事をします。

最初に並べ替えてから、1 つのストリームにグループ化します。

Map<Gender, List<Person>> sortedListsByGender = (List<Person>) roster
        .stream()
        .sorted(Person::compareByAge)
        .collect(Collectors.groupingBy(Person::getGender));

最初にグループ化し、次にすべての値を並べ替えます。

Map<Gender, List<Person>> sortedListsByGender = (List<Person>) roster
        .stream()
        .collect(Collectors.groupingBy(Person::getGender));
sortedListsByGender.values()
        .forEach(list -> Collections.sort(list, Person::compareByAge));

のように、1回の実行でこれを行う何かが既に実装されているかどうか、私はただ疑問に思っていますgroupingBySorted。

4

1 に答える 1

36

sorted(comparator)操作の前にストリームで使用する場合collect、ストリームはストリームの内容全体をバッファリングしてソートできるようにする必要があり、後でグループの小さなリストをソートする場合と比較して、ソートにはそのバッファ内でより多くのデータ移動が必要になる場合があります。そのため、並列処理が有効になっている場合、実装では複数のコアが使用されますが、個々のグループを並べ替えるほどパフォーマンスは良くありません。

ただし、usingsortedListsByGender.values().forEach(…)は並列化可能な操作ではなく、using でもsortedListsByGender.values().parallelStream().forEach(…)グループの並列処理のみが許可されることに注意してください。ただし、各並べ替え操作はまだシーケンシャルです。

のようにコレクター内でソート操作を実行する場合

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collectors.collectingAndThen(
        Collectors.toCollection(ArrayList::new), l->{ l.sort(c); return l; } );
}

 

Map<Gender, List<Person>> sortedListsByGender = roster.stream()
    .collect(Collectors.groupingBy(Person::getGender, toSortedList(Person::compareByAge)));

並べ替え操作は同じように動作します (修正してくれた Tagir Valeev に感謝します) が、挿入時の並べ替え戦略がどのように実行されるかを簡単に確認できます。コレクターの実装を次のように変更するだけです。

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collectors.collectingAndThen(
        Collectors.toCollection(()->new TreeSet<>(c)), ArrayList::new);
}

完全を期すために、最後のコピー手順を回避するために最初にソートされたコレクターが必要な場合ArrayListは、次のようなより複雑なコレクターを使用できます。

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collector.of(ArrayList::new,
        (l,t) -> {
            int ix=Collections.binarySearch(l, t, c);
            l.add(ix<0? ~ix: ix, t);
        },
        (list1,list2) -> {
            final int s1=list1.size();
            if(list1.isEmpty()) return list2;
            if(!list2.isEmpty()) {
                list1.addAll(list2);
                if(c.compare(list1.get(s1-1), list2.get(0))>0)
                    list1.sort(c);
            }
            return list1;
        });
}

順次使用には効率的ですが、マージ機能は最適ではありません。基礎となる並べ替えアルゴリズムは事前に並べ替えられた範囲の恩恵を受けますが、マージ関数が実際にこれらの範囲を認識しているにもかかわらず、最初にこれらの範囲を見つける必要があります。残念ながら、JRE にはこれらの情報を利用できる公開 API がありません (効率的にsubLists を渡すことはできますbinarySearchが、 の要素ごとに新しいサブ リストを作成するlist2とコストがかかりすぎる可能性があります)。並列実行のパフォーマンスをさらに上げたい場合は、ソート アルゴリズムのマージ部分を再実装する必要があります。

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collector.of(ArrayList::new,
        (l,t) -> l.add(insertPos(l, 0, l.size(), t, c), t),
        (list1,list2) -> merge(list1, list2, c));
}
static <T> List<T> merge(List<T> list1, List<T> list2, Comparator<? super T> c) {
    if(list1.isEmpty()) return list2;
    for(int ix1=0, ix2=0, num1=list1.size(), num2=list2.size(); ix2<num2; ix2++, num1++) {
        final T element = list2.get(ix2);
        ix1=insertPos(list1, ix1, num1, element, c);
        list1.add(ix1, element);
        if(ix1==num1) {
            while(++ix2<num2) list1.add(list2.get(ix2));
            return list1;
        }
    }
    return list1;
}
static <T> int insertPos(
    List<? extends T> list, int low, int high, T t, Comparator<? super T> c) {
    high--;
    while(low <= high) {
        int mid = (low+high)>>>1, cmp = c.compare(list.get(mid), t);
        if(cmp < 0) low = mid + 1;
        else if(cmp > 0) high = mid - 1;
        else {
            mid++;
            while(mid<=high && c.compare(list.get(mid), t)==0) mid++;
            return mid;
        }
    }
    return low;
}

この最後のソリューションは、単純なbinarySearchベースの挿入とは異なり、安定した並べ替えの実装であることに注意してください。つまり、ソースストリームに定義された遭遇順序がある場合Person、同じ年齢の s であり、相対的な順序は変更されません。Gender

于 2016-03-09T20:23:59.427 に答える