Is there a "faster" way to iterate through a two-dimensional array than using nested for loops?

Question

I have written a program that encrypts and decrypts a file that gets read in using a foursquare cipher. Currently, I am storing the file to a character array, passing that into a function which breaks it up into bigrams, and encrypting it that way using nested for loops in another function. At this point, I'm basically trying to optimize the running time. Is there an alternative way to iterate through the two-dimensional array I'm using that doesn't use two for loops or, at the most, using only one for loop? Below is the relevant code:

FileHandler.java

   import java.io.*;
    import java.util.*;

    public class FileHandler {
    private List<String> characters = new ArrayList<String>();
    public char fileToChar[];

    public void preEncryptionFile(String fileText) throws IOException {
        String line;

        FileInputStream fileReader = new FileInputStream(fileText);
        DataInputStream dataInputStream = new DataInputStream(fileReader);
        BufferedReader bufferedReader = 
               new BufferedReader(new InputStreamReader(dataInputStream));

        while ((line = bufferedReader.readLine()) != null) {
            characters.add(line);
        }

        String charsToString = characters.toString();

        charsToString = charsToString.replaceAll("[^a-zA-Z]", "").toUpperCase();

        fileToChar = charsToString.toCharArray();

        bufferedReader.close();
    }
}

FourSquareCipher.java

    import java.util.*;

    public class FourSquareCipher {
        List<Character> encryptionList = new ArrayList<Character>();
        List<Character> decryptionList = new ArrayList<Character>();

        private char[][] matrix = { 
                { 'A', 'B', 'C', 'D', 'E', 'Z', 'G', 'P', 'T', 'F' },
                { 'F', 'G', 'H', 'I', 'K', 'O', 'I', 'H', 'M', 'U' }, 
                { 'L', 'M', 'N', 'O', 'P', 'W', 'D', 'R', 'C', 'N' },
                { 'Q', 'R', 'S', 'T', 'U', 'Y', 'K', 'E', 'Q', 'A' }, 
                { 'V', 'W', 'X', 'Y', 'Z', 'X', 'V', 'S', 'B', 'L' },
                { 'M', 'F', 'N', 'B', 'D', 'A', 'B', 'C', 'D', 'E' }, 
                { 'C', 'R', 'H', 'S', 'A', 'F', 'G', 'H', 'I', 'K' },
                { 'X', 'Y', 'O', 'G', 'V', 'L', 'M', 'N', 'O', 'P' }, 
                { 'I', 'T', 'U', 'E', 'W', 'Q', 'R', 'S', 'T', 'U' },
                { 'L', 'Q', 'Z', 'K', 'P', 'V', 'W', 'X', 'Y', 'Z' } };

        public void encryptionBigram(char[] fileToText) {
            int i;
            char x, y;

            for (i = 0; i < fileToText.length - 1; i += 2) {
                x = fileToText[i];
                y = fileToText[i + 1];

                encryption(x, y);
            }
        }

        private void encryption(char x, char y) {
            int i, j;
            int a, b, c, d;

            a = b = c = d = 0;

            for (i = 0; i < 5; i++) {
                for (j = 0; j < 5; j++) {
                    if (x == matrix[i][j]) {
                        a = i;
                        b = j;
                    }
                }
            }

            for (i = 5; i < 10; i++) {
                for (j = 5; j < 10; j++) {
                    if (y == matrix[i][j]) {
                        c = i;
                        d = j;
                    }
                }
            }

            encryptionList.add(matrix[a][d]);
            encryptionList.add(matrix[c][b]);
        }
}

Answer 1

Iterate over a 2D array using a single loop.

More specifically, this code calculates the row & column based on the current index & the width of the sub-arrays.

This will only work if the sub-arrays are of a fixed length/width.

I haven't benchmarked this, so I can't say for sure if it's more efficient than what you currently have. The overhead from checking a 2nd condition & incrementing a 2nd variable may be the same (or even less) than calculating the row & column.

Never-the-less:

char[][] letters = {
    {'A', 'B', 'C'},
    {'D', 'E', 'F'},
    {'G', 'H', 'I'}
};

int width = 3;
int maxIndex = letters.length * width;
for(int i = 0; i < maxIndex; i++) {
    int row = i / width; // determines row
    int column = i % width; // determines column

    System.out.println("Value["+letters[row][column]+"] Row["+row+"] Column["+column+"]");
}

The row is determined by dividing the index (represented by i) by the width. Since the width of the sub-arrays in the above example is 3:

• if the index is 6, the row is 2.
• if the index is 9, the row is 3.
• if the index is 11, the row is 3.66 (still 3)

The column is determined by modular arithmetic. Since every sub-array in the example above has width of 3:

• if the index is 6, the column is 0.
• if the index is 9, the column is 0.
• if the index is 11, the column is 2.

Answer 2

Asymptotically, there's not much to do, since your program still has O(n) time complexity - it reads every character and performs fixed 50 iterations in the two nested for loops for each character, plus some other constant-time work. Since you have to read all input, you can't get better asymptotically.

However, if you want to speed up your program somewhat, those nested for loops are indeed the place to start - in each of them, you're effectively performing a lookup - going through the 25 positions and looking for a match, then returning line and column. This can be improved by creating a Map that maps every letter to it's position data, and has constant asymptotic time complexity for get().

Answer 3

Using a break; will allow you to stop looping as soon as the value is matched, versus continuing through the loop even after you values have be found and set. Of course if your value is at the end of both loops, this may take longer. If your value is at the front of both loops, then you essentially cut out all the extra calculations. You could change your mappings to account for higher frequency letters by placing them in places to be found earlier in the loops.

    for (i = 5; i < 10; i++) {
        for (j = 5; j < 10; j++) {
            if (y == matrix[i][j]) {
                c = i;
                d = j;
                break; // Using break here allows you to do the minimum comparisons.
            }
        }
    }