Quick Summary

This is just a short post that shows a real-life example of why it is often good to view the debug log and check things out in the debugger even when things seem to be working fine.

The Bug

Today I found a very small bug in some code with a very large impact (thankfully in our development environment).

Some Java code was mapping namespace strings to IDs.  It did this by:

• Checking a cache for the mapping.
• Checking the database for the mapping if it didn’t exist in the cache.
• Creating the mapping in the DB if it didn’t exist and putting it into the cache.

This had all been working great… until I refactored it to allow nested namespaces.  Suddenly, the namespace being used in the key wasn’t a string, it was an object!

We were building the cache key explicitly by adding the namespace to the value.  So, the fix was as simple as adding a toString() method to the new namespace class.  Without that, the toString() method had the instance reference, and every single item coming in was therefore unique!

So… effectively we got no caching and had our caches growing rapidly with useless data (the second part of which was somewhat okay as they were LRU caches).

 Finding the Bug

This bug definitely could have been found with unit tests had one been there.  But… one wasn’t. We noticed the bug when a consumer dumped millions of records of data against our environment and pointed out that it was vastly slower than it had been before.

It was still working in a way that got it past our general testing; it was just slower.

Once the consumer pointed this out, I turned on debug logging and immediately saw that every single record was incurring the overhead of 6 database calls, even though this should have stopped after the first thousand records or so triggered data caching.

Sending just one request against my IDE immediately showed that the cache key we were using was garbage as per the reasons noted above.

Lesson Learned!

It immediately occurred to me how silly it is that I no longer had debug logging on in my IDE.  Also, on top of that, it occurred to me how silly it is that I don’t habitually take 30 seconds to watch the new code execute in a debugger just to verify it does what I intended.

Again, unit tests would catch many of these situations… but some standard debug logging and debugger checks can definitely help to significantly limit errors in new code.

Insertion sort is a very simple sorting algorithm. It runs in O(N^2) time, which is not great as most good sorting algorithms run in O(n * lg(n)) time.

It does turn out to be a very useful though in practice because:
– It is quite efficient on small lists.
– It is stable (won’t change the relative position of elements that are the same sort value).
– It is very efficient on mostly sorted lists.
– It requires no additional memory.

The algorithm is very simple if you think about it this way:
– Iterate “i” from index 1 (0 based) to length – 1.
– In a nested loop, move from “i” backward, swapping the element from “i” downward until it is in its proper place.

import java.util.Arrays;

public class InsertionSort {
    public static void sort(int[] a) {
        int i = 1;
        while (i <a> 0 &amp;&amp; a[j-1] &gt; a[j]) {
                int tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                j--;
            }
            ++i;
        }
    }

    public static void main(String[] args) {
        int a[] = new int[] {7, 2, 9, 1, 6, 3, 4, 5, 8};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

Output

[7, 2, 9, 1, 6, 3, 4, 5, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Visualization

Image taken from https://en.wikipedia.org/wiki/Insertion_sort#/media/File:Insertion_sort.gif.

What is a Permutation?

A permutation is a distinct combination of the same set of digits. For example, a permutation of “abc” is “bca”. A common computer problem is finding all possible permutations of a given string of characters. The string “abcd” would have 24 possible permutations to print out, for example.

Calculating Permutation Counts Directly

The number of permutations for a given set of characters is the factorial of the count. For example, “abcd” has 4 characters, so 4! = 4 * 3 * 2 * 1 = 24 permutations.

How Should We Generate Permutations?

You can generate permutations in a number of ways… but I think the easiest one is to use a functional paradigm. This is very similar to the approach we used in the Locker Number No Repeats problem here: https://coding-stream-of-consciousness.com/2018/09/19/locker-number-w-o-repeats/.

The approach is:
– Make a recursive helper method that takes in just the target string of characters.
– Have it call a private recursive method with 2 parameters; a string representing the currently selected characters (will be empty) and a string representing the remaining/unused characters (will be set to the input string) and return the count of the found permutations.
– Make the private recursive method taking the 2 parameters noted earlier.
– If no characters are left in the unused character list, we have a solution; print it. Also, return 1 to count that solution.
– Otherwise, cycle through the remaining characters; ror each, recursively call the function with (1) The current string + the current remaining character and (2) all remaining characters except the current one we are processing.
– Track and return the sum of solutions from all the recursive calls.

Java Implementation

public class FunctionalPermutation {

  //Recursive helper function - gets recursion started.
  public static int permute(String s) {
    if (s == null) return 0;
    return permute("", s);
  }

  private static int permute(String c, String r) {

    //If no letters remain in r, we have a solution.  Print
    //it and return 1 to count it.
    if (r.length() == 0) {
      System.out.println(c);
      return 1;
    }

    //Recurse once for each remaining letter
    //in r, adding each to the current string.
    //Pass all letters but the added one into
    //the recursive call as remaining letters.
    //Also, sum up the number of solutions.
    int sum = 0;
    for (int i = 0; i < r.length(); ++i) {
      sum += permute(c + r.charAt(i), 
        r.substring(0, i) + r.substring(i + 1));
    }
    return sum;
  }

  public static void main(String[] args) {
    System.out.println("Permutation Count: " + permute("abcd"));
  }
}

Output

dbca
dcab
dcba
Permutation Count: 24

A common interview problem for programming is to generate all of the possible locker numbers without repeats.

This is a little silly in the physical world… but the basic idea is:
– You have the numbers 0-9 (so, 10 numbers).
– You can choose any of the 10 for digit 1.
– You can choose any of the remaining 9 for digit 2.
– And the pattern continues.

So, this is a combinations problem… how many ways can you choose N numbers out of 10 numbers?

Calculating it Directly

• Basically, its a limited factorial.
• If N = 4, we have 10 options for #1, 9 for #2, 8 for #3 and 7 for #4 = 10 * 9 * 8 * 7 = 5,040 combinations.

Listing and Counting Them in Java

This problem can be expressed very easily and directly in a functional manner. In this case, that means that we continually build up our solutions immutably, as opposed to, say, trying to keep a character array that we modify as we go.

public class LockerNumberNoRepeats {
    public static void main(String[] args) {
        System.out.println("Total combinations = " +
            permutations(4));
    }

    public static int permutations(int targetLength) {
        return permutations("", "0123456789", targetLength);
    }

    private static int permutations(String c, String r,
            int targetLength) {

        //Print the result if we've reached a full locker
        //combo of the target length.  Also, return 1 so we
        //can sum up all found combinations.
        if (c.length() == targetLength) {
            System.out.println(c);
            return 1;
        }

        //Use sum to count all the permutations we see.  Also
        //cycle through all remaining letters (r) and add each
        //to our current string (c).  Then recursively call this
        //function to continue.
        int sum = 0;
        for (int i = 0; i < r.length(); ++i) {
            sum += permutations(c + r.charAt(i),
                r.substring(0,i) + r.substring(i + 1),
                targetLength);
        }
        return sum;
    }
}

Output

9874
9875
9876
Total combinations = 5040