3
\$\begingroup\$

This is not a "please do my homework" question. I solved a problem two ways and would like to know which solution is better; better being defined by better readability, lower complexity and lower memory consumption. I'd also like to note that this is a not a homework assignment but an optional no-credit practice problem.

My CS class offers practice problems through their site. One specific question is named "removeShorterStrings." The prompt being:

Write a method removeShorterStrings that takes an ArrayList of Strings as a parameter and that removes from each successive pair of values the shorter string in the pair. For example, suppose that an ArrayList called list contains the following values: {"four", "score", "and", "seven", "years", "ago"} In the first pair, "four" and "score", the shorter string is "four". In the second pair, "and" and "seven", the shorter string is "and". In the third pair, "years" and "ago", the shorter string is "ago". Therefore, the call: removeShorterStrings(list); should remove these shorter strings, leaving the list as follows: "score", "seven", "years". If there is a tie (both strings have the same length), your method should remove the first string in the pair. If there is an odd number of strings in the list, the final value should be kept in the list.

I have come up with the following solutions:

The "ask for permission" solution:

void removeShorterStrings(ArrayList<String> list) {
    if (list.size() != 0) {
        int isOdd = (list.size() >> 0) & 1;
        for (int i = 0; i <= (list.size() >> 1) - isOdd; i++) {
            String first = list.get(i);
            String second = list.get(i + 1);
            if (first.length() <= second.length()) {
                list.remove(i);
            } else {
                list.remove(i + 1);
            }
        }
    }
}

and the "ask for forgiveness" solution:

void removeShorterStrings(ArrayList<String> list) {
    for (int i = 0; i <= (list.size() >> 1); i++) {
        try {
            String first = list.get(i);
            String second = list.get(i + 1);
            if (first.length() <= second.length()) {
                list.remove(i);
            } else {
                list.remove(i + 1);
            }
        } catch (IndexOutOfBoundsException e) {
            break;
        }
    }
}

I come from a JavaScript/python background, so I'm unsure of what is considered "good practice" in java.

TL;DR: Which solution is better in terms of better readability, lower complexity and lower memory consumption?

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

Asking for forgiveness would be the best policy for dealing with errors that may be beyond your control, such as when opening a file for reading. Checking beforehand is useless, because too many things could go wrong: the file might not exist, you might not have the right permissions, the disk could fail altogether, etc. Furthermore, even if you did check beforehand, circumstances could change during the brief period between your check and the real operation. Therefore, the only reasonable approach would be to just do it, and deal with any errors that come up.

When working with a list of words, however, the outcome is entirely deterministic. Since it is entirely possible to write your code such that it never triggers an error, that's what you should aim for. (Well, maybe the program is multithreaded, and some other thread is manipulating the ArrayList behind your back, but that would be your program's fault, and such errors are also preventable with proper engineering.)

Therefore, your first approach is better. However, the list.size() != 0 check is a superfluous check, and list.size() >> 0 is a pointless shift.

Personally, I find the indexing confusing, because the list is being modified as you traverse it, and the termination condition (list.size() >> 1) - isOdd is a moving target. Consider working backwards, so that each pair you consider is always in "virgin" territory.

public static void removeShorterStrings(ArrayList<String> list) {
    for (int i = (list.size() & ~1) - 2; i >= 0; i -= 2) {
        String first = list.get(i);
        String second = list.get(i + 1);
        if (first.length() <= second.length()) {
            list.remove(i);
        } else {
            list.remove(i + 1);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I see that you did (list.size() & ~1) - 2, can you explain or point me in a resource that explains what that does? Are you essentially ANDing the size and 11111...0 then subtracting 2? Why does that work? As for the pointless shifts, you're right. I forgot to remove that when tinkering around. \$\endgroup\$ – npengra317 Sep 28 '18 at 1:15
  • \$\begingroup\$ @npengra317 That's right. ~ 1 has all bits set to 1, except the rightmost bit is 0. & ~1 forces the least-significant bit to 0, essentially rounding down to the nearest even number. \$\endgroup\$ – 200_success Sep 28 '18 at 1:38
  • \$\begingroup\$ What a nifty trick. Thank you for your response. \$\endgroup\$ – npengra317 Sep 28 '18 at 2:00
  • \$\begingroup\$ Addressing your edit: I understand that moving targets are tricky and are prone to lots of mistakes, but if done correctly, is moving backwards still preferable to moving forwards (in this scenario)? \$\endgroup\$ – npengra317 Sep 28 '18 at 4:33
  • \$\begingroup\$ Not only is it less confusing, in my opinion, to work backwards, it is more efficient to compare with 0 (just one opcode) than to recalculate the termination index every time through the loop. \$\endgroup\$ – 200_success Sep 28 '18 at 4:36

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.