2
\$\begingroup\$

I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there.

The exercise (translation):

Change the "divide and conquer"-Method for the search of the largest element in an array (program 5.6), so that you split the array in k parts, that differ in size by 1 at most and find the maximum in each part recursively to return the maximum of the entire array. (end of translation)

Therefore, for the first method call an array of length 13 and k of 3 should be split into parts of 5+4+4, then into parts of 2-2-1 (for 5) or 2+1+1 (for 4) and subsequently into 1-1-0 (for 2). Parts must always be at least of size 1. Parts of size 0 do not actually exist and are therefore unnecessary calls.

My approach

I have a recursive method that calls itself k-times (using a for-loop in the recursive method) every time it is invoked and does not trigger the base case. However, I was forced to create a second base-case for the "unnecessary" calls. Especially the fact that I had to make this second base case makes me uneasy if this still is an elegant solution.

To hide those variables that need to be given for the recursion but are unnecessary to know by the actual code I created a "Handler" method in lieu of anything better to call it.

Request

I still struggle with recursion, therefore I would like to ask to focus on the recursive method. I have the suspicion that it maybe should have been coded with a second recursive method instead of the forloop inside the recursive method. However, I ultimately also expected that to lead to even more convoluted code, due to recursion in a recursion, and therefore avoided it.

Program 5.6

static double max(double[] array, int left, int right){
        if (left == right){
            return array[left];
        }
        int middle = (left+right)/2;
        double u = max(array, left, middle);
        double v = max (array, middle+1, right);
        if (u>v){
            return u;
        } else {
            return v;
        }
    }

My Code

public class Aufgabe5_60 {
    private static int findMax2(int[] ar, int k, int l, int r) {
        if (l == r) { // Base Case 1
            return ar[l];
        } else if (l > r) { // Base Case 2, k > nNumbers, unnecessary calls
            return 0;
        } else {
            int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
            int max = 0; // maximum value between l and r

            /*
             * The left and right indices of the k parts you split the array
             * into. Every split-part contains nNumbers/k >= 1numbers. The
             * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
             */
            int[] left = new int[k];
            int[] right = new int[k];
            for (int i = 0; i < k; i++) {
                /*
                 * All left indices are either the left index of the array that
                 * is being split (l) or are the index following the right index
                 * of the last array-part. All right indices are left index +
                 * the size (nNumbers/k) this array-part should have while
                 * accounting for the fact that l alone already gives the
                 * array-part a size of 1 (-1). 
                 */
                left[i] = (i == 0) ? l : right[i - 1] + 1;
                right[i] = (nNumbers % k > i) ? left[i] + (nNumbers / k) : left[i] + (nNumbers / k) - 1;

                int temp = findMax2(ar, k, left[i], right[i]);
                if (temp > max) {
                    max = temp;
                }
            }
            return max;
        }
    }

    public static int findMaxHandler(int[] ar, int k) {
        return findMax2(ar, k, 0, ar.length - 1);
    }

    public static void main(String[] args) {
        /* Create and fill test array */
        int N = Integer.parseInt(args[0]);
        int[] array = new int[N];
        for (int i = 0; i < array.length; i++) {
            array[(int) Math.random() * array.length] = (i + 1) * 2;
        }

        int k = Integer.parseInt(args[1]);
        /* Print out maximum value in array */
        System.out.println(findMaxHandler(array, k));
    }
}
\$\endgroup\$
  • \$\begingroup\$ This looks like a lot of code where iterative would have been so much shorter and understandable... \$\endgroup\$ – Pimgd Apr 7 '17 at 22:08
  • \$\begingroup\$ @Pimgd On the one hand, I agree with you, on the other, recursion is still really difficult for me so I'm basically happy for any recursive exercise this book gives me. The more practice it gives, the easier I can write normal recursions later on, the easier I can get to bottom-up dynamic programming - which would make it iterative again. \$\endgroup\$ – Isofruit Apr 7 '17 at 22:11
  • \$\begingroup\$ perhaps the book will cover other data structures such as trees later on? Trees are well suited for recursion, iterating through them is a pain. \$\endgroup\$ – Pimgd Apr 7 '17 at 22:13
  • \$\begingroup\$ @Pimgd exactly that! This is an exercise of exactly the chapter where it starts covering trees. Next chapter is mathematical features of binary trees and looking at my current track record, one of those exercises will also make it onto code-review. \$\endgroup\$ – Isofruit Apr 7 '17 at 22:15
2
\$\begingroup\$
int temp = findMax2(ar, k, left[i], right[i]);
if (temp > max) {
    max = temp;
}

This can be shortened to

max = Math.max(max, findMax2(ar, k, left[i], right[i]));

right[i] = (nNumbers % k > i) ? left[i] + (nNumbers / k) : left[i] + (nNumbers / k) - 1;

This is hard to read. Splitting it up...

right[i] = (nNumbers % k > i) 
         ? left[i] + (nNumbers / k) 
         : left[i] + (nNumbers / k) - 1;

Riiight. So, why not...

right[i] = left[i] + (nNumbers / k);
if (nNumbers % k > i) {
    right[i] -= 1;
}

Well, it is a double write. Your choice.


Assuming earlier changes...

int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
int max = 0; // maximum value between l and r

/*
 * The left and right indices of the k parts you split the array
 * into. Every split-part contains nNumbers/k >= 1numbers. The
 * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
 */
int[] left = new int[k];
int[] right = new int[k];
for (int i = 0; i < k; i++) {
    /*
     * All left indices are either the left index of the array that
     * is being split (l) or are the index following the right index
     * of the last array-part. All right indices are left index +
     * the size (nNumbers/k) this array-part should have while
     * accounting for the fact that l alone already gives the
     * array-part a size of 1 (-1). 
     */
    left[i] = (i == 0) ? l : right[i - 1] + 1;
    right[i] = left[i] + (nNumbers / k);
    if (nNumbers % k > i) {
        right[i] -= 1;
    }

    max = Math.max(max, findMax2(ar, k, left[i], right[i]));
}
return max;

Left and right are read-only.

Your IDE might not tell you this, but, findMax2 is just pass-by-value. So...

left[i] = (i == 0) ? l : right[i - 1] + 1;

This is your only write to left.

    right[i] = left[i] + (nNumbers / k);
    max = Math.max(max, findMax2(ar, k, left[i], right[i]));

These are your only reads from left.

They're ALL using [i]. So, we can get rid of the entire left array. It's a useless array. Let's get rid of it.

int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
int max = 0; // maximum value between l and r

/*
 * The left and right indices of the k parts you split the array
 * into. Every split-part contains nNumbers/k >= 1numbers. The
 * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
 */
int[] right = new int[k];
for (int i = 0; i < k; i++) {
    /*
     * All left indices are either the left index of the array that
     * is being split (l) or are the index following the right index
     * of the last array-part. All right indices are left index +
     * the size (nNumbers/k) this array-part should have while
     * accounting for the fact that l alone already gives the
     * array-part a size of 1 (-1). 
     */
    int left = (i == 0) ? l : right[i - 1] + 1;
    right[i] = left + (nNumbers / k);
    if (nNumbers % k > i) {
        right[i] -= 1;
    }

    max = Math.max(max, findMax2(ar, k, left, right[i]));
}
return max;

What about right?

    int left = (i == 0) ? l : right[i - 1] + 1;
    max = Math.max(max, findMax2(ar, k, left, right[i]));

These are the reads.

    right[i] = left + (nNumbers / k);
    if (nNumbers % k > i) {
        right[i] -= 1;
    }

And these are the writes.

Seems like we're only ever accessing i and i - 1. Do we really need an array, or can we just work with "current" and "previous"?

int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
int max = 0; // maximum value between l and r

/*
 * The left and right indices of the k parts you split the array
 * into. Every split-part contains nNumbers/k >= 1numbers. The
 * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
 */
int previousRight = 0;
for (int i = 0; i < k; i++) {
    /*
     * All left indices are either the left index of the array that
     * is being split (l) or are the index following the right index
     * of the last array-part. All right indices are left index +
     * the size (nNumbers/k) this array-part should have while
     * accounting for the fact that l alone already gives the
     * array-part a size of 1 (-1). 
     */
    int left = (i == 0) ? l : previousRight + 1;
    int currentRight = left + (nNumbers / k);
    if (nNumbers % k > i) {
        currentRight--;
    }

    max = Math.max(max, findMax2(ar, k, left, currentRight));
    previousRight = currentRight;
}
return max;

Yeah, we can. What else can we do? Well... nNumbers doesn't change throughout the loop. And neither does k. So we can cache nNumbers / k. We can also cache nNumbers % k.

final int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
final int cachedNumKDivResult = nNumbers / k;
final int cachedNumKRemainder = nNumbers % k;
int max = 0; // maximum value between l and r

/*
 * The left and right indices of the k parts you split the array
 * into. Every split-part contains nNumbers/k >= 1numbers. The
 * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
 */
int previousRight = 0;
for (int i = 0; i < k; i++) {
    /*
     * All left indices are either the left index of the array that
     * is being split (l) or are the index following the right index
     * of the last array-part. All right indices are left index +
     * the size (nNumbers/k) this array-part should have while
     * accounting for the fact that l alone already gives the
     * array-part a size of 1 (-1). 
     */
    int left = (i == 0) ? l : previousRight + 1;
    int currentRight = left + cachedNumKDivResult;
    if (cachedNumKRemainder > i) {
        currentRight--;
    }

    max = Math.max(max, findMax2(ar, k, left, currentRight));
    previousRight = currentRight;
}
return max;

Hmmh.... left and currentRight ... they're both derived from the same variables...

What if... we set new values for left and right at the END of the for-loop?

final int nNumbers = (r - (l - 1)); // Amount of numbers from l to r
final int cachedNumKDivResult = nNumbers / k;
final int cachedNumKRemainder = nNumbers % k;
int max = 0; // maximum value between l and r

/*
 * The left and right indices of the k parts you split the array
 * into. Every split-part contains nNumbers/k >= 1numbers. The
 * splits 0 to nNumbers%k (excluding nNumbers%k) are larger by 1.
 */
int left = l;
int right = left + cachedNumKDivResult;
for (int i = 0; i < k; i++) {
    /*
     * All left indices are either the left index of the array that
     * is being split (l) or are the index following the right index
     * of the last array-part. All right indices are left index +
     * the size (nNumbers/k) this array-part should have while
     * accounting for the fact that l alone already gives the
     * array-part a size of 1 (-1). 
     */
    if (cachedNumKRemainder > i) {
        right--;
    }

    max = Math.max(max, findMax2(ar, k, left, right));
    left = right + 1;
    right = left + cachedNumKDivResult;
}
return max;

Yeah, that'd work. Now we got rid of previousRight.

I didn't touch your comments. Chances are they don't make sense anymore. I'll be honest, I don't understand the algorithm, and I didn't test this code. All I did was analyse the code statically and rearrange statements. Maybe if you analyse the code you can come up with a more understandable description of the algorithm?

\$\endgroup\$
2
\$\begingroup\$

Interface

First of all, "find the maximum" is open to interpretation. Do you want to find the maximum value, or an index where the maximum value occurs? I would consider the latter to be more useful: with the index, it's easy to look up what the maximum value is, but knowing the maximum value tells you nothing about where it is located.

Not that you should need it in this case, but returning the index also give you a way to return a "not found" error by returning -1. Returning 0 for Base Case 2 (which admittedly should be eliminated altogether) is a bad idea since it assumes that all of the data are nonnegative. The same goes for your int max = 0 initial assumption. You would be better off picking an arbitrary element as the initial maximum.

Second, it is customary in Java to use inclusive-exclusive bounds. That is, l would be the first element being considered, and r would be one position beyond the last element to be considered. Inclusive-exclusive bounds have the pleasant property that r - l gives you the number of elements. You would avoid the -1 in

int nNumbers = (r - (l - 1)); // Amount of numbers from l to r

and in

public static int findMaxHandler(int[] ar, int k) {
    return findMax2(ar, k, 0, ar.length - 1);
}

String.substring(beginIndex, endIndex) is an example of this design principle.

Implementation

Allocating arrays for left and right is unnecessary, if you use an intelligent splitting algorithm. Here, I take the span (r - l) and divide it by k, rounding to the nearest integer. Then, I take the remaining span and divide it by k-1, and the remaining span after that by k-2, and so on.

public static int findMaxIndex(int[] a, int k, int l, int r) {
    assert k > 1;
    if (l >= r) throw new ArrayIndexOutOfBoundsException();

    int maxIndex = l;    // initial assumption
    for (float d = k; d > 0 && (r - l) > 1; d--) {
        int width = Math.round((r - l) / d);
        if (width > 0) {
            int index = findMaxIndex(a, k, r - width, r);
            if (a[index] > a[maxIndex]) {
                maxIndex = index;
            }
            r -= width;
        }
    }
    return maxIndex;
}

Note that I've done a slight optimization by testing (r - l) > 1 rather than (r - l) > 0, because I've already started with the assumption that l is the maximum index.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the pointers on the indices. I'll try to keep that in mind for future pieces of code! But wouldn't calling in the recursion using k-1, then k-2etc reduce the amount of parts you split the array into (which I understood was demanded by the exercise to be kept stable)? And wouldn't the fact that you just got rid of the base case l==r all together (now throws ArrayIndexOutOfBoundsException() instead of returning a value) lead to the code terminating once the base case is reached for the first time? \$\endgroup\$ – Isofruit Apr 8 '17 at 5:42
  • \$\begingroup\$ I would argue that your l == r base case is invalid, since the maximum of a zero-length array is ill defined. Rather, I require at least one element, and I refrain from recursing altogether if a slice has width 0. \$\endgroup\$ – 200_success Apr 8 '17 at 5:56
  • \$\begingroup\$ As for the regularity of the divisions, I do it correctly in spirit, but slightly differently. The strategy is to make each slice as fair as possible at each stage. For the example of a 13-element array with k=3, I split it as 4+5+4 (right-to-left) instead of 5+4+4 as suggested in the exercise. The 5 would be 2+2+1 (the recursive call for the last 1 being optimized out); the 4 would be 1+2+1 (the last 1 being optimized out). \$\endgroup\$ – 200_success Apr 8 '17 at 6:05
  • \$\begingroup\$ Actually, I believe that this algorithm should also produce acceptable results if it used integer division (truncating towards 0) instead of rounding the result of floating-point division to the nearest integer. Let me think about it some more. \$\endgroup\$ – 200_success Apr 8 '17 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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