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();
        }
    }
}

All purpose binary search in PHP

A colleague asked about why there is no binary search method in PHP, but only the slow linear time array_search. I don’t have answer though, but someone suggest that you can do fast searching in a hash by flipping the array into a hash:

<?php
    // DON'T USE THIS FUNCTION, IT IS SLOW
    function flip_search($list, $key) { 
        $res = array_flip($list);
        if (array_key_exists($key, $res)) {
            return $res[$key];
        }       
        return FALSE;
    }
?>

What’s the run time of this function? Linear, as there is no magic in doing the flipping, but has to go through the array entry one by one, and not to mention it is memory inefficient. So if you get a sorted array, use binary search; if your array is not sorted, use the build-in array_search

I set out to write a general binary search for PHP.

<?php
    /*
     * Parameters: 
     *   $a - The sort array.
     *   $first - First index of the array to be searched (inclusive).
     *   $last - Last index of the array to be searched (exclusive).
     *   $key - The key to be searched for.
     *   $compare - A user defined function for comparison. Same definition as the one in usort
     *
     * Return:
     *   index of the search key if found, otherwise return (-insert_index - 1). 
     *   insert_index is the index of smallest element that is greater than $key or sizeof($a) if $key
     *   is larger than all elements in the array.
     */
    function binary_search(array $a, $first, $last, $key, $compare) {
        $lo = $first; 
        $hi = $last - 1;

        while ($lo <= $hi) {
            $mid = (int)(($hi - $lo) / 2) + $lo;
            $cmp = call_user_func($compare, $a[$mid], $key);

            if ($cmp < 0) {
                $lo = $mid + 1;
            } elseif ($cmp > 0) {
                $hi = $mid - 1;
            } else {
                return $mid;
            }
        }
        return -($lo + 1);
    }
?>

To use it is pretty straight forward:

<?php
    function cmp($a, $b) {
        return ($a < $b) ? -1 : (($a > $b) ? 1 : 0);
    }

    $a = array(1,2,3,4,5,6);
    $idx = binary_search($a, 0, sizeof($a), 4, 'cmp');
?>

Feel free to use the code if you need it.

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;
}