0 1 knapsack Java Code

     /**
     *
     * @param w weight for items
     * @param v values for items
     * @param i number of items
     * @param W the max weight
     * @return what knapsack/0-1 should return
     */
    static int knapsack(int[]w, int []v, int i, int W){
        if(i < 0) return 0;         if(w[i] > W){
            return knapsack(w,v, i-1, W);
        }else {
            return Math.max(knapsack(w,v, i-1, W), knapsack(w,v, i-1, W-w[i])+ v[i] );
        }
    }

Throttling web service / application

There are different throttling techniques one can use to throttle a network applications, Following are some well established and simple techniques used in different network applications.

Out of which Token Bucket suits very well for Web Services with the following reasoning,

  • Failing fast on the incoming requests because there is no tokens available. That helps the caller to strategize immediately what to do in case of running out of limits.
  • Failing fast also helps in not building a log task queue at the callers side.
  • New milk is better than old milk (milk and wine policy) because keeping an old request with no relevance to the caller is just waste of resources if relevance is what you care about.

In my coming post I shall implement a simple throttler that uses the Token Bucket algorithm in Java.

Least Recently Used or LRU Cache : a simple implementation in Java

A friend of mine asked me about LRU cache and while explaining the same I could not locate a simple implementation one by just googling it.

The Java util provides a beautiful implementation through LinkedHashMap. Which is a Hash table and linked list implementation of the Map interface, with predictable iteration order. In order to use it as an LRU cache, do the following,

  • use constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and set the accessOrder to true. and,
  • override the implementation for removeEldestEntry(Map.Entry eldest)
  • please keep in mind that this is NOT an thread safe implementation and to have thread safety for this LinkedHashMap, you can do something like Map m = Collections.synchronizedMap(new LinkedHashMap(…)), if multiple threads may use the map.

You can of-course look at the implementation of LinkedHashMap for reference and it is really awesome how implemented but I thought to write up my own implementation for LRU cache using a HashMap and a linked list with minimal functionality. So this implementation provides a LRU cache implementation in Java using Hashmap and a doubly linked list.

package com.das.yadab.java;

import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {
    public static final int MAX_SIZE = 100; // Default max size for the cache to grow.
    private Entry<K, V> head;
    private HashMap<K, Entry> internalCache;
    private int maxSize;

    public LRUCache() {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        maxSize = MAX_SIZE;
    }

    public LRUCache(int maxSize) {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        this.maxSize = maxSize;
    }

    /**
     * Gets value associated with the specified key from cache.
     *
     * @param key
     * @return value or null if not found
     */
    public V get(Object key) {
        Entry<K, V> e = internalCache.get(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

    /**
     * Associates key and value in the cache, null value is not allowed.
     * If cache size has grown more than the allowed capacity the eldest member will be evicted.
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        if (value == null) {
            throw (new IllegalArgumentException("Null Value association is not helpful in caching"));
        }
        if (shouldRemoveEldestEntry()) {
            Entry eldest = head.after;
            removeEntry(eldest);
        }
        Entry entry = new Entry(key, value);
        if (!internalCache.containsKey(key)) {
            entry.addBefore(head);
        }
        internalCache.put(key, entry);
        return value;
    }

    private void removeEntry(Entry eldest) {
        // since we do not allow null value association so this is safe.
        if (internalCache.remove(eldest.key) != null) {
            eldest.recordRemoval(this);
        }
    }

    /*
    Returns true if this map should remove its eldest entry.
    if maxSize is not set during initialization the method will always return false.
     */
    public boolean shouldRemoveEldestEntry() {
        if (internalCache.size() > maxSize) {
            return true;
        }
        return false;
    }

    static class Entry<K, V> implements Map.Entry<K, V> {
        private Entry<K, V> before, after;
        private K key;
        private V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        private void addBefore(Entry<K, V> existingEntry) {
            after = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(LRUCache<K, V> cache) {
            remove();
            addBefore(cache.head);
        }

        final void recordRemoval(LRUCache<K, V> m) {
            remove();
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return (key == null ? 0 : key.hashCode()) ^
                    (value == null ? 0 : value.hashCode());
        }

        @Override
        public String toString() {
            return "Entry key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "internalCache=" + internalCache +
                ", head=" + head +
                ", maxSize=" + maxSize +
                '}';
    }
}

An example usage, since it only accesses the key “0”, it should retain the key “0” though it is added at the beginning.

LRUCache cache = new LRUCache(5);
for (int i = 0; i &lt; 10; i++) {
    cache.put(Integer.toString(i), i);
    cache.get(Integer.toString(0));
}

Java : difference between Polymorphism and Inheritance

Since the definition for both them have some common ground so it may confuse some times with the differences between this two paradigm. Definitions from wiki, you might have already read it.

  • Polymorphism polymorphism is the provision of a single interface to entities of different types. Java supports basically subtype(using inheritance in Java) and parametric polymorphism (using generics in Java).
  • Inheritance (OOP) is when an object or class is based on another object (prototypal inheritance) or class (class-based inheritance), using the same implementation (inheriting from an object or class) specifying implementation to maintain the same behavior (realizing an interface; inheriting behavior).

So from the above definition,

  1. Inheritance or subclassing in Java is one of the technique used to achieve polymorphism.
  2. Inheritance refers to using the structure and behavior of a superclass in a subclass.
  3. Inheritance helps code reuse at the same time while achieving polymorphism.

Java : Asynchronous Task sequencing using Observer pattern

The other day I was answering a question on stackoverflow on what could be a simple implementation of sequencing or ordering asynchronous tasks in Java. More detail about the question. Basically task sequencing problem is, you have a list of tasks say : {A, B, C, D} and you want execute them in some order, say {A} -> {B, C} ->{D} ->{X} -> {A}.

I preferred the Observer pattern because it is more of a reactive pattern so that design is reactive in nature rather than controlling and more loosely coupled.

public abstract class Task extends Observable implements Runnable, Observer {
    private final Mutex lock = new Mutex();
    private final String taskId;
    private final Set<String> completedTasks;
    private final Set<String> shouldCompletedTasksBeforeStart;

    public Task(final String taskId) {
        this.taskId = taskId;
        this.completedTasks = new HashSet<>();
        this.shouldCompletedTasksBeforeStart = new HashSet<>();
    }

    public String getTaskId() {
        return this.taskId;
    }

    @Override
    public void run() {
        while (true) {
            this.lock.getLock();
            if (this.completedTasks.equals(this.shouldCompletedTasksBeforeStart)) {
                doWork();
                setChanged();
                notifyObservers(this.taskId);
                // reset
                this.completedTasks.clear();
            }
            this.lock.freeLock();
            try {
                // just some sleep, you change to how it fits you
                Thread.sleep(1000);
            } catch (final InterruptedException e) {
                // TODO Auto-generated catch block
            }
        }
    }

    @Override
    public void update(final Observable observable, final Object arg) {
        this.lock.getLock();
        this.completedTasks.add((String) arg);
        this.lock.freeLock();
    }

    public void addPredecessorTask(final Task task) {
        if (this.taskId.equals(task.taskId)) {
            return;
        }
        this.lock.getLock();
        // Notice here, it is a little logic make your predecessor/successor work
        task.addObserver(this);
        this.shouldCompletedTasksBeforeStart.add(task.taskId);
        this.lock.freeLock();
    }
    protected abstract void doWork();
}

//HelloTask.java
public static class HelloTask extends Task {
    public HelloTask(final String taskId) {
        super(taskId);
    }

    @Override
    protected void doWork() {
        System.out.println("Hello from " + getTaskId() + "!");
    }
}

//Main.java
public class Main {
    public static void main(final String[] args) {
        final HelloTask helloTaskA = new HelloTask("A");
        final HelloTask helloTaskB = new HelloTask("B");
        final HelloTask helloTaskC = new HelloTask("C");

        helloTaskA.addPredecessorTask(helloTaskB);
        helloTaskC.addPredecessorTask(helloTaskB);

        final ExecutorService pool = Executors.newFixedThreadPool(10);
        pool.execute(helloTaskC);
        pool.execute(helloTaskA);
        pool.execute(helloTaskB);

    }
}

Artificial Brain and cryptanalysis

Was reading about different Blue brain or Artificial brain projects and thought of writing a simple network myself. So all I could afford myself is one compute machine from amazon which allows to run 3000 threads only if I am not doing much in each neuron. Each thread is a neuron and after adding little logic of filtering I came down to much lower number. I felt like, what am I doing, so to simulate this in cloud framework, I need the following,

  • A good messaging platform
  • A very lightweight service framework to make it work as neuron

And to able to use this network for doing a cryptanalysis is not far but the brain I produced is a size of an ant or less. I need bigger brain means a lot of machines => a lot of money ??

2.11 years without a post

I like writing about what I am thinking but somehow I have stopped for past 2.11 years after I changed my job. I did not do well though to put an excuse for not writing so I am going to write about many interesting things I found along the way and about my new research on dimensions “From 3 to 2 or 3 to 4

Follow

Get every new post delivered to your Inbox.