помогите с оптимизацией алгоритма - PullRequest
0 голосов
/ 20 июня 2011

Я хотел бы оптимизировать этот алгоритм. Функция makeFrame делит аудиосигнал на временные рамки с использованием окна Хеннинга длительностью около 37 мс. Затем функция divideFreqs выполняет быстрое преобразование Фурье на каждом таймфрейме, используя библиотеку jtransforms (и именно она является наиболее трудоемкой). Как я мог сократить время этой операции, поскольку это занимает слишком много времени. Для аудиофайла длительностью 5 секунд выполнение операции занимает около 13 секунд. Я думал об использовании многопоточности, но никогда не использовал его раньше.

 public double[][] makeFrame(double[] audioOutput) {

            int length = audioOutput.length;

            //calculate a hannining window size of 37 ms
            int window = (int) Math.round(0.37 * sampleRate);
            int interval = (int) Math.round(0.0116 * sampleRate);
            length = length - window;
            int numintervals = length / interval;
            //calculate hanning window values
            double[] hanw = hanning(window);
            double[][] sections = new double[numintervals + 1][25];


            //divide the signal into timeframes using Hanning window of 37ms
            int k = 0;
            for (int i = 0; i < length; i += interval) {
                double[] temp = new double[88200];
                int t = 0;
                int s;

                s = i;

                for (; s < i + window; s++) {
                    temp[t] = audioOutput[s] * hanw[t];
                    t++;
                }
                sections[k] = divideFreqs(temp, sampleRate);
                k++;
            }

            return sections;
        }


public static double[] hanning(int window) {

int w = 0;

        double h_wnd[] = new double[window]; //Hanning window

        for (int i = 1; i < window; i++) { //calculate the hanning window
            h_wnd[i] = 0.5 * (1 - Math.cos(2.0 * Math.PI * i / (window + 1)));
        }

        return h_wnd;
    }

 public static double[] divideFreqs(double[] audioData, float fs) {

        DoubleFFT_1D fft = new DoubleFFT_1D(44100);
        int len;
        double[] secenergy;


        //Frequency bands in the range of 1Hz-20000Hz
        int[][] bandsec = new int[][]{
            {1, 100},
            {100, 200},
            {200, 300},
            {300, 400},
            {400, 510},
            {510, 630},
            {630, 770},
            {770, 920},
            {920, 1080},
            {1080, 1270},
            {1270, 1480},
            {1480, 1720},
            {1720, 2000},
            {2000, 2320},
            {2320, 2700},
            {2700, 3150},
            {3150, 3700},
            {3700, 4400},
            {4400, 5300},
            {5300, 6400},
            {6400, 7700},
            {7700, 9500},
            {9500, 12000},
            {12000, 15500},
            {15500, 20000}};


        //perform FFT on the data
        fft.realForwardFull(audioData);


        //splitting real and imaginary numbers
        double[] real = new double[22050];
        double[] imaginary = new double[22050];
        for (int row = 0; row < 22050; row++) {
            real[row] = (double) Math.round(audioData[row + row] * 100000000) / 100000000;
            imaginary[row] = (double) Math.round(audioData[row + row + 1] * 100000000) / 100000000;

        }

        len = bandsec.length;
        secenergy = new double[len];

        //calculate energy for each critical band
        double[] tempReal;
        double[] tempImag;
        for (int i = 0; i < len; i++) {
            int k = 0;
            tempReal = new double[bandsec[i][1] - (bandsec[i][0] - 1)];
            tempImag = new double[bandsec[i][1] - (bandsec[i][0] - 1)];

            for (int j = bandsec[i][0] - 1; j < bandsec[i][1]; j++) {

                tempReal[k] = real[j];
                tempImag[k] = imaginary[j];
                k++;
            }
            secenergy[i] = energy(tempReal, tempImag);

        }

        return secenergy;
    }

 public static double energy(double[] real, double[] imaginary) {
        double e = 0;

        Complex sum = new Complex(0, 0);
        ArrayList<Complex> complexList = new ArrayList<Complex>();

        for (int i = 0; i < real.length; i++) {
            Complex comp = new Complex(real[i], imaginary[i]);

            complexList.add(comp.multiply(comp));
        }

        for (int i = 0; i < complexList.size(); i++) {
            Complex comp = new Complex(complexList.get(i).getReal(), complexList.get(i).getImaginary());

            sum = Complex.add(comp, sum);


        }

        e = Math.sqrt(sum.magnitude());
        e = (double) Math.round(e * 10000) / 10000;
        return e;
    }

Ответы [ 4 ]

3 голосов
/ 20 июня 2011

Использование нескольких ядер поможет, но часто оптимизирует ваш код, что дает вам большие преимущества.

Использование двойного вместо сложного объекта на моей машине в 9 раз быстрее.

The average time using double took 38,687 ns
The average time using Complex took 344,010 ns

Тестовый код

public class EnergyTest {
    public static void main(String... args) {
        double[] real = new double[22050];
        double[] imaginary = new double[22050];
        for (int i = 0; i < real.length; i++) {
            real[i] = Math.random() - Math.random();
            imaginary[i] = Math.random() - Math.random();
        }
        {
            int runs = 100000;
            long start = 0;
            double e = 0;
            for (int i = -10000; i < runs; i++) {
                if (i == 0) start = System.nanoTime();
                e += energyDouble(real, imaginary);
            }
            assert e > 0;
            long time = System.nanoTime() - start;
            System.out.printf("The average time using double took %,d ns%n", time / runs);
        }
        {
            int runs = 10000;
            long start = System.nanoTime();
            double e = 0;
            for (int i = -10000; i < runs; i++) {
                if (i == 0) start = System.nanoTime();
                e += energy(real, imaginary);
            }
            assert e > 0;
            long time = System.nanoTime() - start;
            System.out.printf("The average time using Complex took %,d ns%n", time / runs);
        }
    }

    public static double energyDouble(double[] real, double[] imaginary) {
        double re_total = 0, im_total = 0;

        for (int i = 0; i < real.length; i++) {
            double re = real[i];
            double im = imaginary[i];
            double re2 = re * re - im * im;
            double im2 = 2 * re * im;
            re_total += re2;
            im_total += im2;
        }
        double e = Math.sqrt(re_total * re_total + im_total * im_total);
        e = (double) Math.round(e * 10000) / 10000;
        return e;
    }

    public static double energy(double[] real, double[] imaginary) {
        double e = 0;

        Complex sum = new Complex(0, 0);
        ArrayList<Complex> complexList = new ArrayList<Complex>();

        for (int i = 0; i < real.length; i++) {
            Complex comp = new Complex(real[i], imaginary[i]);

            complexList.add(comp.multiply(comp));
        }

        for (int i = 0; i < complexList.size(); i++) {
            Complex comp = new Complex(complexList.get(i).getReal(), complexList.get(i).getImaginary());

            sum = Complex.add(comp, sum);


        }

        e = Math.sqrt(sum.magnitude());
        e = (double) Math.round(e * 10000) / 10000;
        return e;
    }

    static class Complex {

        private final double re;
        private final double im;

        public Complex(double re, double im) {
            this.re = re;
            this.im = im;
        }

        public double getReal() {
            return re;
        }

        public double getImaginary() {
            return im;
        }

        public Complex multiply(Complex comp) {
            double re2 = re * comp.re - im * comp.im;
            double im2 = im * comp.re + re * comp.im;
            return new Complex(re2, im2);
        }

        public static Complex add(Complex a, Complex b) {
            return new Complex(a.re + b.re, a.im + b.im);
        }

        public double magnitude() {
            return re * re + im * im;
        }
    }
}
2 голосов
/ 22 июня 2011

Я не знаю вашу библиотеку, так как сам использую FFTW, но я заметил, что

1) your fft size is not a power of 2

2) your window is 370ms not 37ms.

3) Since your window has a size of 370ms (i.e. ~16k samples) why feed a 88200 
(or does the constructor value say "take only 44100 values"?) array into it? 
It is fully sufficient to take 
    pow(2.0, ceil(log2(0.37*44100))) = 2^14 = 16384
as your fft size. 
Zero padding wont add additional frequency resolution I'm afraid.

4) you instatiate a new FFT object for every call to divideFreq.
I'm not sure how expensive the construction is, so try make it a class member.

5) Last but not least (I think this is the major speed loss here) 
Your hop size is much too small! 
A common overlap is 1/2 or 2/3 of the window size 
(in terms of your code: interval = windowSize/3). 
Your's is around 1/31 of the window size. 
Thats really overkill give you many redundant results. 

ура

1 голос
/ 22 июня 2011

Чтобы БПФ действительно работал, вы должны иметь степень 2 как количество выборок. Это позволяет FFT работать в O (n * log (n)), а не выполнять DFT, который является O (n * n). Ваша библиотека, вероятно, достаточно умна, чтобы сделать это улучшение, если вы предоставите ввод правильного размера. К сожалению, это означает, что размер вашего окна не зависит от вас, так как он будет ограничен размерами 2,4,8,16 и т. Д. *

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

1 голос
/ 20 июня 2011

Несколько идей:

В makeFrame объявите double[] temp = new double[88200] вне цикла, чтобы избежать повторного выделения и освобождения памяти. (я не знаю, достаточно ли умен оптимизатор, чтобы сделать это сам по себе)

В divideFreqs, Какова цель Math.round(data*100000000)/100000000?Вы ограничиваете до 9 значащих цифр?Действительно ли 10-ая цифра так сильно влияет на результат?Если этот шаг не является строго необходимым, его устранение может сэкономить некоторое время.

Самая большая экономия, которую я вижу, будет получена за счет удаления всей конструкции и копирования в массивы real и imaginary.Похоже, что ваше БПФ оставляет audioData с чередованием 22050 вещественных / мнимых частей.Таким образом, вы можете изменить сигнатуру энергетической функции на energy(double fftData[], int lowFreq, int highFreq), и в этой функции заменить два цикла на:

      for (int i = 0; i <highFreq-lowFreq; i++) {
             Complex comp = new Complex(fftData[2*i], fftData[2*i+1]);
             sum=  Complex.add(sum, comp.multiply(comp)) 
      }

Затем заменить тело divideFreqs просто:

//...
fft.realForwardFull(audioData); //splitting real and imaginary numbers

len = bandsec.length;
secenergy = new double[len];  
for (int i = 0; i < len; i++) {  
    secenergy[i] = energy(audioData, bandSec[i][0], bandSec[i][1]-1)
}
return secenergy

Это позволяет избежать тонны выделения памяти, копирования и освобождения и должно значительно увеличить скорость.
После этих изменений для еще лучшей производительности вы можете заменить манипулирование комплексным числом прямыми двойными операциями, показанными @Peter.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...