Pages

A thread-safe DateFormatter via ThreadLocal

The exercise 2-b at the end of chapter two from the book Java 8 Lambdas by Richard Warburton asks to wrap a DateFormatter in a ThreadLocal so to make it thread safe.

We have spotted in legacy code, designed to work in a single thread context, something like:
DateFormatter formatter = // ...

// ...

Calendar cal = Calendar.getInstance();
cal.set(Calendar.YEAR, 1970);
cal.set(Calendar.MONTH, Calendar.JANUARY);
cal.set(Calendar.DAY_OF_MONTH, 1);
String formatted = formatter.getFormat().format(cal.getTime());
We know that DateFormatter, a Swing class used to format java util Date, is non thread safe. And now we plan to use this code in a multithreaded environment. We need to refactor it.

If we need to stick to the DateFormatter, here is a possible solution:
ThreadLocal<DateFormatter> formatter =  // 1
    ThreadLocal.withInitial(  // 2
        () -> new DateFormatter(  // 3
            new SimpleDateFormat("dd-MMM-yyyy", Locale.ENGLISH)));  // 4
1. Wrapping an instance of it in a ThreadLocal saves our day, since each thread has its own copy of the variable.
2. Since Java 8, the withInitial() static method let us create a ThreadLocal passing a Supplier that is going to be used to initialize the object.
3. That's the Supplier. Nothing is passed in, and it returns a new DateFormatter.
4. The DateFormatter will be constructed from this SimpleDateFormat built on the fly specifying the format as a string. Notice the second parameter, I want the dates to be localized in English whichever is the default locale.

Job done. Still it would be nice to ...

Switch to java.time

The classes in java.time have been designed for working correctly in multithreading. So, getting rid of Calendar and DateFormatter for LocalDate and DateTimeFormatter, would lead to code simpler and more robust, like this:
DateTimeFormatter formatter8 = DateTimeFormatter.ofPattern("dd-MMM-yyyy", Locale.ENGLISH);
// ...

LocalDate aDate = LocalDate.of(1970, 1, 1);
String formatted = formatter8.format(aDate);
I have pushed the above Java code in my GitHub repository forked from the one gently provided by the author.
Follow the links to see the Question2 solution and its test case.

Go to the full post

HackerRank Java Dequeue

Given n integers in input, consider each window in it sized m, where m is less or equal to n, and get the number of unique elements in each window. Return the maximum value among them.

This HackerRank Java Challenges problem is named Java Dequeue, a clear hint that a Deque would helpful to solve it elegantly.

The HackerRank settings implies that data are passed us by System.in. To develop a method that could be easily tested, I made it accept an InputStream as parameter, then I passed it through a Scanner, in its own try-with-resource block.
public static int solution(InputStream is) {
    try (Scanner scanner = new Scanner(is)) {
        // ... see below
    }
}
The first two integers we expect in the input stream are the above described n and m. A problem constrain states that m is not bigger than n, I make it clear in the code with an assertion.
int n = scanner.nextInt();
int m = scanner.nextInt();
assert m <= n;
Now I should be ready to get the next n integers and work on them. The big hint in the problem name suggests to push them in a Deque. Actually, we are going to use it as a queue. Since ArrayDeque is documented as "likely to be ... faster than LinkedList when used as a queue", my choice goes for it. To avoid slowdowns due to possible resizings, I create it specifying its capacity to the maximum "m" specified by the problem.

We also need to count the items in each window, and to do that a second container is useful. We'll push any item entering the window in a hash table, storing as value its current count. When an item exits the window we decrease its count in the hash. If the count is zero, we remove it.

We are going to call our method many times in a row, and I don't want to create each time a new deque and hash. It is cheaper to make them class data member, and simply reset them any time the method is called.
public class Solution {
    private static final int MAX_WINDOW_SIZE = 100_000;

    private static Deque<Integer> window = new ArrayDeque<>(MAX_WINDOW_SIZE);
    private static Map<Integer, Integer> counter = new HashMap<>();

    public static int solution(InputStream is) {
        // ... see above

        window.clear();            
        counter.clear();
        
        // ... see below
    }
}
Let's fill up the window for the first time. The hash map 'counter' is set up as described above.
for (int i = 0; i < m; i++) {
    int in = scanner.nextInt();
    window.add(in);
    counter.merge(in, 1, Integer::sum);
}

int result = counter.size();

// ... see below
To count how many different integers are in the current window, I simply check the size of the hash map.

Now it is just a matter of iterating on all the other integer in the input stream.
for (int i = m; i < n && result < m; i++) {
    Integer out = window.remove();
    Integer in = scanner.nextInt();
    window.add(in);

    // ... see below
}

return result;
I have started looping on the m-th item, willing to go up to the n-th. But, wait, if I find a window with all different numbers (meaning, the current result is already equal to "m") I have already found the problem solution. That could save some CPU time.

In the loop, firstly I adjust the window, removing its first element and adding a new last element. The exiting and entering elements are used to modify the counter map. Then I recalculate the result, and I check it against the current solution.
if (out.intValue() != in.intValue()) { // 1
    counter.merge(in, 1, Integer::sum);  // 2
    counter.merge(out, -1, (a, b) -> a == 1 ? null : a + b); // 3
    result = Math.max(result, counter.size()); // 4
}
1. If what enters in the window is the same of what exists from it, I don't have to do anything.
2. I merge the item 'in' in the map. That means, if the map contains 'in', Integer::sum is used to adjust its value (on its current value and the '1' I passed in). Otherwise a new item is created in the map, key 'in', value '1'.
3. Similarly to the previous line, but now I'm performing a sort of 'merge down'. I'm not satisfied by this line I wrote, even though it is kind of fun. Its point is that we know for sure that 'out' is in the map, so we know that we are going to execute the lambda passed to merge(). It would return null if the value associated to 'out' is 1, removing it. Otherwise it would return a + b, but b is set to -1, so it would decrease it. The weak spot is, what if for 'out' is not in the map? Well, merge() would push it in, with value -1. Damn it. There is no way to avoid this inconsistency, since merge() would throw an exception if null is passed as value. End of the story is, I would not use this line in production code.
4. Maybe this check-and-set looks a bit too pythonic, what do you think about it?

Full Java code and test case available on GitHub.

Go to the full post