6

Ao trabalhar com Stream atualmente uso o método sorted para ordenar, exemplo:

    Stream<Integer> stream = Stream.of(3, 2, 1);
    stream.sorted(); // saida será 123

Qual o algoritmo de ordenação desse método?

Tem maneiras mais eficientes de ordenar usando Stream?

1
  • 4
    Provavelmente é o TimSort que é usado, mas não tenho como garantir essa informação Commented 8/01/2019 às 21:24

1 Resposta 1

11

Qual o algoritmo de ordenação desse método?

Estou no Java 11.

Primeiro, vejamos como o método sorted() é declarado na interface Stream:

Stream<T> sorted();

Ok, isso não nos ajuda. Ele é um método abstrato sem implementação default. Então, para achar a implementação, vejamos o código do Stream.of(...):

@SafeVarargs
@SuppressWarnings("varargs") // Creating a stream from an array is safe
public static<T> Stream<T> of(T... values) {
    return Arrays.stream(values);
}

Agora, o código do Arrays.stream(...):

public static <T> Stream<T> stream(T[] array) {
    return stream(array, 0, array.length);
}

E depois:

public static <T> Stream<T> stream(T[] array, int startInclusive, int endExclusive) {
    return StreamSupport.stream(spliterator(array, startInclusive, endExclusive), false);
}

Observe que os valores agora estão armazenados em um Spliterator.

Agora o StreamSupport.stream(...):

public static <T> Stream<T> stream(Spliterator<T> spliterator, boolean parallel) {
    Objects.requireNonNull(spliterator);
    return new ReferencePipeline.Head<>(spliterator,
                                        StreamOpFlag.fromCharacteristics(spliterator),
                                        parallel);
}

A classe java.util.stream.ReferencePipeline não é uma classe pública, mas o seu código ainda assim pode facilmente ser visto dentro da JDK:

abstract class ReferencePipeline<P_IN, P_OUT>
        extends AbstractPipeline<P_IN, P_OUT, Stream<P_OUT>>
        implements Stream<P_OUT>  {

Então, vamos ver a classe interna Head, que é enfim a implementação de Stream que procuramos:

static class Head<E_IN, E_OUT> extends ReferencePipeline<E_IN, E_OUT> {

A classe interna Head herda da classe externa ReferencePipeline e não sobrescreve o método sorted. Então, olhemos na superclasse (ReferencePipeline):

@Override
public final Stream<P_OUT> sorted() {
    return SortedOps.makeRef(this);
}

A classe SortedOps também não é pública. Vejamos que método é esse makeRef:

static <T> Stream<T> makeRef(AbstractPipeline<?, T, ?> upstream) {
    return new OfRef<>(upstream);
}

A classe OfRef é interna à SortedOps:

private static final class OfRef<T> extends ReferencePipeline.StatefulOp<T, T> {
    /**
     * Comparator used for sorting
     */
    private final boolean isNaturalSort;
    private final Comparator<? super T> comparator;

    /**
     * Sort using natural order of {@literal <T>} which must be
     * {@code Comparable}.
     */
    OfRef(AbstractPipeline<?, T, ?> upstream) {
        super(upstream, StreamShape.REFERENCE,
              StreamOpFlag.IS_ORDERED | StreamOpFlag.IS_SORTED);
        this.isNaturalSort = true;
        // Will throw CCE when we try to sort if T is not Comparable
        @SuppressWarnings("unchecked")
        Comparator<? super T> comp = (Comparator<? super T>) Comparator.naturalOrder();
        this.comparator = comp;
    }

    /**
     * Sort using the provided comparator.
     *
     * @param comparator The comparator to be used to evaluate ordering.
     */
    OfRef(AbstractPipeline<?, T, ?> upstream, Comparator<? super T> comparator) {
        super(upstream, StreamShape.REFERENCE,
              StreamOpFlag.IS_ORDERED | StreamOpFlag.NOT_SORTED);
        this.isNaturalSort = false;
        this.comparator = Objects.requireNonNull(comparator);
    }

    @Override
    public Sink<T> opWrapSink(int flags, Sink<T> sink) {
        Objects.requireNonNull(sink);

        // If the input is already naturally sorted and this operation
        // also naturally sorted then this is a no-op
        if (StreamOpFlag.SORTED.isKnown(flags) && isNaturalSort)
            return sink;
        else if (StreamOpFlag.SIZED.isKnown(flags))
            return new SizedRefSortingSink<>(sink, comparator);
        else
            return new RefSortingSink<>(sink, comparator);
    }

    @Override
    public <P_IN> Node<T> opEvaluateParallel(PipelineHelper<T> helper,
                                             Spliterator<P_IN> spliterator,
                                             IntFunction<T[]> generator) {
        // If the input is already naturally sorted and this operation
        // naturally sorts then collect the output
        if (StreamOpFlag.SORTED.isKnown(helper.getStreamAndOpFlags()) && isNaturalSort) {
            return helper.evaluate(spliterator, false, generator);
        }
        else {
            // @@@ Weak two-pass parallel implementation; parallel collect, parallel sort
            T[] flattenedData = helper.evaluate(spliterator, true, generator).asArray(generator);
            Arrays.parallelSort(flattenedData, comparator);
            return Nodes.node(flattenedData);
        }
    }
}

Note o Arrays.parallelSort(flattenedData, comparator);. É aqui que alguma ordenação está sendo feita:

@SuppressWarnings("unchecked")
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
    if (cmp == null)
        cmp = NaturalOrder.INSTANCE;
    int n = a.length, p, g;
    if (n <= MIN_ARRAY_SORT_GRAN ||
        (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
        TimSort.sort(a, 0, n, cmp, null, 0, 0);
    else
        new ArraysParallelSortHelpers.FJObject.Sorter<>
            (null, a,
             (T[])Array.newInstance(a.getClass().getComponentType(), n),
             0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
             MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}

E então temos a linha TimSort.sort(a, 0, n, cmp, null, 0, 0); denunciando que o algoritmo usado é o TimSort em alguns casos (no caso do if). Se isso cair no else, vejamos esse ArraysParallelSortHelpers.FJObject.Sorter:

static final class FJObject {
    static final class Sorter<T> extends CountedCompleter<Void> {
        static final long serialVersionUID = 2446542900576103244L;
        final T[] a, w;
        final int base, size, wbase, gran;
        Comparator<? super T> comparator;
        Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
               int wbase, int gran,
               Comparator<? super T> comparator) {
            super(par);
            this.a = a; this.w = w; this.base = base; this.size = size;
            this.wbase = wbase; this.gran = gran;
            this.comparator = comparator;
        }
        public final void compute() {
            CountedCompleter<?> s = this;
            Comparator<? super T> c = this.comparator;
            T[] a = this.a, w = this.w; // localize all params
            int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
            while (n > g) {
                int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
                Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
                                                  wb+h, n-h, b, g, c));
                Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
                                                  b+u, n-u, wb+h, g, c));
                new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
                new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
                Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
                                                  b+q, h-q, wb, g, c));
                new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
                s = new EmptyCompleter(bc);
                n = q;
            }
            TimSort.sort(a, b, b + n, c, w, wb, n);
            s.tryComplete();
        }
    }

E novamente, vemos o TimSort.sort(a, b, b + n, c, w, wb, n); lá.

Conclusão: O algoritmo usado é o TimSort.

Tem maneiras mais eficientes de ordenar usando Stream?

Isso depende muito da distribuição dos dados. Sem assumir nada sobre a distribuição dos dados, o algoritmo TimSort é um excelente algoritmo estável, com tempo de processamento Θ(n log n) e que tende a bater outros algoritmos que também são Θ(n log n). O TimSort é baseado no MergeSort, mas ele tenta se aproveitar de ordenamentos parciais dos dados sempre que possível para otimizar algumas coisas e pode seletivamente utilizar o InsertionSort em determinadas partes pequenas onde isso seria mais rápido que o MergeSort. Esse algoritmo também aproveita-se de várias outras possíveis otimizações.

Dito isso, é difícil haver uma forma mais eficiente de ordenar um Stream qualquer do que desse modo que serve para o caso geral. É difícil encontrar algum algoritmo de ordenação que possa bater o TimSort no caso geral. Além disso, a implementação dada ainda tenta paralelizar essa aplicação do TimSort se o array for grande o suficiente (é o que ocorre no ArraysParallelSortHelpers.FJObject.Sorter) para tentar obter um desempenho ainda melhor.

No entanto, se o seu Stream não for um Stream qualquer e sim algo que você saiba de antemão que tenha uma determinada estrutura ou ordenação específica da qual você pode tirar proveito para uma ordenação melhor, então nesses casos específicos, uma outra forma de ordenação melhor pode ser possível. Mas aí, cada caso é um caso.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .