Posts

Shortest Distance Graph Algorithms - How do they differ?

The shortest distance graph algorithms can be tricky. Which algorithm should be used when, whether it can work for negative edges or cycles, which one is the most efficient for the given problem - you should be asking these questions before deciding on a Shortest Distance Algorithms. The implementation and pseudo code for the standard Shortest Distance Algorithms are easily available on the web but how these different algorithms differ is often not highlighted. In this post, I will focus on how different graph algorithms differ from each other. These different algorithms differ in term of - Single Source Shortest Path vs All Pair Shortest Path Algorithms . Single Source Shortest Path algorithm calculates the shortest distance from a given Source vertex to all other graph vertices. All Pair Shortest Distance algorithm calculates the shortest distance between all pairs of graph vertices. Weighted graph - Can the algorithm work if edges have weights? Negative weight edges - Will

Concise Collection Initialization using Google Guava

One thing I really like with languages like python, ruby or perl is that they have succinct and elegant way to initialize the collections -  Map, Set and Array. Collection Literals project is supposed to bring concise initialization syntax to Java. But there is no hope for this until Java 8. There are some hackish ways to do inline initialization of collections particularly using Double Curly Brace Initialization but none of these is elegant and expressive. Google provides an excellent api of their core libraries called Guava . This library provides some nice utility classes to perform initialization of collections. For each collection type, Guava provides Utility Classes. e.g. for Lists, there are classes - Lists  (utility class for operating with lists) and ImmutableList  - (an Immutable version of List). Lets take a look at couple of examples - Loading .... References - http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/001193.html http://www.c2.com/cgi/wiki?

Java - One liner to Configure Logging

Often while writing some quick test or doing a prototype, we want to use logging. But we do not want to spend any time writing a properties file and doing the whole setup. However there is a quick way to get log4j ready to use in a single line. Log4j provides a BasicConfigurator which can be used to quickly configure the logging. Usage Example - public class LoggingOneLiner1 { private static final Logger logger = Logger .getLogger(LoggingOneLiner1.class); public static void main(String[] args) { // Configure the logging - this does the whole setup BasicConfigurator.configure(); // Optional Step - change the logging level to INFO from default DEBUG Logger.getRootLogger().setLevel(Level.INFO); logger.info("Its nice to to be able to configure logging in one line"); logger.debug("I like quick and dirty java tricks"); } } From the api docs of log4j - The invocation of the   BasicConfigurator.configure   method creates a rather simpl

Speedup Your Collections with Improved Hashing Function from Java7

Java7 has introduced an improved hash function for Map and Map derived implementations ( since 7u6 ). It is applicable for keys of type String . Following collections can make use of this new hash function. HashMap Hashtable HashSet LinkedHashMap LinkedHashSet WeakHashMap ConcurrentHashMap The new hash function improves the performance when there are large number of collisions .  It can be enabled by setting the System property  jdk.map.althashing.threshold . If jdk.map.althashing.threshold=k  , This means that java will use alternative hashing function for maps with capacity greater than k entries. Usage Example - java -Djdk.map.althashing.threshold=512 MyAppMain Why it is disabled by default and caveat before using - This feature is disabled by default to ensure backward compatibility.  The iteration order of keys, values and entries will change after using the new Hash function. According to Java team, many applications have dependencies on iteration

Prefer ThreadLocalRandom over Random

Java 7 has introduced a new random number generator - ThreadLocalRandom Normally to generate Random numbers, we either do Create an instance of java.util.Random  OR Math.random() - which internally creates an instance of java.util.Random on first invocation.  However in a concurrent applications usage of above leads to contention issues - Random is thread safe for use by multiple threads. But if multiple threads use the same instance of Random, the same seed is shared by multiple threads. It leads to contention between multiple threads and so to performance degradation.  ThreadLocalRandom is solution to above problem. ThreadLocalRandom has a Random instance per thread and safeguards against contention. From the api docs -  Usages of this class should typically be of the form:  ThreadLocalRandom.current().nextX(...)  (where  X  is  Int ,  Long , etc). When all usages are of this form, it is never possible to accidently share a  ThreadLocalRandom  across multiple thre

Improving readability using TimeUnit sleep

All of us have seen the following idiom  numerous times in java code. //Sleep for 6 minutes Thread.sleep(6*60*1000); However the above is not readable. When someone is writing code, he has to perform the conversion to milliseconds. While trying to understand the code also, someone has to perform the transformation from milliseconds to familiar seconds and minutes. java.util.concurrent .TimeUnit class also provides mechanism to sleep which circumvents the above difficulties. Following is an example of sleep using TimeUnit. //Sleep for 6 minutes TimeUnit.MINUTES.sleep(6); //Sleep for 10 seconds TimeUnit.SECONDS.sleep(10); //Sleep for 2 hours TimeUnit.HOURS.sleep(2); TimeUnit supports following time units for sleep. DAYS HOURS MICROSECONDS MILLISECONDS MINUTES NANOSECONDS  SECONDS Internally TimeUnit also invokes Thread.sleep() for sleeping. Following is the code used by sleep() method in TimeUnit public void sleep(long timeout) throws InterruptedExceptio