Executor that maintains execution order by group

I need a class that helps me to run set of tasks in the same order of submission (like serialized execution). Yet I don’t want to use a single-thread executor as I have a large collection of different set of tasks that tasks from different set can be run in parallel. If I use one single-thread executor, it loses efficiency that tasks from different sets no longer be run in parallel. If I use one single-thread executor per task set, then I’ll end up with lots of threads, which is not ideal.

Out of necessity, I created the following class, OrderedExecutor.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.Executor;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * An executor that make sure tasks submitted with the same key
 * will be executed in the same order as task submission
 * (order of calling the {@link #submit(Object, Runnable)} method).
 *
 * Tasks submitted will be run in the given {@link Executor}.
 * There is no restriction on how many threads in the given {@link Executor}
 * needs to have (it can be single thread executor as well as a cached thread pool).
 *
 * If there are more than one thread in the given {@link Executor}, tasks
 * submitted with different keys may be executed in parallel, but never
 * for tasks submitted with the same key.
 * 
 * * @param <K> type of keys.
 */
public class OrderedExecutor<K> {

    private final Executor executor;
    private final Map<K, Task> tasks;

    /**
     * Constructs a {@code OrderedExecutor}.
     *
     * @param executor tasks will be run in this executor.
     */
    public OrderedExecutor(Executor executor) {
        this.executor = executor;
        this.tasks = new HashMap<K, Task>();
    }

    /**
     * Adds a new task to run for the given key.
     *
     * @param key the key for applying tasks ordering.
     * @param runnable the task to run.
     */
    public synchronized void submit(K key, Runnable runnable) {
        Task task = tasks.get(key);
        if (task == null) {
            task = new Task();
            tasks.put(key, task);
        }
        task.add(runnable);
    }

    /**
     * Private inner class for running tasks for each key.
     * Each key submitted will have one instance of this class.
     */
    private class Task implements Runnable {

        private final Lock lock;
        private final Queue<Runnable> queue;

        Task() {
            this.lock = new ReentrantLock();
            this.queue = new LinkedList<Runnable>();
        }

        public void add(Runnable runnable) {
            boolean runTask;
            lock.lock();
            try {
                // Run only if no job is running.
                runTask = queue.isEmpty();
                queue.offer(runnable);
            } finally {
                lock.unlock();
            }
            if (runTask) {
                executor.execute(this);
            }
        }

        @Override
        public void run() {
            // Pick a task to run.
            Runnable runnable;
            lock.lock();
            try {
                runnable = queue.peek();
            } finally {
                lock.unlock();
            }
            try {
                runnable.run();
            } catch (Exception ex) {
                ex.printStackTrace();
            }
            // Check to see if there are queued task, if yes, submit for execution.
            lock.lock();
            try {
                queue.poll();
                if (!queue.isEmpty()) {
                    executor.execute(this);
                }
            } finally {
                lock.unlock();
            }
        }
    }
}

Please feel free to use it if you find yourself in the same situation as me.

Efficient data structure for finding median

Just come up with a relatively simple implementation for a data structure that can report median value in constant time, and insertion/remove median in O(log(n)) time. It uses a max heap and min heap to store elements that are smaller and larger then the median respectively, and maintains the property that the differences between the two heaps are always less than or equal to 1.

Feel free to use/enhance/comment it.

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Data structure for storing collection of elements which can report
 * median in constant time, while {@linkplain FastMedian#add(java.lang.Object) adding} 
 * new element and {@linkplain FastMedian#removeMedian() remove median} takes O(log(n)) time. 
 * If there are even number of elements, it always
 * uses the smaller of the two median numbers as the median value.
 */
public class FastMedian<T> {
    private final Comparator<? super T> comparator;
    private final Queue<T> maxHeap;
    private final Queue<T> minHeap;
    private T median;

    /**
     * Creates a {@code FastMedian} which order elements according to their
     * {@linkplain Comparable natural ordering}.
     */
    public FastMedian() {
        this(null);
    }

    /**
     * Creates a {@code FastMedian} which order elements according to the given
     * {@link Comparator}.
     * 
     * @param comparator the comparator for ordering elements. If {@code null},
     *        the {@linkplain Comparable natural ordering} will be used.
     */
    public FastMedian(Comparator<? super T> comparator) {
        this.comparator = comparator;
        if (comparator == null) {
            this.maxHeap = new PriorityQueue<T>(11, Collections.reverseOrder());
            this.minHeap = new PriorityQueue<T>();
        } else {
            this.maxHeap = new PriorityQueue<T>(11, Collections.reverseOrder(comparator));
            this.minHeap = new PriorityQueue<T>(11, comparator);
        }
    }

    /**
     * Inserts the given element.
     *
     * @param e the element to add.
     */
    public void add(T e) {
        if (median == null) {
            median = e;
            return;
        }
        int cmp = (comparator == null) ? (((Comparable<? super T>) e).compareTo(median)) : comparator.compare(e, median);
        if (cmp < 0) {
            maxHeap.add(e);
        } else {
            minHeap.add(e);
        }
        // Rebalance
        int sizeDiff = maxHeap.size() - minHeap.size();
        if (sizeDiff > 0) {
            minHeap.add(median);
            median = maxHeap.remove();
        } else if (sizeDiff < -1) {
            maxHeap.add(median);
            median = minHeap.remove();
        }
    }

    /**
     * Returns the current median value.
     *
     * @return current median value.
     */
    public T getMedian() {
        return median;
    }

    /**
     * Removes the current median and returns it.
     *
     * @return value of the median removed.
     */
    public T removeMedian() {
        T result = median;
        if (maxHeap.isEmpty() && minHeap.isEmpty()) {
            median = null;
            return result;
        }
        if (maxHeap.size() >= minHeap.size()) {
            median = maxHeap.remove();
        } else {
            median = minHeap.remove();
        }
        return result;
    }    
}

A very simple example on using it:


import java.util.TreeSet;

public class MedianTest {
    
    public void test() {
        TreeSet<Integer> numbers = new TreeSet<Integer>();
        FastMedian<Integer> fastMedian = new FastMedian<Integer>();
        
        for (int i = 1; i < 10; i += 2) {
            numbers.add(i);
            fastMedian.add(i);
            System.out.println(numbers + " median: " + fastMedian.getMedian());
        }
        
        for (int i = 10; i >= 2; i -= 2) {
            numbers.add(i);
            fastMedian.add(i);
            System.out.println(numbers + " median: " + fastMedian.getMedian());
        }
        
        System.out.println();

        Integer median = fastMedian.removeMedian();
        while (median != null) {
            numbers.remove(median);
            System.out.println(numbers + " removed: " + median + " new median: " + fastMedian.getMedian());
            median = fastMedian.removeMedian();
        }
    }
}

Checks for whitespaces only string

Someone tries to have a method in Java that checks if a string contains only whitespace characters, and ended up with an implementation like this:

boolean isWhitespaceOnly(String str) {
    // DON'T DO THIS, EXPLAINED BELOW
    return str.trim().equals("");
}

So, what’s wrong with it?

  1. The trim() method will create a new String instance (only exception is an empty string or the first and last characters are not whitespaces. Check Java API doc.).
  2. Always use isEmpty() rather than .equals("") to check if a string is empty, as it is always faster.

In fact we should just inspect characters in the string and return true when we only see whitespaces. It would be faster (as we can terminate whenever we see a non-whitespace) and no new instance being created.

boolean isWhitespaceOnly(String str) {
    int pos = str.length() - 1;
    while (pos >= 0 && str.charAt(pos) <= ' ') {   // checking of <= ' ' is the same contract as the trim() does
        pos--;
    }        
    return pos < 0;
}

Stupid programming II

I came across a segment of Java code like this during a code review:

String str = "" + 10;

Sometimes I really don’t know what’s in people head. Isn’t it a lot more simpler/clearer/better/faster to do it as:

String str = "10";

If it is up to me, we should banish people writing code like this to write single line of code again.

Maximum sum sub-array

Here is a slightly more complicated one:

Q. Given an integer array containing N positive and negative numbers, find the sub-array having the largest sum in linear time O(N) using constant space O(1).

Want some hint?

 You need to keep track of both the maximum sum so far and the maximum sum for including an element. 

My solution (in Java):

    int[] largestSum(int... a) {
        int start = 0, end = -1, curstart = 0, last = 0, sum = Integer.MIN_VALUE;

        for (int i = 0;i < a.length; i++) {
            last += a[i];
            sum = Math.max(last, sum);

            if (sum == last) {
                start = curstart;
                end = i;
            }
            if (last < 0) {
                last = 0;
                curstart = i + 1;
            }
        }
        return Arrays.copyOfRange(a, start, end + 1);
    }

Multiplies all except itself

That’s another simple algorithmic challenge.

Q. Given an array of integers A of size N > 1, produce an output array B of size N with B[i] = A[1]*A[2]…*A[i – 1]*A[i + 1]…*A[N], that is multiplies all elements in A except A[i] itself. Do it in linear time O(N) without using division.

Please think about it first before looking at my answer and I hope there is a better one than mine.

My solution (written in Java):

void mul(int[] a, int[] b) {
    // Compute b[i] = a[0]a[1]...a[i]
    b[0] = a[0];
    for (int i = 1; i < a.length; i++) {
        b[i] = b[i - 1] * a[i];
    }
    // Compute result, with v = a[n - 1]a[n - 2]...a[i] after loop i
    int v = 1;
    for (int i = a.length - 1; i > 0; i--) {
        b[i] = b[i - 1] * v;
        v *= a[i];
    }
    b[0] = v;
}

Detect duplicates

Trying to start a new category to archive some algorithmic problems that I come across. Let’s start with a very simple one.

Q. Given an array of N elements in which each element is an integer between 1 and N, detect if there are any duplicates in linear time O(n) and constant space O(1).

Please think about it being looking at my code.

My solution (in Java):

// If we are allowed to modify the array, it can be as simple as the following.
boolean detectDup(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int d = Math.abs(a[i]) - 1;
        if (a[d] < 0) {
            return true;
        }
        a[d] = -a[d];
    }
    return false;
}