VPF::Скорость при использовании объектов и массивов

Mirkes

Дата 18.10.2013, 11:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

День добрый.
Модифицировал свою программу, приводя к более читаемому и легче модифицируемому виду и столкнулся с потрясающим эффектом торможения.
Вот фрагмент кода старой версии метода:

Код


        long t1=System.nanoTime();
        setCommonOptions(ans);
        if (classes > 2) {
            JOptionPane.showMessageDialog(null, "This method can be applyed for two class problems only");
            return;
        }
        if (classes == 1)
            return;
        takeParam();
        int vecLeng = inputs[0].length;
        PBDialog pb = PBDialog.getInstance();
        pb.init(records, outName + "-" + inName);
        //Calculate the means and covariance matrices
        // Create arrays for calculations
        double[][] mean = new double[2][vecLeng];
        double[][][] cov = new double[2][vecLeng][vecLeng];
        double[] det = new double[2];
        //Work variables
        int k;
        double mem[] = new double[2], work[] = new double[vecLeng];
        double w[] = new double[2], sum, n, d;
        int[][][] res = new int[wpc.length][2][2];
        int answ, answ2;
        //Start OLO loop
        for (int rec = 0; rec < records; rec++) {
            //Clear arrays for matrix and linked attributes
            MyArray.deepFillArray(mean, 0);
            MyArray.deepFillArray(cov, 0);
            //Correct ans
            k = ans.answers[rec];
            ans.power[k]--;
            //Preliminary fill of arrays
            for (int i = 0; i < records; i++) {
                if (i == rec)
                    continue;
                k = ans.answers[i];
                for (int j = 0; j < vecLeng; j++) {
                    mean[k][j] += inputs[i][j];
                    for (int r = 0; r < vecLeng; r++)
                        cov[k][j][r] += inputs[i][j] * inputs[i][r];
                }
            }

            // Normalize meanses
            for (k = 0; k < 2; k++)
                for (int i = 0; i < vecLeng; i++)
                    mean[k][i] /= ans.power[k];
            // Normalize covariations
            for (k = 0; k < 2; k++)
                for (int i = 0; i < vecLeng; i++)
                    for (int j = 0; j < vecLeng; j++) {
                        cov[k][i][j] /= ans.power[k];
                        cov[k][i][j] -= mean[k][i] * mean[k][j];
                    }

            // calculation of pseudo invers and pseudo determinant
            for (k = 0; k < 2; k++) {
                det[k] = PCA.pseudoInvers(cov[k]);
            }

            //Test excluded record
            answ = ans.answers[rec];
            for (k = 0; k < 2; k++) {
                d = MyMath.distanceMatrixSafeSq(cov[k], inputs[rec], mean[k], work);
                //Calculate probability density in point
                mem[k] = Math.exp(-d / 2) / Math.sqrt(det[k]);
            }
            //Using priory probability
            for (k = 0; k < 2; k++)
                mem[k] /= priorWeights[k];
            //Loop by weights
            for (int r = 0; r < wpc.length; r++) {
                if (mem[0] * wpc[r] > mem[1])
                    answ2 = 0;
                else
                    answ2 = 1;
                res[r][answ][answ2]++;
            }
            pb.addStep();
            //Restore ans
            k = ans.answers[rec];
            ans.power[k]++;
        }
        
        long t2 = System.nanoTime();
        System.out.println("Old version\t"+(t2-t1));

В качестве основной структуры данных использованы
double[][] inputs и поле answers в объекте ans.
Поскольку такой разброс данных по разным структурам не удобен, я создал в абстрактном классе, являющемся прототипом того, в котором реализованы оба метода, старый и новый, внутренний класс Record:

Код


    public static class Record {
        protected double[] values;
        protected int answer;
        protected double work = 0;

        public Record(double[] values, int answer) {
            this.values = values;
            this.answer = answer;
        }
    }

После чего написал новый расчетный метод на основе новой структуры данных:

Код


        long t1 = System.nanoTime();
        int[][][] res = (int[][][])ress;
        if (classes > 2) {
            JOptionPane.showMessageDialog(null, "This method can be applyed for two class problems only");
            return;
        }
        if (classes == 1)
            return;
        PBDialog pb = PBDialog.getInstance();
        pb.reinit(records);
        //Calculate the means and covariance matrices
        // Create arrays for calculations
        double[][] mean = new double[2][vecLeng];
        double[][][] cov = new double[2][vecLeng][vecLeng];
        double[] det = new double[2];
        //Work variables
        int k;
        double mem[] = new double[2], work[] = new double[vecLeng];
        double d;
        int answ, answ2;
        //Start OLO loop
        for (Record curr : learn) {
            //Clear arrays for matrix and linked attributes
            MyArray.deepFillArray(mean, 0);
            MyArray.deepFillArray(cov, 0);
            //Correct ans
            k = curr.answer;
            power[k]--;
            //Preliminary fill of arrays
            for (Record rec : learn) {
                if (curr == rec)
                    continue;
                k = rec.answer;
                for (int j = 0; j < vecLeng; j++) {
                    mean[k][j] += rec.values[j];
                    for (int r = 0; r < vecLeng; r++)
                        cov[k][j][r] += rec.values[j] * rec.values[r];
                }
            }

            // Normalize meanses
            for (k = 0; k < 2; k++)
                for (int i = 0; i < vecLeng; i++)
                    mean[k][i] /= power[k];
            // Normalize covariations
            for (k = 0; k < 2; k++)
                for (int i = 0; i < vecLeng; i++)
                    for (int j = 0; j < vecLeng; j++) {
                        cov[k][i][j] /= power[k];
                        cov[k][i][j] -= mean[k][i] * mean[k][j];
                    }

            // calculation of pseudo invers and pseudo determinant
            for (k = 0; k < 2; k++) {
                det[k] = PCA.pseudoInvers(cov[k]);
            }

            //Test excluded record
            answ = curr.answer;
            for (k = 0; k < 2; k++) {
                d = MyMath.distanceMatrixSafeSq(cov[k], curr.values, mean[k], work);
                //Calculate probability density in point
                mem[k] = Math.exp(-d / 2) / Math.sqrt(det[k]);
            }
            //Using priory probability
            for (k = 0; k < 2; k++)
                mem[k] /= priorWeights[k];
            //Loop by weights
            for (int r = 0; r < wpc.length; r++) {
                if (mem[0] * wpc[r] > mem[1])
                    answ2 = 0;
                else
                    answ2 = 1;
                res[r][answ][answ2]++;
            }
            pb.addStep();
            //Restore ans
            k = curr.answer;
            power[k]++;
        }
        long t2 = System.nanoTime();
        System.out.println("New version\t"+(t2-t1));

Легко заметить, что новый метод получен прямым копированием с последующим приведением циклов и обращений к данным к новой структуре. Можно также заметить, что в методах стоит отсчет времени. Вот результаты:

Код


New version    39594962042
Old version    5605102656
Old version    5722358901
Old version    4323833400
New version    37905207297
New version    39433632998

Невооруженным глазом видно, что новый метод работает почти в 8 раз медленнее старого.
Собственно вопрос.

Такое торможение это нормальное явление или я где-то круто наколбасил?
Например класс Record нужно было делать отдельным, а не вложенным?
Поля класса нужно было делать package protected или public?
Поля класса Record нужно было объявлять final?

Может еще какие идеи есть?

Заранее спасибо!

--------------------

Mirkes

Mirkes

Дата 18.10.2013, 12:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

Еще точнее локализовал место торможения:

Старый метод

Код


            tt-=System.nanoTime();

            //Preliminary fill of arrays
            for (int i = 0; i < records; i++) {
                if (i == rec)
                    continue;
                k = ans.answers[i];
                for (int j = 0; j < vecLeng; j++) {
                    mean[k][j] += inputs[i][j];
                    for (int r = 0; r < vecLeng; r++)
                        cov[k][j][r] += inputs[i][j] * inputs[i][r];
                }
            }
            tt+=System.nanoTime();

Новый метод

Код


            tt-=System.nanoTime();
            
            //Preliminary fill of arrays
            for (Record rec : learn) {
                if (curr == rec)
                    continue;
                k = rec.answer;
                for (int j = 0; j < vecLeng; j++) {
                    mean[k][j] += rec.values[j];
                    for (int r = 0; r < vecLeng; r++)
                        cov[k][j][r] += rec.values[j] * rec.values[r];
                }
            }

            tt+=System.nanoTime();

наружу выводится полное время в методе и суммарное время в данном фрагменте. плюс я потом посчитал время в остальной части метода и среднее время в остальной части метода:
New version     37,318,277,450     34,478,510,827     2,839,766,623
New version     36,169,007,371     33,488,532,797     2,680,474,574     2,735,056,488
New version     36,031,285,164     33,346,356,897     2,684,928,267
Old version       5,366,280,548       2,860,017,089     2,506,263,459
Old version       5,300,923,214       2,822,633,646     2,478,289,568     2,489,431,553
Old version       4,015,113,629       1,531,371,997     2,483,741,632

--------------------

Mirkes

Дата 18.10.2013, 12:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

Начал с тупого поиска причин и на первой же итерации получил вместо торможения некоторое (недостоверное) ускорение. Вот новый текст нового метода (фрагмент)

Код


            tt-=System.nanoTime();
            
            //Preliminary fill of arrays
//            for (Record rec : learn) {                             //ЭТО я убрал
            for (int rrr=0;rrr<learn.length;rrr++){            //Это я поставил
                rec=learn[rrr];
                if (curr == rec)
                    continue;
                k = rec.answer;
                for (int j = 0; j < vecLeng; j++) {
                    mean[k][j] += rec.values[j];
                    for (int r = 0; r < vecLeng; r++)
                        cov[k][j][r] += rec.values[j] * rec.values[r];
                }
            }

            tt+=System.nanoTime();

Легко заметить, что отличие от старого варианта только в организации цикла. Результаты для сравнения
старый результат
New version     37,318,277,450     34,478,510,827
New version     36,169,007,371     33,488,532,797
New version     36,031,285,164     33,346,356,897
новый результат
New version     5,099,199,203     2,589,693,051
New version     5,064,083,085     2,582,950,691
New version     4,030,317,983     1,539,601,223

Обращаюсь к документации

Цитата

The for-each construct is also applicable to arrays, where it hides the index variable rather than the iterator. The following method returns the sum of the values in an int array:

// Returns the sum of the elements of a
int sum(int[] a) {
    int result = 0;
    for (int i : a)
        result += i;
    return result;
}
So when should you use the for-each loop? Any time you can. It really beautifies your code. Unfortunately, you cannot use it everywhere. Consider, for example, the expurgate method. The program needs access to the iterator in order to remove the current element. The for-each loop hides the iterator, so you cannot call remove. Therefore, the for-each loop is not usable for filtering. Similarly it is not usable for loops where you need to replace elements in a list or array as you traverse it. Finally, it is not usable for loops that must iterate over multiple collections in parallel. These shortcomings were known by the designers, who made a conscious decision to go with a clean, simple construct that would cover the great majority of cases.

Цитата

class EnhancedForDemo {
    public static void main(String[] args){
         int[] numbers =
             {1,2,3,4,5,6,7,8,9,10};
         for (int item : numbers) {
             System.out.println("Count is: " + item);
         }
    }
}
In this example, the variable item holds the current value from the numbers array. The output from this program is the same as before:
Count is: 1
Count is: 2
Count is: 3
Count is: 4
Count is: 5
Count is: 6
Count is: 7
Count is: 8
Count is: 9
Count is: 10
We recommend using this form of the for statement instead of the general form whenever possible.

Действительно, данная конструкция делает код понятнее, но потери в производительности в 7 раз - это круто. Везде в других местах в Гугле пишут что конструкции приблизительно одинаковы, но for each более читаемая.
Еще и рекомендуют использовать эту форму везде, где только можно!

Интересно, это мне так везет, или никто просто не пытался использовать этот цикл в счетных частях?

Это сообщение отредактировал(а) Mirkes - 18.10.2013, 13:12

--------------------

Mirkes

Дата 18.10.2013, 15:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

Провел тест вне прочего контекста

Код


package test;

import java.util.Random;

public class Tesst {

    protected int vecLeng = 10;

    public Tesst() {
        //To select size
        int size = 100000;
        //Create the array of int and double
        int[] idats = new int[size];
        double[][] ddats = new double[size][vecLeng];
        Record[] recs = new Record[size];
        Random rnd = new Random();
        //fill arrays
        for (int i = 0; i < size; i++) {
            idats[i] = rnd.nextInt(2);
            for (int j=0;j<vecLeng;j++)
            ddats[i][j] = rnd.nextDouble();
            recs[i] = new Record(idats[i], ddats[i]);
        }
        //Now all ready to test as a test goal I select calculation of two covariance matrix.
        int stat = 1; //size of sumple
        //Output header
        System.out.println("iter\tForArrays\tForRecords\tForEachRecord");
        for (int i = 0; i < stat; i++)
            System.out.println(i + "\t" + calcForArray(idats, ddats) +
                    "\t" + calcForRecordArray(recs) +
                    "\t" + calcForEachRecord(recs));
    }

    public static void main(String[] args) {
        new Tesst();
    }

    public long calcForArray(int[] idats, double[][] ddats) {
        double[][][] cov = new double[2][vecLeng][vecLeng] ;
        int[] counts = new int[2];
        double[][] mean = new double[2][vecLeng];
        long t = -System.nanoTime();
        int k=0;
        for (int i = 0; i < idats.length; i++) {
            k= idats[i];
            counts[k]++;
            for (int j=0;j<vecLeng;j++){
                mean[k][j]+=ddats[i][j];
                for (int m=0;m<vecLeng;m++)
                    cov[k][j][m]+=ddats[i][j]*ddats[i][m];
            }
        }
        t += System.nanoTime();
        nextWork(cov,mean,counts);
        return t;
    }

    public long calcForRecordArray(Record[] dats) {
        double[][][] cov = new double[2][vecLeng][vecLeng] ;
        int[] counts = new int[2];
        double[][] mean = new double[2][vecLeng];
        long t = -System.nanoTime();
        int k=0;
        for (int i = 0; i < dats.length; i++) {
            k= dats[i].idat;
            counts[k]++;
            for (int j=0;j<vecLeng;j++){
                mean[k][j]+=dats[i].ddat[j];
                for (int m=0;m<vecLeng;m++)
                    cov[k][j][m]+=dats[i].ddat[j]*dats[i].ddat[m];
            }
        }
        t += System.nanoTime();
        nextWork(cov,mean,counts);
        return t;
    }

    public long calcForEachRecord(Record[] dats) {
        double[][][] cov = new double[2][vecLeng][vecLeng] ;
        int[] counts = new int[2];
        double[][] mean = new double[2][vecLeng];
        long t = -System.nanoTime();
        int k=0;
        for (Record rec:dats){
            k= rec.idat;
            counts[k]++;
            for (int j=0;j<vecLeng;j++){
                mean[k][j]+=rec.ddat[j];
                for (int m=0;m<vecLeng;m++)
                    cov[k][j][m]+=rec.ddat[j]*rec.ddat[m];
            }
        }
        t += System.nanoTime();
        nextWork(cov,mean,counts);
        return t;
    }


    //Method to show the necessity of calculated value

    public double nextWork(double[][][]cov,double[][]mean,int[]counts){
        return (cov[0][0][0]+mean[0][0]) / counts[0];
    }

    public static class Record {
        protected int idat;
        protected double[] ddat;

        public Record(int i, double[] d) {
            idat = i;
            ddat = d;
        }
    }
}

Методы фактически такие же, но никакой статистически достоверной разницы в скорости выполнения не наблюдается.
Такое впечатление, что смена типа цикла приводит в случае основной программы к каким-то дополнительным расходам. Понять бы еще каким. Займусь профайлером.

Тему закрываю, скорее всего ее следует удалить, поскольку сухой остаток такой:
smile

При запуске под отладчиком без профайлера в некоторых ситуациях циклы for each тормозят.
Однако если пустить в IDE но без отладчика или с отладчиком но с профайлером - тогда все нормально.
IDE JDeveloper. При каких условиях - не знаю и искать не буду.
Сожалею о Вашем времени, потраченном на чтение всего этого

--------------------

Mirkes

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »