6

Eu conheço o algoritmo Quick Sort, mas, no momento, quero analisar o Merge Sort.

Encontrei na internet dois tipos de implementação do Merge Sort. Mas, quando os comparo com o algoritmo de Inserção, eles parecem ser menos eficientes e isto não é esperado para um grande número de itens.

Enter the number of elements you want to sort:
300000

Time spent to executing BubbleSort: 362123 milliseconds
Time spent to executing Selection:  108285 milliseconds
Time spent to executing Insertion:   18046 milliseconds
Time spent to executing MergeSort:   35968 milliseconds
Time spent to executing MergeSort2:  35823 milliseconds

Tem um outro jeito de implementar o Merge Sort para torná-lo mais eficiente que o algoritmo de Inserção ?

Vejam o meu código...

package br.com.test.test1;

import java.util.Random;
import java.util.Scanner;

 /**
 *
 * @author Joao
 */
public class Main {

    // generate an int array with random numbers between 0 and 500
    public static int[] generateRand(int n){
        int[] randArray = new int[n];
        Random number = new Random();

        // random numbers between 0 and 500
        for (int i = 0; i < n; i++){
            randArray[i] = number.nextInt(501);
        }
        return randArray;
    }

    public static void main(String[] args) {
        long startTime;
        Scanner input = new Scanner(System.in);
        int n;

        System.out.println("Enter the number of elements you want to sort:");
        n = input.nextInt();

        MyArray array = new MyArray(n);
        int[] aux = new int[n];
        aux = generateRand(n);


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.bubblesort();
        // Time spent to executing BUBBLESORT 
        System.out.println("\nTime spent to executing BubbleSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.selection();
        // Time spent to executing SELECTION 
        System.out.println("Time spent to executing Selection: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.insertion();
        // Time spent to executing INSERTION 
        System.out.println("Time spent to executing Insertion: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort(0, n-1);
        // Time spent to executing MERGESORT 
        System.out.println("Time spent to executing MergeSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort2(0, n-1);
        // Time spent to executing MERGESORT 2
        System.out.println("Time spent to executing MergeSort2: "+(System.currentTimeMillis() - startTime)+" milliseconds");

    }
}

--- e ---

package br.com.test.test1;

/**
 *
 * @author Joao Paulo
 */
class MyArray {
    private int[] v;
    private int n;  // array index
    private int len;

    public MyArray(int length) {
        len = length;
        v = new int[len];
        n = 0;
    }

    public void copy(int[] k){
        n = 0;
        for (int i = 0; i < len; i++) {
            v[i] = k[i];
            n++;
        }
    }

    public void show(){
        for (int i = 0; i < n; i++) {
            System.out.print(" " + v[i]);
        }
        System.out.println("\n");
    }


    // *******  START OF ALGORITHMS TO SORT  *******

    // ----------   Start of BubbleSort and Selection   --------------
    public void bubblesort(){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n-1; j++) {
                if (v[j] > v[j+1]) {
                    change(j, j+1);
                }
            }
        }
    }

    public void selection() {
        int min;
        for (int i = 0; i < n-1; i++) {
            min = i;
            for (int j = i+1; j < n; j++){
                if (v[j] < v[min]){
                    min = j;
                }
            }
            change(i, min);
        }
    }

    private void change(int one, int two) {
        int temp = v[one];
        v[one] = v[two];
        v[two] = temp;
    }
    // ----------   End of BubbleSort and Selection   ----------------


    // ----------   Start of Insertion   -----------------------------
    public void insertion() {
        int i, j;
        int temp;
        for (i=1; i < n; i++) {
            temp = v[i];   // marked variable
            j = i;
            while ((j > 0) && (v[j-1] > temp)) {
                v[j] = v[j-1];
                j = j - 1;
            }
            v[j] = temp;
        }
    }
    // ----------   End of Insertion   -------------------------------


    // ----------   Start of MergeSort   -----------------------------
    public void mergeSort (int start, int end){
        if(start == end) return;

        int middle = (start+end)/2;
        mergeSort(start,middle);
        mergeSort(middle+1,end);
        merge(start,middle,end);
    }

    public void merge(int start, int middle, int end) {
        int[] aux = new int[v.length];

        for (int x = start; x <= end; x++) {
            aux[x] = v[x];
        }

        int i = start;
        int j = middle+1;
        int k = start;

        //emptying out array 'v' inserting items neatly in array 'aux' 
        while (i <= middle && j <= end) {
            if (aux[i] < aux[j]){
                v[k++] = aux[i++];
            } else {
                v[k++] = aux[j++];
            }
        }

        //copying values from 'aux' to 'v'
        while (i <= middle){
            v[k++] = aux[i++];
        }

        while (j <= end){
            v[k++] = aux[j++];
        }
    }
    // ----------   End of MergeSort   -------------------------------


    // ----------   Start of MergeSort 2  ----------------------------
    public void mergeSort2 (int start, int end) {
        if(start >= end) return;

        int middle = (start+end)/2;
        mergeSort2(start,middle);
        mergeSort2(middle+1,end);
        merge2(start,middle,end);
    }

    public void merge2(int start, int middle, int end) {
        int[] helper = new int[v.length];

        // Copy both parts into the helper array
        for (int i = start; i <= end; i++) {
            helper[i] = v[i];
        }

        int i = start;
        int j = middle + 1;
        int k = start;

        // Copy the smallest values from either the left or the right side back to the original array
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                v[k] = helper[i];
                i++;
            } else {
                v[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            v[k] = helper[i];
            k++;
            i++;
        }
        // Since we are sorting in-place any leftover elements from the right side
        // are already at the right position.
    }
    // ----------   End of MergeSort 2  ------------------------------

}
7
  • Creio que o primeiro ponto seja que uma única rodada não é um bom parâmetro. Quem sabe rodar umas 20 vezes e tirar a média é desvio padrão? Também não creio que seja interessante rodar com base em uma única situação inicial. Por último, você só tem 501 itens distintos (ou seria 500?, se começar do 1?), o algoritmo de inserção é ótimo quando há ordenação parcial (chegando a o(n) no melhor caso), já o mergesort sempre executará o(n log n) instruções 8/09/2017 às 4:11
  • Minha conclusão é que vejo maior problemática na metodologia de investigação do que de algoritmo propriamente dito 8/09/2017 às 4:12
  • Tem um ponto que detectei no merge2: o tamanho de memória extra do mergesort é n + o(log n) + o(1). Note que parte é constante, pois você precisa de um vetor auxiliar no algoritmo, não de um vetor auxiliar para cada chamada da função merge2. Outro ponto que ajuda é você passar sempre os dois vetores, alternando quem é o vetor principal e quem é o secundário na recursão. 8/09/2017 às 4:15
  • Ok @Jefferson Quesado! Vou seguir suas orientações. Obrigado! 8/09/2017 às 4:22
  • Fiz um pequeno modelo para fazer as contas. Só pegando aqui suas implementações das ordenações para testar e ver se os tempos são compatíveis 8/09/2017 às 4:55

1 Resposta 1

6

TL;DR

Otimizei a criação do vetor auxiliar de trabalho e o tempo esperado de se rodar o merge sort v3 é de 4.29 ms +- 0.78 ms

Veja os dados que obtive:

Repetições do experimento de BUBBLE SORT: 100
Total acumulado de BUBBLE SORT: 241062
Média de BUBBLE SORT: 2410.62
Desvio padrão de BUBBLE SORT: 235.99742251631358
Repetições do experimento de BUBBLE SORT MINIMO: 100
Total acumulado de BUBBLE SORT MINIMO: 163971
Média de BUBBLE SORT MINIMO: 1639.71
Desvio padrão de BUBBLE SORT MINIMO: 36.23835096700842
Repetições do experimento de BUBBLE SORT FLAGGED: 100
Total acumulado de BUBBLE SORT FLAGGED: 169241
Média de BUBBLE SORT FLAGGED: 1692.41
Desvio padrão de BUBBLE SORT FLAGGED: 51.61025170262282
Repetições do experimento de SELECTION SORT: 100
Total acumulado de SELECTION SORT: 35973
Média de SELECTION SORT: 359.73
Desvio padrão de SELECTION SORT: 13.946401729913024
Repetições do experimento de INSERTION SORT: 100
Total acumulado de INSERTION SORT: 11862
Média de INSERTION SORT: 118.62
Desvio padrão de INSERTION SORT: 57.24637168159279
Repetições do experimento de MERGE SORT: 100
Total acumulado de MERGE SORT: 33125
Média de MERGE SORT: 331.25
Desvio padrão de MERGE SORT: 30.73785380545715
Repetições do experimento de MERGE SORT (2): 100
Total acumulado de MERGE SORT (2): 32395
Média de MERGE SORT (2): 323.95
Desvio padrão de MERGE SORT (2): 11.65703065263035
Repetições do experimento de MERGE SORT (3): 100
Total acumulado de MERGE SORT (3): 429
Média de MERGE SORT (3): 4.29
Desvio padrão de MERGE SORT (3): 0.782317200386264

Resolvendo a questão calmamente

Realizei o teste com os seus 5 algoritmos de ordenação mais os seguintes outros que eu coloquei:

  1. bubblesort mínimo (cada iteração no laço externo garante que o maior elemento na parte desordenada fique na sua posição correta, não precisando ser reverificado)
  2. bubblesort mínimo com flag (semelhante ao mínimo, mas tem uma flag para detectar se houve alguma mudança; em caso negativo, o vetor está ordenado e podemos parar)
  3. mergesort com uma única alocação de memória (acabei pegando a implementação disponível na Wikipedia, versão top-down)

Para garantir os resultados do teste, todo vetor que iria ser ordenada era inicializado de maneira totalmente aleatória, com números distribuídos uniformemente no domínio dos inteiros com sinal de 32 bits ([-2^31, 2^31 - 1]). Rodei o teste 100 vezes e coletei os dados para fazer a média, soma total e desvio padrão.

Você pode acessar o repositório de teste no GitLab.

Dividi em 3 partes o código para ficar mais claro cada responsabilidade:

SortStuff.java

Esse cara aqui tem como função chamar o ordenador e coletar os dados, enviando para a parte de cálculos estatísticos cada rodada:

package sort;

import java.util.function.Consumer;
import java.util.function.LongSupplier;

public class SortStuff {
    public static final int SIZE_ARRAY = 30_000;
    public static final int N_REPETITION = 100;

    public static LongSupplier calculaTempo(Consumer<Array> metodoOrdenacao) {
        return () -> {
            Array a = Array.getRandomArray(SIZE_ARRAY);

            long init = System.currentTimeMillis();
            metodoOrdenacao.accept(a);
            return System.currentTimeMillis() - init;
        };
    }

    public static void main(String[] args) {
        Estatisticas estatBubble = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::bubbleSort));
        Estatisticas.printEstatisticas(estatBubble, "BUBBLE SORT");

        Estatisticas estatBubble2 = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::bubbleSort2));
        Estatisticas.printEstatisticas(estatBubble2, "BUBBLE SORT MINIMO");

        [...] /* basicamente a mesma coisa para as outras estratégias de ordenação */

        Estatisticas estatMerge3 = repeatGetEstatisticas(N_REPETITION, calculaTempo(Array::mergeSort3));
        Estatisticas.printEstatisticas(estatMerge3, "MERGE SORT (3)");
    }

    private static Estatisticas repeatGetEstatisticas(int n, LongSupplier l) {
        Estatisticas estat = new Estatisticas();
        for (int i = 0; i < n; i++) {
            estat.adicionaRodada(l.getAsLong());
            System.err.println("Terminou a rodada " + i);
        }

        return estat;
    }

}

Note que estou usando um pouco de expressões lambdas do Java 8 para diminuir o quanto de código produzi.

A função main faz a chamada para o repeatGetEstatisticas. No caso, ela configura qual vai ser a estratégia de ordenação sendo utilizada para medir o tempo.

Na função calculaTempo, dado um dos métodos de ordenação escolhidos, retorna uma outra função que conta o tempo necessário para fazer somente o tempo da ordenação. Os métodos de ordenação foram feitos de tal sorte que eles não possuem argumentos explícitos, e não possuem retorno. Então, eles se comportam como se fossem uma função que simplesmente consome o objeto que contém o vetor a ser ordenado. Lembre-se, o this que a gente menciona dentro de um método de instância é um argumento implícito passado para o método. Para simular a chamada do método daquele objeto, fiz metodoOrdenacao.accept(a).

A função repeatGetEstatisticas faz n vezes a operação passada. A operação passada é uma função que, ao ser executada, gera um long como resultado, que é imediatamente passado para a classe responsável pelos cálculos estatísticos. Sua saída é exatamente esse conjunto de dados produzidos.

Note que calculaTempo gera uma função que retorna o tempo demandado em mili segundos para ser usado em repeatGetEstatisticas.

Estatisticas.java

Faz os cálculos estatísticos. Nada de interessante, puro tédio.

Array.java

Classe que contém o vetor a ser ordenado v, o seu tamanho n e métodos de ordenação. Também fiz um inicializador aleatório passando o tamanho do vetor, o método estático Array.getRandomArray.

public static Array getRandomArray(int n) {
    Array a = new Array(n);

    Random number = new Random();

    for (int i = 0; i < n; i++) {
        // Random.nextInt() é, pelo que li, uniforme em todo o domínio
        // inteiro 32 bits
        a.v[i] = number.nextInt();
    }

    return a;
}

A única diferença relevante entre nossas duas inicializações aleatórias foi que eu escolho Random.nextInt(), que gera para o domínio dos inteiros uma distribuição uniforme. Você escolheu Random.nextInt(int bound), que gera uma distribuição uniforme no intervalo [0, bound), porém, como a quantidade de elementos requisitados era muito maior que esse limite, havia muita repetição dentro do vetor.

O outro ponto interessante é a terceira opção de mergesort que eu escrevi (baseado no verbete da Wikipedia, conforme supracitado):

public void mergeSort3() {
    // cria o vetor auxiliar uma única vez
    int aux[] = new int[n];

    System.arraycopy(v, 0, aux, 0, n);

    mergeSort3(aux, v, 0, n);
}

/**
 * ordenar o vetor no intervalo [ini,end), fechado no começo e aberto no
 * final
 * 
 * areaTrabalho vai carregar o etor ordenado, no final
 * 
 * @param entradaDesordenada
 *            vetor de entrada, não prometo alterar
 * @param areaTrabalho
 *            local onde vai acontecer o trabalho de ordenação das
 *            informações da entradaDesordenada
 * @param ini
 * @param end
 */
private void mergeSort3(int[] entradaDesordenada, int[] areaTrabalho, int ini, int end) {
    if (end - ini <= 1) {
        return;
    }

    int middle = (ini + end) / 2;
    mergeSort3(areaTrabalho, entradaDesordenada, ini, middle);
    mergeSort3(areaTrabalho, entradaDesordenada, middle, end);
    merge3(entradaDesordenada, areaTrabalho, ini, middle, end);
}

public void merge3(int[] entradaDesordenada, int[] areaTrabalho, int start, int middle, int end) {
    int i = start;
    int j = middle;

    for (int k = start; k < end; k++) {
        if (i < middle && (j >= end || entradaDesordenada[i] <= entradaDesordenada[j])) {
            areaTrabalho[k] = entradaDesordenada[i];
            i++;
        } else {
            areaTrabalho[k] = entradaDesordenada[j];
            j++;
        }
    }
}

Note que só há uma única chamada ao operador new int[]. Isso significa que o vetor auxiliar só é criado uma única vez. Evitar criar objetos em memória pode gerar resultados muito positivos, ainda mais quando a quantidade esperada de objetos adicionais criados seja de o(n) (com tamanho médio de o(log n) cada um) para um algoritmo cujo tempo de execução seja o(n log n).

Também não foi necessário fazer a cópia da areaTrabalho de volta para entradaDesordenada, o que economiza o(n) operações para cada chamada do método merge*, que vai juntar as duas metades ordenadas do vetor em uma única parte.

Uma outra pequena otimização que eu fiz, porém não fui atrás de estudar o efeito colateral, foi chamar a chamada System do Java para copiar vetores: System.arraycopy(v, 0, aux, 0, n);. Supostamente, chamar assim oferece uma performance muito mais eficiente do que a cópia feita manualmente por um laço.

Falo supostamente porque de fato eu não medi o tempo. Se não me engano, essa chamada System.arrayCopy faz uma chamada internamente à função memcpy do (descrita em string.h), ou então ao comando de processador para cópia de regiões de memória

Conclusão

Analisando os tempos, proporcionalmente eles estão meio coerentes com os resultados que você obteve (só o selectionsort que se saiu proporcionalmente melhor em relação ao insertionsort). Então, minha hipótese que coloquei nos comentários de possível falha na metodologia de avaliação foi falseada. Peço desculpas :-)

Retirando o fator da alocação de memória, o tempo do mergesort foi umas 25 vezes mais rápido do que o do insertionsort para 30.000 elementos. Em comparação às outras alternativas de mergesort que você tinha posto, foi 75 vezes mais rápido.

Eu também resolvi tirar uma última dúvida cruel, como seria o comportamento dos outros mergesorts caso o conjunto aumentasse de tamanho? Então fiz o teste para 100.000 elementos, 5 rodadas:

Repetições do experimento de INSERTION SORT: 5
Total acumulado de INSERTION SORT: 13589
Média de INSERTION SORT: 2717.8
Desvio padrão de INSERTION SORT: 1937.7354566606869
Repetições do experimento de MERGE SORT: 5
Total acumulado de MERGE SORT: 21585
Média de MERGE SORT: 4317.0
Desvio padrão de MERGE SORT: 98.35903618885253
Repetições do experimento de MERGE SORT (2): 5
Total acumulado de MERGE SORT (2): 23670
Média de MERGE SORT (2): 4734.0
Desvio padrão de MERGE SORT (2): 334.4233843498388
Repetições do experimento de MERGE SORT (3): 5
Total acumulado de MERGE SORT (3): 108
Média de MERGE SORT (3): 21.6
Desvio padrão de MERGE SORT (3): 1.6733200530681511

Note que, em média, os mergesorts antigos estão agora demorando "apenas" 2x o tempo do insertionsort; quando eram 30.000 elementos, eram 3x mais demorados, um indicativo de que com o tamanho da entrada, mesmo os mergesorts não otimizados podem ser melhores do que o insertionsort.

Outro ponto interessante é que o insertionsort apresentou um desvio padrão muito alto, uns 67% do tamanho médio. Isso, para mim, indica que o insertionsort não foi testado o suficiente, foram coletados poucos conjuntos de trabalho para ele. Precisaria repetir o teste umas 100 vezes ou mais para verificar se seu comportamento iria convergir para algum valor menos impreciso.

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 .