Wednesday 27 December 2017

Algorithms | Interpolation Search: Beating Binary Search

Interpolation search is an algorithm to search given key in a uniformly distributed sorted array. It is an improvement over Binary Search when the keys are uniformly distributed in a sorted array.

Binary search always chooses the middle element for comparison, discarding one half of the search space or the other. However, Interpolation search tries to predict where the key would lie in the search space via a linear interpolation, reducing the search space to the part before or after the estimated position if the key is not found there.

A linear interpolation of values, 'key' should be found at position:

pos = low + [(key - array[low]) * (high-low) / (array[high]-array[low])]

here,
array[]: Array where keys are stored.
key: Key to be searched
low: Starting index in array[]
high: Ending index in array[]

Algorithm
It works same as Binary search except above interpolation logic.

1. Calculate the value of "pos" using the linear interpolation formula.
2. if it is a match, return the position of the item, and exit.
3. if the key < array[pos]
     3.a. Calculate the linear interpolation of the left sub-array.
Otherwise,
     3.b. Calculate the linear interpolation in the right sub-array.
4. Repeat until a match is found or the sub-array reduces to zero.

Pseudo Code
int interpolationSearch(int[] array, int x) {
    int low = 0;
    int high = array.length - 1;
    int pos;

    while ((array[high] != array[low]) && (x >= array[low]) && (x <= array[high])) {
        pos = low + ((x - array[low]) * (high - low) / (array[high] - array[low]));

        if (array[pos] < x) {
            low = pos + 1;
        } else if (x < array[pos]) {
            high = pos - 1;
        } else {
            return pos;
        }
    }

    if (x == array[low]) {
        return low;
    } else {
        return -1;
    }
}

Complexity
This approach works faster than Binary search when the keys are uniformly distributed. Average case complexity of interpolation search is O(log log N) if the keys are uniformly distributed, where N is the number of keys.

However, the worst case complexity is O(N) e.g., searching for 1000 in 1, 2, 3, …, 999, 1000, 10^9.

Tuesday 26 December 2017

Design Patterns | Singleton using enum: Enforce the singleton property with a private constructor or an enum type

A singleton is simply a class that is instantiated exactly once.

Before release 1.5, there were two ways to implement singletons. Both are based on keeping the constructor private and exporting a public static member to provide access to the sole instance.

In one approach, the member is a final field:

/** Singleton with static initialization using a public static final variable. */
public class Singleton {
     public static final Singleton INSTANCEnew Singleton();
     private Singleton() { ... }
}

The private constructor is called only once, to initialize the public static final field Singleton.INSTANCE. Singleton instance will exist once the Singleton class is initialized.

However, a privileged client can invoke the private constructor using reflection by the AccessibleObject.setAccessible method.

/** Singleton with the static factory. */
public class Singleton {
     private static final Singleton INSTANCE = new Singleton();
     private Singleton() { ... }
     public static Singleton getInstance() {
          return INSTANCE;
     }
}

To make a singleton class that is implemented using either of the previous approaches serializable, it is not sufficient merely to add implements Serializable to its declaration.

Each time a serialized instance is deserialized, a new instance will be created. To maintain the singleton guarantee, we need to declare all instance fields transient and provide a readResolve method.

/** readResolve method to preserve singleton property while serialization. */
private Object readResolve() {
     /** Return the one true Singleton and let the garbage collector
      *  take care of the Singleton impersonator.
      */
     return INSTANCE;
}

Singleton using enum
As of release 1.5, there is a third approach to implementing singletons. This approach is functionally equivalent to the public field approach, except that it is more concise, provides the serialization machinery for free, and provides the guarantee against multiple instantiations, even in the face of sophisticated serialization or reflection attacks.

Enum is thread-safe which helps us to avoid double checking (less code for better results).

While this approach has yet to be widely adopted, a single-element enum type is the best way to implement a singleton.

public enum Singleton {
     INSTANCE;
     public void doStuff(){
           System.out.println("Singleton using Enum");
     }
}

/** This is the way to call the Singleton. */
public static void main(String[] args) {
     Singleton.INSTANCE.doStuff();
}


Design Patterns | Singleton design pattern

The singleton pattern is a software design pattern which restricts the instantiation of a class to one object. This is useful when exactly one instance of a class is needed to coordinate actions across the system. For an example, a single DB connection shared by multiple objects as creating a separate DB connection for every object may be costly. The term comes from the mathematical concept of a singleton.

Definition
The singleton pattern is a design pattern that ensures at most one instance of a particular class is ever created in the application.

More examples of the Singleton
Project Configuration
The class that reads project configuration should be made Singleton by reads once and holds on application Cache and global access to all classes in the application.

Application Log
Logger must be initialized once and can be used everywhere in the application.

Analytics and Reporting
If you are using some kind of data analysis tool like Google Analytics, you will notice that they are designed to be a singleton. It initializes once and being used everywhere for each user action.

How to achieve Singleton property
1. Hide the constructor of the class (make the constructor private).
2. Define a public static operation (getInstance()) that returns the sole instance of the class.

/**
 * Basic singleton design pattern implementation in Java
 * @author rajesh.dixit
 */
class Singleton {

     private static Singleton INSTANCE;

     /** 1. Hide the constructor. */
     private Singleton() {

     }

     /**
      * Returns the sole instance of the class.
      * @return instance of the class
      */
     public static Singleton getInstance() {
           if (INSTANCE == null) {
                INSTANCE = new Singleton();
           }
           return INSTANCE;
     }
}

Singleton and Thread Safety
Two instances of Singleton class will be created if the getInstance() called simultaneously by two threads. We can make the make getInstance() method synchronized to ensure that no two threads can be entered into getInstance() method at the same time.

public static synchronized Singleton getInstance() {
     /* Lazy initialization, creating object on first use */
     if (INSTANCE == null) {
           synchronized (Singleton.class) {
                if (INSTANCE == null) {
                     INSTANCE = new Singleton();
                }
          }
     }
     return INSTANCE;
}

Singleton and Early Initialization
Using early initialization we will initialize upfront before our class is being loaded. This way we don’t need to check for synchronization as it is initialized before being used ever.

class Singleton {

     private static Singleton INSTANCE = new Singleton();

     private Singleton() {

     }

     /**
      * Returns the sole instance of the class.
      * @return instance of the class
      */
     public static Singleton getInstance() {
           return INSTANCE;
     }
}

Singleton and Object Cloning
Cloning is used to create a copy of the object at any instance original object by implementing java.lang.Cloneable interface and override clone() method from Object class.

To prevent cloning on singleton object, throw CloneNotSupportedException exception explicitly from the clone() method.

Singleton and Serialization
Java Serialization allows converting the state of an object into the stream of bytes to store or transfer. Deserialization used to convert byte stream into. If a singleton class desterilized, it will end up creating duplicate objects.

To resolve this issue, we need to include readResolve() method in our class which will be invoked before the object is de-serialized. We will return INSTANCE from readResolve() which will ensure a single instance of the Singleton class exists in the application.

import java.io.Serializable;

class Singleton implements Cloneable, Serializable {

    private static final long serialVersionUID = 1L;

    private static volatile Singleton INSTANCE;
    private int value;

    /** Private Constructor prevents any other class from instantiating. */
    private Singleton() {
    }

    public static synchronized Singleton getInstance() {
        /* Lazy initialization, creating object on first use */
        if (INSTANCE == null) {
            synchronized (Singleton.class) {
                if (INSTANCE == null) {
                    INSTANCE = new Singleton();
                }
            }
        }
        return INSTANCE;
    }

    /** restricts another object creation while de-serialization. */
    protected Object readResolve() {
        return getInstance();
    }

    /** restricts cloning of object */
    @Override
    public Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException();
    }

    public void display() {
        System.out.println("Hurray! I am display from Singleton!");
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

Example of Singleton pattern in core libraries
Creational methods return the same instance again and again.
java.lang.Runtime#getRuntime()
java.awt.Desktop#getDesktop()
java.lang.System#getSecurityManager()
Related Posts Plugin for WordPress, Blogger...