Dúvida com ordenações

24 de junho de 2007 9 respostas

francislon 24 de junho de 2007

Pessoal, estou fazendo um trabalho da facul e nele tenho que resolver o seguinte problema:

Calcular o tempo médio que algoritmos de ordenação demoram para ordenar um vetor de um determinado tamanho. No inicio o vetor terá um tamanho que eu determinarei(tamanho * 1), depois ele terá: (tamanho * 2), depois: (tamanho*4), depois: (tamanho * 8), depois: (tamanho * 16).

Irei ordenar estes vetores com os seguintes algoritmos: bubbleSort, insertSort, quickSort.

Para fazer isto escolhi fazer cada ordenacao e calculos de tempo em classes separadas: OrdenacaoBolha, OrdenacaoInsercao, OrdenacaoRapida. Escolhi implementar uma classe abstrata Ordenacao para facilitar o desenvolvimento.

Vamos às classes:

Classe Ordenacao.java:

package ordenando;

import java.util.Random;

/**
 *
 * @Autor: Francislon Silva
 */
public abstract class Ordenacao {
    public static final int NUM_MAT = 2;
    
    public int[] criaVetor(int tamanho)
    {
        int i;
        int vet[];
        Random aleatorio = new Random();
        
        vet = new int[tamanho];
        for(i=0;i<tamanho;i++)
        {
            vet[i] = 0 + aleatorio.nextInt(5000);
        }
        return vet;
    }    
    
    public void trocar(int vet[], int num, int num2)
    {
        int aux;
        
        aux = vet[num];
        vet[num] = vet[num2];
        vet[num2] = aux;
    
    }
    
    public abstract void calculandoOrdenacao();
    public abstract double[] getMedia();
    
}

Classe OrdenacaoBolha.java:

package ordenando;

/**
 *
 * @Autor: Francislon Silva
 */

public class OrdenacaoBolha extends Ordenacao{
    private double media[];
    
    
    public OrdenacaoBolha() {
        media = new double[5];
    }
    
    private void ordenar(int vet[]) {
        int i;
        int j;
        int aux;
        
        for(i=0;i<(vet.length);i++) {
            for(j=0;j<(vet.length-i-1);j++) {
                if(vet[j]>vet[j+1]) {
                    trocar(vet, j, j+1);
                } //end if
            } // end for j
        } // end for i
    } // end ordenar
    
    
    public void calculandoOrdenacao() {
        int i;
        int j, aux, tam;
        double inicio, fim, soma;
        int vet[]; 
        
        for(i = 0; i&lt5; i++) {
            soma = 0;
            
            for(j = 0; j &lt 100; j++){
                tam = (int)(NUM_MAT * Math.pow(2, i));
                vet = criaVetor(tam);           
                //System.out.println(NUM_MAT * Math.pow(2, i));
                inicio = System.nanoTime();
                ordenar(vet);
                fim = System.nanoTime();
                
                /*for(aux = 0; aux<vet.length;aux++) {
                    System.out.println(vet[aux]);
                }*/
                
                soma += (fim - inicio);
            } //end for j
            System.out.println("Soma: " + soma);
            media[i] = soma/100;
            System.out.println("Media quando o vetor tem tamanho " + ((i+1)*10) + " " + media[i]);
        } //end for i
        
    } // end calculandoOrdenacao
    
    public double[] getMedia() {
        return media;
    }
}

Classe OrdenacaoInsercao.java:

package ordenando;

/**
 *
 * @Autor: Francislon Silva
 */

public class OrdenacaoInsercao extends Ordenacao{
    private double media[];
    
    public OrdenacaoInsercao() {
        media = new double[5];
    }
    
    private void ordenar(int[] v) { 
         for (int i = 1; i >&lt v.length; i++) { 
            int value = v [i], j = i - 1;
            while ( j &gt= 0 && value &lt v [j] ) { 
               v[j + 1] = v [j];
               j--;
            }
                                
            v[j + 1] = value;
         }
      }
    

    public void calculandoOrdenacao() {
        int i;
        int j, aux, tam;
        double inicio, fim, soma;
        int vet[]; 
        
        for(i = 0; i&lt5; i++) {
            soma = 0;
            
            for(j = 0; j &lt 100; j++){
                tam = (int)(NUM_MAT * Math.pow(2, i));
                vet = criaVetor(tam);           
                //System.out.println(NUM_MAT * Math.pow(2, i));
                inicio = System.nanoTime();
                ordenar(vet);
                fim = System.nanoTime();
                
                /*for(aux = 0; aux<vet.length;aux++) {
                    System.out.println(vet[aux]);
                }*/
                
                soma += (fim - inicio);
            } //end for j
            System.out.println("Soma: " + soma);
            media[i] = soma/100;
            System.out.println("Media quando o vetor tem tamanho " + ((i+1)*10) + " " + media[i]);
        } //end for i
        
    }

    public double[] getMedia() {
        return media;
    }
    
}

Classe OrdenacaoRapida.java:

package ordenando;

/**
 *
 * @Autor: Francislon Silva
 */

public class OrdenacaoRapida extends Ordenacao{
    private double media[];
    /** Creates a new instance of OrdenacaoRapida */
    public OrdenacaoRapida() {
        media = new double[5];
    }
    
    private void ordenar(int vet[], int inicio, int fim)
    {
        int j;
        while (inicio >&lt fim) {
            j = separa(vet, inicio, fim);
            ordenar(vet, inicio, j-1);
            inicio = j + 1;
        }
    }
    
    private int separa(int v[], int p, int r) {
        int t, c = v[p], i = p+1, j = r;
        while (/*A*/ i &lt= j) {
            if (v[i] &lt= c) ++i;
            else if (c &lt v[j]) --j;
            else {
                t = v[i]; v[i] = v[j]; v[j] = t;
                ++i; --j;
            }
        }
        // agora i == j+1
        t = v[p]; v[p] = v[j]; v[j] = t;
        return j;
    }

    public void calculandoOrdenacao() {
         int i;
        int j, aux, tam;
        double inicio, fim, soma;
        int vet[]; 
        
        for(i = 0; i&lt5; i++) {
            soma = 0;
            
            for(j = 0; j &lt 100; j++){
                tam = (int)(NUM_MAT * Math.pow(2, i));
                vet = criaVetor(tam);           
                //System.out.println(NUM_MAT * Math.pow(2, i));
                inicio = System.nanoTime();
                ordenar(vet, 0, tam-1);
                fim = System.nanoTime();
                
                /*for(aux = 0; aux<vet.length;aux++) {
                    System.out.println(vet[aux]);
                }
                */
                soma += (fim - inicio);
            } //end for j
            System.out.println("Soma: " + soma);
            media[i] = soma/100;
            System.out.println("Media quando o vetor tem tamanho " + ((i+1)*10) + " " + media[i]);
        } //end for i
        
        
    }

    public double[] getMedia() {
        return media;
    }
    
    
}

A questão é o seguinte galera: teria alguma forma mais prática/eficiente de fazer isto? Pois cada um tem uma forma de enxergar a implementação de determinado problema.

Outra dúvida, eu estou passando um vetor como parametro para ordenar em outra classe. Já ouvi dizer que em Java todas as passagens de parametros são copias, mas também já ouvi dizer que é possivel fazer da forma que fiz. Alguém poderia esclarecer melhor isto? Afinal, em java tem ou não passagem por referencia? É correto fazer passagem por referencia? Isto vai contra a lógica de OO?

Agradeço a ajuda de todos.

9 Respostas

pango 25 de jun. de 2007

Cara,

objetos passados em parâmetros são sempre passados por referência, já que, na verdade, o que você está passando é o endereço em memória daquele objeto.

Marck 25 de jun. de 2007

O objeto é passado uma referencia e é possível alterar atributos desde que não se altere sua referência.

Ex.:

Coordenadas coo = new Coordenadas();

coordenadas(coo);

void coordenadas(Coordenadas coo){

    coo.x = 10;
    coo.y = 20;
}

Alteramos atributos do Objeto coordenadas.

void coordenadas(Coordenadas coo){

    coo = outroObjeto;
}

Invalido, pois estamos tentando alterar a refêrencia

Já variáveis primitivas são passados uma cópia de sua representação na memória.

int a = 10;

void primitivo(){
  
 b = a;   
 b = 20;
}

A variavel "a" ainda sim vale 10, pois para "b", foi passada apenas uma cópia.

A única excesão, qd falamos de objetos, é o String que se comporta da mesma maneira que as variaveis primitivas.

Espero ter ajudado e peço que me corrijam onde estiver errado.

Marck.

thingol 25 de jun. de 2007

a) O método “calculandoOrdenacao” pode ser movido para a classe abstrata Ordenacao. Como está, você tem um monte de “copy & paste” desnecessário.

b) System.nanoTime é um pouco “inexato” apesar de sua “precisão” absurda (bilionésimos de segundo). Em vez disso, a maneira correta de efetuar benchmarks é a seguinte: efetuar um loop de 1500 vezes o algoritmo a ser testado SEM MEDIR O TEMPO, para que o compilador JIT do Java efetue a compilação para código nativo), e então efetue um loop de 1000 vezes o seu algoritmo, sendo que esse tempo é que deve ser medido. Aí você terá um tempo “médio”.

Não se esqueça:

que o tempo de criar os dados deve ser excluído de seu cálculo;
que o array é alterado pela sua rotina de sort (ou seja, você tem de usar um “System.arraycopy” para fazer uma cópia “nova” dos dados desordenados sobre os dados ordenados);
e além disso, 5000 pontos são muito pouco para os computadores de hoje em dia (hum, esqueci que você estava usando “bubblesort” - 5000 pontos são muito para ele, mesmo para os computadores modernos). Use um valor um pouco maior.

francislon 26 de jun. de 2007

Pow pessoal, valeu mesmo pango, Marck e thingol. Deu pra entender muita coisa do que vcs falaram.

thingol disse:
O método “calculandoOrdenacao” pode ser movido para a classe abstrata Ordenacao. Como está, você tem um monte de “copy & paste” desnecessário.

Então thingol, eu ia colocar na classe abstrata, mas na classe OrdenacaoRapida, onde utilizo o quickSort para ordenar, o metodo recebe parametros diferentes. Mas irei seguir os seus conselhos

francislon 26 de jun. de 2007

Acabei esquecendo de uma duvida:

thingol disse:

Então qual outro método utilizo para ter mais exatidão?

thingol 26 de jun. de 2007

O que quis dizer é o seguinte: você pode usar System.nanoTime para medir tempo (é o jeito mais preciso de fazer isso em Java), mas não cronometre o tempo de execução de apenas 1 iteração; normalmente (a menos que a própria iteração seja muito, desesperadoramente muito lenta) você cronometra algumas iterações, e faz a média. Digamos que uma iteração leve 1 milissegundo; ora, mesmo que System.nanoTime tenha a precisão de 1 bilionésimo de segundo, pode ser que sua exatidão seja de 10 milissegundos (não sei qual o sistema operacional que você está usando, para poder lhe dizer com precisão o valor da exatidão). Então é melhor fazer umas 1000 iterações para você ter um tempo de cerca de 1 segundo para poder cronometrar.

francislon 26 de jun. de 2007

hum…
brigadão cara…
mas então o que será que é mais eficiente:

calcular o tempo de cada iteração, ir somando e depois calcular a média. Ou calcular o tempo de várias iterações e depois dividir pela quantidade de iterações feitas?

thingol 26 de jun. de 2007

Acho mais fácil dar um exemplo.

import java.util.*;

interface Testable {
    public int test (int iter);
}

/** Testando a ordenação via Arrays.sort */
class TestTarget1 implements Testable {
    Double[] array;
    Double[] originalArray;
    Random r = new Random();
    public TestTarget1 (int arraySize) {
         array = new Double [arraySize];
         for (int i = 0; i &lt arraySize; ++i) {
              array [i] = r.nextDouble();
         }
         originalArray = array.clone();
    }
    
    public int test (int iter) {
        System.arraycopy (originalArray, 0, array, 0, originalArray.length);
        Arrays.sort (array);
        return 0;
    }
}

/** Testando o "shuffling" */
class TestTarget2 implements Testable {
    List<Double> list;
    List<Double> originalList;
    Random r = new Random();

    @SuppressWarnings ("unchecked")
    public TestTarget2 (int arraySize) {
         list = new ArrayList<Double>();
         for (int i = 0; i &lt arraySize; ++i) {
              list.add (r.nextDouble());
         }
         originalList = (List)((ArrayList)list).clone();
    }

    @SuppressWarnings ("unchecked")
    public int test (int iter) {
        list = (List)((ArrayList)originalList).clone();
        Collections.shuffle (list);
        return 0;
    }
}

/** Testando a construção de um SortedSet */
class TestTarget3 implements Testable {
    Double[] array;
    Random r = new Random();

    public TestTarget3 (int arraySize) {
        array = new Double [arraySize];
        for (int i = 0; i &lt arraySize; ++i) {
             array[i] = r.nextDouble();
        }
    }

    public int test (int iter) {
        SortedSet<Double> set = new TreeSet<Double>();
        for (Double d : array) {
            set.add (d);
        }
        return 0;
    }
}


class BenchmarkGenerico {
     private Testable target;

     public void setTarget (final Testable pTarget) {
          target = pTarget;
     }
     
     public void warm (int iterations) {
         System.out.println ("Warming...");
         for (int i = 0; i &lt iterations; ++i) {
             target.test (i);
         }
     }
     
     public void benchmark (String message, int times, int iterations) {
         System.out.println ("Benchmarking...");
         long measured[] = new long [times];
         for (int i = 0; i &lt times; ++i) {
             long t = System.currentTimeMillis();
             for (int j = 0; j &lt iterations; ++j) {
                 target.test (j);
             }
             measured[i] = System.currentTimeMillis() - t;
         }
         Arrays.sort (measured);
         // Aqui só estou listando os tempos obtidos, mas é interessante
         // fazer algumas análises estatísticas.
         System.out.println (message);
         for (int i = 0; i &lt measured.length; ++i) {
             System.out.printf ("%.2f ms/iteration%n", (double) measured[i] / iterations);
         }
     }

     public static void main(String[] args) {
         BenchmarkGenerico bmg = new BenchmarkGenerico();
         bmg.setTarget (new TestTarget1(5000));
         bmg.warm(1000);
         bmg.benchmark("Benchmark para TestTarget1", 10, 1000);
         
         bmg.setTarget (new TestTarget2(5000));
         bmg.warm(1000);
         bmg.benchmark("Benchmark para TestTarget2", 10, 1000);
        
         bmg.setTarget (new TestTarget3(5000));
         bmg.warm(1000);
         bmg.benchmark("Benchmark para TestTarget3", 10, 1000);
     }
}

francislon 28 de jun. de 2007

Vlw mesmo thingol, terminei o trabalho seguindo os seus conselhos
Abraço

Criado 24 de junho de 2007

Ultima resposta 28 de jun. de 2007

Respostas 9

Participantes 4

9 Respostas

Topicos relacionados