Java.Help

[Пух]

У меня быстрая сортировка

import java.util.Random;

class Quicksort {
    public static void qsort (int items[]) {
        qs(items, 0, items.length-1);
    }

    private static void qs(int a[], int left, int right){
        int i=left;
        int j=right;
        int m = a[(left+right)/2];
        do {
            while(a[i] < m ) i++;
            while(m <a[j]) j--;

            if (i<=j) {
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                i++; j--;
            }
        } while(i<=j);

        if(left<j) qs(a, left, j);
        if(i<right) qs(a, i, right);
    }
 
    public static void main(String[] args) {
        int [] a = new int [10000000];
        Random rand = new Random ();

        for (int i = 0; i < a.length; i++){
            a[i] = rand.nextInt(7000);
        }
        long start = System.nanoTime();
        qsort(a);
        long time = System.nanoTime() - start;
        System.out.println("time = " + ((double)time / Math.pow(10,9)) + " seconds");
    }
}

и пирамидальная сортировка

import java.util.Random;

class Heap {

    private static void downHeap(int a[], int k, int n){
        int newElem = a[k];
        int child;

        while (k <= n/2){
            child = 2*k;
            if (child < n && a[child] < a[child + 1] )
                child++;
            if (newElem >= a[child]) break;
            a[k] = a[child];
            k = child;
        }
        a[k] = newElem;
    }

    public static void sortHeap(int a[]){
        int i = 0;
        int temp = 0;

        for (i = a.length/2 - 1; i >= 0; i--){
            downHeap(a,i,a.length-1);
        }

        for(i=a.length-1; i > 0; i--){
            temp=a[i]; 
            a[i]=a[0];
            a[0]=temp;
            downHeap(a, 0, i-1);
        }
    }


    public static void main(String[] args) {
        int [] a = new int [10000000];
        Random rand = new Random ();

        for (int i = 0; i < a.length; i++){
            a[i] = rand.nextInt(7000);
        }
        long start = System.nanoTime();
        sortHeap(a);
        long time = System.nanoTime() - start;
        System.out.println("time = " + ((double)time / Math.pow(10,9)) + " seconds");
    }
}

запускал c Windows 7 (32bit), Linux (Mint, 32bit). Метод main одинаковый для двух классов. Массив случайных чисел размером 10 млн.

tessio@tessio-desktop ~ $ javac Heap.java
tessio@tessio-desktop ~ $ java Heap
time = 6.025920925 seconds
tessio@tessio-desktop ~ $ javac Quicksort.java
tessio@tessio-desktop ~ $ java Quicksort
time = 1.246984762 seconds

Согласно википедии сложность быстрой сортировки в среднем n*logn, пирамидальной - гарантировано n*logn. Вопрос:
почему быстрая сортировка работает в 5 раз быстрее ?
Может я пирамидальную не правильно написал?

 

[dreamer]

Ява много времени тратит на инициализацию, поэтому надо повторять действие много раз, чтобы измерить время, например у меня следующий код (при немного переделанном вашем):

    public static void main(String[] args) {
        Sorter sorter = args[0].equals("quick") 
            ? new Quick()
            : new Heap();
            
        final int size = Integer.parseInt(args[1]);
        final int count = Integer.parseInt(args[2]);
        
        final int [] original = new int [size];
        final int [] copy = new int [size];
        Random rand = new Random ();

        for (int i = 0; i < original.length; i++){
            original[i] = rand.nextInt(7000);
        }
        
        System.out.printf("Sorting %d elements with %s for %d times%n", 
            size, args[0], count);
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
            System.arraycopy(original, 0, copy, 0, size);
            sorter.sort(copy);
        }
        double time = (System.nanoTime() - start);
        System.out.printf("Result %.8f%n", (time/count)/1e9);
    }

Это тоже не претендует на отличный код, но результаты следующие:

Sorting 7000 elements with quick for 1000 times
Result 0,00081534

Sorting 7000 elements with heap for 1000 times
Result 0,00091705

Разница невелика, кроме того если асимптотическая скорость одинаковая, то это не значит, что и реальная будет одинаковой.
Одинаковым будет ее рост при росте размеров массива.

 

[Пух]

dreamer, спасибо! Переписал как вы сказали, теперь всё намного лучше:

tessio@tessio-desktop ~/sort1 $ java Sorter quick 100000 1000
Sorting 100000 elements with quick for 1000 times
Result 0,01326927
tessio@tessio-desktop ~/sort1 $ java Sorter heap 100000 1000
Sorting 100000 elements with heap for 1000 times
Result 0,01903841

 

[Пух]

К примеру, есть такой код (конструкторы использовать нельзя).

class Vector{
	
	private double vector [];
	
	public void setSize(int size){
		vector = new double[size];
	}
	
	public double getElem(int index){
		return vector[index];
	}
	
	public int getLength(){
		return vector.length;
	}
	
	public void setElem(int index, double value){
		vector[index] = value;
	}
}

Есть методы setSize, getElem, getLength, setElem. Теперь в остальных методах как получать доступ к элементам вектора? Через массив или через метод getElem ?
То есть, к примеру метод getMin() как правильней написать?

	public double getMin(){
		double min = Double.POSITIVE_INFINITY;
		for (double elem:vector){
			if (elem < min){
				min = elem;
			}
		}
		return min;
	}

или

	public double getMin(){
		double min = Double.POSITIVE_INFINITY;
		for (int i = 0; i < getLength(); i++){
			if (getElem(i) < min){
				min = getElem(i);
			}
		}
		return min;
	}

Работать то оно и так и так будет, интересует как правильней делать))

 

[PainKiller]

Хз, кому как, но я за первый вариант, если перебирать массив, то foreach, мне кажется, удобнее. Возник вопрос, а почему нельзя использовать конструкторы?=)

 

[ImMortal]

Мне тоже думается что первый вариант удобнее.

 

[Пух]

Хз, кому как, но я за первый вариант, если перебирать массив, то foreach, мне кажется, удобнее. Возник вопрос, а почему нельзя использовать конструкторы?=)

По заданию так.
Ну что удобней использовать foreach то понятно, только вот правильно ли это?

 

[akl]

Если уже методы реализовал - то используй.

 

[Пух]

class Test{
    public static void main(String args[]){
        BigDecimal a = new BigDecimal(1.0/3, MathContext.UNLIMITED);
        int n = a.toString().length();
        System.out.println(n);
    }
}

вывод: 56.
Больше никак?

 

[dreamer]

Есть методы setSize, getElem, getLength, setElem. Теперь в остальных методах как получать доступ к элементам вектора? Через массив или через метод getElem ?

Работать то оно и так и так будет, интересует как правильней делать))

Правильнее использовать для действий те методы, которые для них задуманы. Ведь для этого методы и нужны?
Тогда изменить действие можно только в одном месте (в методе) а не по всему коду.