4
\$\begingroup\$

The data are in a file called test.txt, which is available at https://drive.google.com/file/d/1g0ffvH5oP5C4Cp6ciEp_L1Rst6WeTuYG/view?usp=sharing. There are some odd formatting things about it which I cannot replicate by putting on this website, hence I'm hosting it on my Google Drive. It is just simulated data, so there are no privacy concerns about using it.

I would like to cut down on the computational time of this code in Java.

import java.io.FileInputStream;
import java.lang.Math;
import java.util.Scanner;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.FileOutputStream;

public class BlockBootstrapTest {

    // B(x, i, L) is the subset of x which starts at index i (based on 1-indexing 
    // as opposed to 0-indexing) and has length L
    public static double[] B(double[] x, int i, int L) {
        double[] out = new double[L];
        for (int j = 0; j < L; j++)
            out[j] = x[i - 1 + j];
        return out;
    }

    // Sum of an array

    public static double sum(double[] x) {
        double s = 0;
        for (int i = 0; i < x.length; i++)
            s += x[i];
        return s;
    }

    // Mean of an array
    public static double mean(double[] x) {
        return sum(x)/((double) x.length);
    }

    // Compute B-bar_i
    public static double bMean(double[] x, int i, int L) {
        return(mean(B(x, i, L)));
    }

    // Compute MBB mean
    public static double mbbMu(double[] x, int L) {
        int n = x.length;
        double[] blockAvgs = new double[n - L + 1];

        for (int i = 0; i < n - L + 1; i++) {
            blockAvgs[i] = bMean(x, i + 1, L);  
        }

        return mean(blockAvgs);
    }

    // Compute MBB variance
    public static double mbbVariance(double[] x, int L, double alpha) {
        int n = x.length;
        double mbbMean = mbbMu(x, L);
        double[] diffs = new double[n - L + 1];

        for (int i = 0; i < n - L + 1; i++) {
            diffs[i] = Math.pow(L, alpha) * Math.pow(bMean(x, i + 1, L) - mbbMean, 2);
        }

        // Compute the summation
        double varSum = sum(diffs);
        double out = varSum / ((double) n - L + 1);
        return out;

    }

    // Compute NBB mean
    public static double nbbMu(double[] x, int L) {
        int n = x.length;
        int b = (int) Math.floor(((double) n) / L);
        double[] blockAvgs = new double[b];

        for (int i = 0; i < b; i++)
            blockAvgs[i] = bMean(x, 1 + ((i + 1) - 1) * L, L);

        return mean(blockAvgs);

    }

    // Compute NBB variance
    public static double nbbVariance(double[] x, int L, double alpha) {
        int n = x.length;
        int b = (int) Math.floor(((double) n) / L);
        double nbbMean = nbbMu(x, L);
        double[] diffs = new double[b];

        for (int i = 0; i < b; i++)
            diffs[i] = Math.pow(bMean(x, 1 + ((i + 1) - 1) * L, L) - nbbMean, 2);

        double varSum = Math.pow((double) L, alpha) * sum(diffs) / ((double) b);
        return varSum;

    }

    // factorial implementation
    public static double factorial(int x) {
        double out = 1;
        for (int i = 1; i < x + 1; i++)
            out *= i;
        return out;
    }

    // Hermite polynomial
    public static double H(double x, int p) {
        int upperIdx = (int) Math.floor(((double) p) / 2);

        double out = 0;
        for (int i = 0; i < upperIdx + 1; i++) {
            out += Math.pow(-1, i) * Math.pow(x, p - (2 * i)) / 
                ((factorial(i) * factorial(p - (2 * i))) * Math.pow(2, i));
        }
        out *= factorial(p);

        return out;

    }

    // Row means
    public static double[] rowMeans(double[][] x, int nrows, int ncols) {
        double[] means = new double[nrows];
        for (int i = 0; i < nrows; i++) {
            double[] row = new double[ncols];
            for (int j = 0; j < ncols; j++)
                row[j] = x[i][j];
            means[i] = mean(row);
        }
        return means;
    }

    public static void main(String[] argv) throws IOException {

        FileInputStream fileIn = new FileInputStream("test.txt");
        FileOutputStream fileOutMBB = new FileOutputStream("MBB_test.txt");
        FileOutputStream fileOutNBB = new FileOutputStream("NBB_test.txt");
        FileOutputStream fileOutMean = new FileOutputStream("means_test.txt");

        Scanner scnr = new Scanner(fileIn);
        PrintWriter outFSMBB = new PrintWriter(fileOutMBB);
        PrintWriter outFSNBB = new PrintWriter(fileOutNBB);
        PrintWriter outFSmean = new PrintWriter(fileOutMean);

        // These variables are taken from the command line, but are inputted here for ease of use.
        int rows = 5000;
        int cols = 3000;
        int minBlockSize = 0;
        int maxBlockSize = 2998; // this could potentially be any value < cols
        int p = 1;
        double alpha = 0.1;
        double[][] timeSeries = new double[rows][cols];

        // read in the file, and perform the H_p(x) transformation
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                timeSeries[i][j] = H(scnr.nextDouble(), p);
            }
            scnr.next(); // skip null terminator
        }

        // block bootstrap variance estimators
        double[][] outMBB = new double[rows][maxBlockSize];
        double[][] outNBB = new double[rows][maxBlockSize];

        // row means
        double[] sampleMeans = rowMeans(timeSeries, rows, cols);
        for (int i = 0; i < rows; i++) {
            outFSmean.print(sampleMeans[i] + " ");
        }
        outFSmean.println();
        outFSmean.close();

        for (int j = 0; j < rows; j++) {
            double[] row = new double[cols];
            for (int k = 0; k < cols; k++)
                row[k] = timeSeries[j][k];
            for (int m = minBlockSize; m < maxBlockSize; m++) {
                outMBB[j][m] = mbbVariance(row, m + 1, alpha);
                outNBB[j][m] = nbbVariance(row, m + 1, alpha);
                outFSMBB.print(outMBB[j][m] + " ");
                outFSNBB.print(outNBB[j][m] + " ");
            }
            outFSMBB.println();
            outFSNBB.println();
        }

        outFSMBB.close();
        outFSNBB.close();
    }
}

Note that p and alpha can take on any values for which ((double) p) * alpha < 1 is true.

A very high-level overview of what this code is doing

This is implementing a procedure known as block bootstrapping on Hermite-transformed data, and attempts to find the variance of a sample mean based on such a procedure for a particular type of time-series data. I will not bore you with the mathematical details of this procedure. Assume that the implementation is correct as is.

Depending on how the block bootstrap is executed (in the Wikipedia page linked above, it talks about "simple" and "moving" block bootstrapping), the formula of the variance of a sample mean changes and is executed using mbbVariance and nbbVariance. I need these variance values for various block lengths spit out into text files for each row of data.

It also outputs a third text file with the means for each row of data.

Please note that the Hermite polynomial implementation is based on the probabilists' Hermite polynomials formula at https://en.wikipedia.org/wiki/Hermite_polynomials#Explicit_expression.

What I know about this code:

  • The mbbVariance and nbbVariance parts are taking the most time out of all other lines of the code. Especially considering the fact that we could potentially be performing these operations 3000 times each per row for 5000 rows, my estimate is that it would take at least 20 hours just to process the loop in which these functions are executed. This is unacceptable, given that I have about 20 files that I will be processing. I know for a fact that this is executing correctly for smaller data sets, but it needs to be scaled up.
  • There are many layers of functions calling other functions in mbbVariance and nbbVariance. However, removing such function calls didn't cut down on the time it took to execute these functions.

I don't know much about data structures and algorithms, so anything from those topics that would be helpful for this problem I would love to know about. I'm also very new to Java.

\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

Four things come to mind immediately:

(1) You’re doing a lot of memory allocations.

(2) You’re doing a lot of copying of arrays.

(3) You have some unnecessary calls to pow() (which is very slow).

(4) You’re actually computing a factorial.

I think we can take care of (1) and (2) together. You have a lot of calls to B() that can eliminated if you implement a new version of mean() that works with an array subrange, rather than using bMean() to allocate, copy, and deallocate an array every single time it’s called. (This will also cut down on memory use, and likely do wonders for cache friendliness.)

Perhaps something like this (WARNING: untested code):

public static double sum(double[] x, int i, int L) {
    double s = 0;
    int hi = i + L;
    while (i < hi)
        s += x[i++];
    return s;
}

// Mean of an array
public static double mean(double[] x, int i, int L) {
    return sum(x, i, L)/((double) L);
}

Now all your calls to bMean() become calls to mean(), and will avoid a memory allocation, L copies of doubles, and a memory deallocation. It would be really interesting to track memory usage before and after the change.

Another place where item (2) can be avoided is in rowMeans(). Since you’re accessing the array by columns, there is no need to copy each row. Just use

means[i] = mean(x[i]);

For item (3), you can optimize your frequent calls to pow(2, i). If i is always than 64, use

x = 1L << i

If i is always less than 32, use

x = 1 << i

Otherwise, use a lookup table:

private static double[] pow2 = { 1.0, 2.0, 4.0, 8.0, … };   // up to the size you need
// later…
x = pow2[i];

If i can be greater than 64, just compute the table once rather than manually.

Finally, item (4) can also be sped up considerably using a lookup table.

private static double[] fact = { 1.0, 1.0, 2.0, 6.0, 24.0, … };  // up to the size you need

Again, if you need large factorials and don’t want to compute the table manually, compute the table once up front and then do a lookup.

\$\endgroup\$
3
\$\begingroup\$

My review is focused about simplification of your code using java DoubleStream and DoubleSummaryStatistics classes; I found some repeated operation in your code that can be avoided to slightly increase efficiency. You have the following methods in your code:

public static double sum(double[] x) {
    double s = 0;
    for (int i = 0; i < x.length; i++)
        s += x[i];
    return s;
}
    // Mean of an array
public static double mean(double[] x) {
    return sum(x)/((double) x.length);
}

These methods can be erased because already included in DoubleStream and DoubleSummaryStatistics. You have the following methods in your code:

// Compute B-bar_i
public static double bMean(double[] x, int i, int L) {
    return(mean(B(x, i, L)));
}
// Compute MBB variance
public static double mbbVariance(double[] x, int L, double alpha) {
    int n = x.length;
    double mbbMean = mbbMu(x, L);
    double[] diffs = new double[n - L + 1];
    for (int i = 0; i < n - L + 1; i++) {
        diffs[i] = Math.pow(L, alpha) * Math.pow(bMean(x, i + 1, L) - mbbMean, 2);
    }
    // Compute the summation
    double varSum = sum(diffs);
    double out = varSum / ((double) n - L + 1);
    return out;
}
// Compute NBB mean
public static double nbbMu(double[] x, int L) {
    int n = x.length;
    int b = (int) Math.floor(((double) n) / L);
    double[] blockAvgs = new double[b];
    for (int i = 0; i < b; i++)
        blockAvgs[i] = bMean(x, 1 + ((i + 1) - 1) * L, L);
    return mean(blockAvgs);
}
// Compute NBB variance
public static double nbbVariance(double[] x, int L, double alpha) {
    int n = x.length;
    int b = (int) Math.floor(((double) n) / L);
    double nbbMean = nbbMu(x, L);
    double[] diffs = new double[b];
    for (int i = 0; i < b; i++)
        diffs[i] = Math.pow(bMean(x, 1 + ((i + 1) - 1) * L, L) - nbbMean, 2);
    double varSum = Math.pow((double) L, alpha) * sum(diffs) / ((double) b);
    return varSum;
}

They can be rewritten in the following way:

// Compute B-bar_i
public static double bMean(double[] x, int i, int l) {
    return DoubleStream.of(b(x, i, l)).average().orElse(0);
}

// Compute MBB mean
public static double mbbMu(double[] x, int l) {
    DoubleSummaryStatistics statistics = new DoubleSummaryStatistics();

    for (int i = 0; i < x.length - l + 1; i++) {
        statistics.accept(bMean(x, i + 1, l));
    }

    return statistics.getAverage();
}

// Compute MBB variance
public static double mbbVariance(double[] x, int L, double alpha) {
    double mbbMean = mbbMu(x, L);
    DoubleSummaryStatistics statistics = new DoubleSummaryStatistics();

    for (int i = 0; i < x.length - L + 1; i++) {
        statistics.accept(Math.pow(L, alpha) * Math.pow(bMean(x, i + 1, L) - mbbMean, 2));
    }

    return statistics.getAverage();
}

// Compute NBB mean
public static double nbbMu(double[] x, int L) {
    int b = (int) Math.floor(((double) x.length) / L);
    DoubleSummaryStatistics statistics = new DoubleSummaryStatistics();

    for (int i = 0; i < b; i++) {
        statistics.accept(bMean(x, 1 + i * L, L)); 
    }

    return statistics.getAverage();
}

// Compute NBB variance
public static double nbbVariance(double[] x, int L, double alpha) {     
    int b = (int) Math.floor(((double) x.length) / L);
    double nbbMean = nbbMu(x, L);
    DoubleSummaryStatistics statistics = new DoubleSummaryStatistics();

    for (int i = 0; i < b; i++) {
        statistics.accept(Math.pow(bMean(x, 1 + i * L, L) - nbbMean, 2));
    }

    return Math.pow((double) L, alpha) * statistics.getAverage();
}

Another method rewritten using a DoubleStream:

// Row means
public static double[] rowMeans(double[][] x, int nrows, int ncols) {
    double[] means = new double[nrows];
    for (int i = 0; i < nrows; i++) {
        double[] row = new double[ncols];
        for (int j = 0; j < ncols; j++)
            row[j] = x[i][j];
        means[i] = DoubleStream.of(row).average().orElse(0);
    }
    return means;
}

In your main code you can calculate one time the factorial of p and pass it for the consecutive calls of your method h, here your version of the method not passing the factorial:

// Hermite polynomial
public static double H(double x, int p) {
    int upperIdx = (int) Math.floor(((double) p) / 2);
    double out = 0;
    for (int i = 0; i < upperIdx + 1; i++) {
        out += Math.pow(-1, i) * Math.pow(x, p - (2 * i)) / 
        ((factorial(i) * factorial(p - (2 * i))) * Math.pow(2, i));
    }
    out *= factorial(p);
    return out;
}

I added the new parameter factorialP to this method, probably it will be an increment of performance:

// Hermite polynomial
public static double h(double x, int p, int factorialP) {
    final int upperIdx = (int) Math.floor((double)p / 2);
    int out = 0;

    for (int i = 0; i < upperIdx + 1; i++) {
        out += Math.pow(-1, i) * Math.pow(x, p) / 
        ((factorial(i) * factorial(p)) * Math.pow(2, i));
        p -= 2;
    }

    return out * factorialP;

}

//later in your main method
int factorialP = factorial(p);
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        timeSeries[i][j] = h(scnr.nextDouble(), p, factorialP);
    }
    scnr.next(); // skip null terminator
}

I think is possible to parallelize operations because you are doing sum of elements and calculating average of them, but I have no further knowledge or experience about this argument to give an answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.