Technicalitee

sizeof for Java developers...

2012-02-02T09:55:00.001-08:00

It is a famous interview question, which has been asked to me and i have asked to others. How do you find the size of an Object in Java? I have come across 2 methods earlier, one is the naive method using a List of 1000000 objects and measuring the heap size with Runtime.java and dividing the delta by number of Objects, second way is using instrumentation. I recently came across a new method of determining object size, it is used internally by Twitter and open sourced under their commons project on Github. The class provides full functionality for Hotspot VMs which we mostly use in our application systems and without -XX:{+|-}UseCompressedOops option enabled which i suppose most of us dont know it exists before watching this talk. The talk is given by the same person who wrote this code. It is wonderful talk which details many memory related stuff and is a must watch for all Java developers. Even though we might not face problems like Twitter it is always good to know them. The calculator implementation returns the size of object in bytes and uses reflection based logic combined with visitor pattern to calculate the size of an object. Cyclic reference check is also handled with the help of a IdentityHashMap. I wrote a small test class to see how it works.


Output : 
E1 size -> 96
E2 size -> 72
E3 size -> 80
Default list size with e1 and e2 -> 248
Default list size with 2 e1 and 1 e2 -> 248
Default list size with 2 e1,1 e2 and 1 e3 -> 328
Predefined sized list size with 1 e1,1 e2 and 1 e3 -> 304

Compared to the naive method which can be inaccurate and hell of configuring instrumentation with preMain() etc. stuff, using this class is dead simple and easy if you have Google Guava in your classpath which i think is mandatory :-). it works only with Guava 11.0.1 and above since the code uses a self loading cache implementation available with Guava. It is available under Apache license and should be reliable since Twitter uses it. If in future i have to crack some memory issue this would definitely be useful...

Guava sweetness!

2011-12-23T00:54:00.000-08:00

If you search for Google Guava in Google you could get a huge number of articles as to why Guava is sweet and the benefits of using it in a Java project irrespective of the problem domain we trying to address. I am not going to reiterate those. Last week i had my own reason to feel happy for using Guava in my project. Rather than a specific problem domain it was a problem of domains. In our application we had a problem of extracting the topmost domain name from a URL host i.e. if the host name is webcache.google.com then i have to extract the top most domain name which is google.com

Being a smart-fast developer i am (notice the sarcasm ;-)) i quickly jumped into eclipse to write an awesome algorithm by using split method to separate the hosts as [webcache,google,com] and join the last 2 to get google.com. I did it all in minutes, wrote few unit tests with other .com hosts and checked in the source and lived happily ever after for the next 10 minutes. My colleague came to my place and asked about webcache.google.co.in. I realized that my code would return co.in as the top domain instead of google.co.in. Both of us discussed and came up with the solution of removing the first segment by default so that [webcache,google,co,in] will return google.co.in and dispersed. When i sat to change the code i realized that [google,co,in] as input would return co.in again. Searching through the internet for any predfined algorithms lead me to this list of public suffixes maintained by Mozilla which can be used to filter out the topmost domain excluding the public suffix from host string.

I decided to write an automated parser which will periodically hit the public list from internet and update the list of suffixes. Suddenly it struck me that this is a general problem and writing a custom solution is not worth it. Since i have already been using Guava for general purpose in my project i started searching Guava for any such functionality of public suffix filtering and found the awesome class InternetDomainName, this has a method topPrivateDomain() which does what i want i.e. return the top most private domain one level beneath the public suffix. 2 days of my effort saved! And i cannot be sure whether i would have handled all scenarios given the 2 days time. The method looks up an immutable set maintained by TldPatterns.java which is class that is auto generated regularly based on latest public suffix with each new release.

However there is one downside to the approach that if the public suffix list gets updated this may not reflect immediately. Thought of contributing a patch to guava which would automatically update the patterns, fortunately (for them ;-)) it has already done by someone and has been accepted as an enhancement. I always have my option of decorating InternetDomainName.java with my own class in case if required before this gets into the official release. Yet another reason to smile for having added Guava in a Java project. Wish google releases a separate JDK with Guava integrated. And the lesson learned here is "If you feel you are solving a generic problem look into Guava before jumping to code".......

My programming principles

2011-11-10T08:13:00.000-08:00

A collection of few best practices and programming principles for Java i have learnt from my experience

Use final modifier for almost all variables, especially for instance variables
Never use a instance variable for data passing between two functions, use arguments instead
Follow Single Responsibility Principle for functions i.e. any function should do only task, if it does more than one then break it into multiple functions
If you want to return more than one value from a function use Tuples
Avoid creating custom checked exceptions, all custom exceptions should extend RuntimeException
Wrap checked exceptions that arise from classes that are not in our control within a RuntimeException or its subclass

Instead of creating a Java bean with getter/setters use immutable i.e. final data members with public accesse.g.

public class Pair{
  public final String key;
  public final String value;

  public Pair(String k, String v){
     key = k;
     value = v
  }
}

is better than

public class Pair{
   private String key;
   private String value;

   public void setKey(String k){
      key = k;
   }

   public void setValue(String v){
      value = v;
   }

   public String getKey(){
      return key;
   }

   public String getValue(){
      return value;
   }
}

Use factory methods over constructors e.g.

private Pair(String k, String v){
     key = k;
     value = v
}

public static Pair of(String k, String v){
   return new Pair(k,v);
}
Usage:-
Pair.of("A","B");

is more concise

A method should not have more than 15 lines of code
Decompose the problem into functions rather than classes to the most atomic level, i.e. a function cannot be decomposed further
Good code does not require any comments, code should convey the intent
Premature optimization is the root of all evil - Donlad Knuth. But if you are 100% sure of the performance benefit you can write it at first shot
Always use slf4j for logging instead of Log4j or something else
Search in your classpath jars before writing any generic utility functions, many frameworks already would have them
Use generic utility APIs like Google Guava, Apache commons instead of writing own code
Programming is not about typing, it is about thinking - Rich Hickey, code written after spending sometime thinking about it rather than something written in haste will be beneficial at longer run
Read Clean code by Uncle Bob
Don't write Unit test cases before writing actual code, those should be used only at later point of time to check any changes does not break the functionality instead of having to test the whole functionality. TDD is not that great!
Watch this presentation on writing simple systems by Rich Hickey
Do not use static imports for anything else except constants, especially not for methods

Disclaimer: These are my personal opinion and does not mean all are correct and also cannot be followed in all situations, this is just an attempt to remind myself of my learnings in the past and for future reference

Curse of the iframe!

2011-10-28T07:28:00.000-07:00

Not sure how many of us developers have used iframes in their applications, i am one of the unfortunate few (may be many). I have been working on an application for a social networking site which depends on hidden iframe based ping to our server from the social site. Browsers are worst at handling iframes consistently. Each browser makes their own implementation of the iframe be it security or rendering.

How would we feel if different vendors implement different JVMs but choose to make the collections behavior different, felt the same while working on iframes. We already had an issue with MS browsers on handling the iframe since the internal ping did not happen due to security settings , i.e. the topmost site was a https while our internal iframe contacted our server in http. This works on all browsers even in Safari but not in IE8+ since MS thinks displaying http content with https is bad which is valid. To fix the issue we placed a patch that will by default ping to our server via https. It worked, we were all happy and deployed the code to production. Soon after we deployed it the issue started reappearing for few users irrespective of the browser. The issue changed its pattern from browser based to user id based like an evolving virus.

On digging deeper using firebug after 1 day i found that the social networking site has dropped a bomb, yes a new header named X-Frame-Options started appearing for few user ids in the response when we pinged through iframe. The roll out of this header is happening in phased manner and soon all users will face the issue. The request doesn't directly contact out URL but through a proxy url provided by the social networking site. We finally decided to get rid of the scum named iframe completely so that we need not handle all this complications. On reading about X-Frame-Options it is found that it is a new header proposed by MS and implemented by other browsers. If you don't like your site's code to be displayed within a frame then you can send this header in your response and modern browsers like IE8+, Mozilla 4+ etc. will not render the content. This might be useful in multiple scenarios when we want our site content not to be displayed in some third party site. I don't want to explain the technical details of this header since it has been done already by the experts.

References:

Mozilla

MSDN

Webmasterworld

Two important things i learned from this issue is:

1. Social networks don't give a shit about their 3rd party developers and apps, they just keep pushing whatever they want without prior information, it is our duty to continuously monitor and adapt accordingly!

2. There is a need for a separate body to govern browser implementations and regulate the behavior of browsers towards iframe, CSS etc. handling to be consistent

Caution while using 3rd party Object keys!

2011-10-03T08:33:00.000-07:00

I am developing a multithreaded application which requires downloading content from multiple websites. The system requires a very high performance characteristic and already runs in 30+ threads. While solving a silly code bug which reduced the performance earlier, I noticed that the threads in the pool are in blocking state for a considerable time while only one thread from the pool is in runnable state. On inspecting the thread dump it lead me to something unexpected since it was waiting on the hashCode() method of URL.java. I had used it as a performance optimization to cache the visited CSS/JS links of a particular site to avoid duplicates.
I didnt care to read the documentation or look into the implementation, all that i saw was whether an equals() and hashCode() was implemented by URL.java and felt happy to use the URL object itself as key to avoid unwanted toString().

Later after discovering the blockage i went through the hashCode() method of URL.java. It is delegated to java.net.URLStreamHandler.java which calls InetAddress.getByName(host)

on tracing to the depth i found that InetAddress is a static class and the getByName method internally calls another method which locks (synchronizes) on a static HashMap i.e. lookup table containing IP addresses.

On a multi threaded high performant application this matters very much even if the hashCode is cached. Since the method locks this table and if it takes time due to some reason all the remaining threads in the pool which were to generate a hashCode() to the call for contains() method for performance were waiting for this lookup table. If i had read the documentation which clearly says it is a blocking method i would have avoided this.
I am sure that many of my IT colleagues would do the same mistake as me! Lesson learnt is that when we use a 3rd party API object (even if its a part of java.net it is not written by me so it is a 3rd party :0D) as a key in a hash based collection, it is better to check the hashCode() and equals() implementation before going ahead as they might have some hidden performance implications like this. Finally i had to revert back to the String representation of the URL instead of having the URL object itself since that level of check is enough in my case ;-)

Servlet vs JSP!

2011-09-06T08:18:00.000-07:00

No this is not another post detailing the key differences between these 2. There are plenty of good sites which give great explanation on this. I was stuck up in a silly issue for 1+ days. The gist of the issue is that i am developing a facebook app with iframe canvas. For the first time when the user logs in i have to check whether user has authorized this app and redirect the user to facebook page requesting for necessary permissions. Since it is a Java servlet based application initially i tried using response.sendRedirect() the url. Since the canvas i.e. my application screen was within an iframe the redirected page was displayed within facebook to give a facebook within facebook effect. While learning about frame busting redirect with javascript i tried to embed this code in my redirect method.

The code worked in IE, but firefox and chrome displayed the text as-is. I was puzzled initially and thought it was an iframe behavior difference between IE and others. I compared my redirect code with another PHP application for facebook. To my surprise he also had written the same javascript code from PHP server and it was working like a charm in all browsers. After 1.5 days of struggle i decided to check the headers with curl. Then i found out that my websites content was "text/plain" whereas the PHP site's content was "text/html". This made be recollect the minute difference i studied long ago.
Servlet's default content type for response is "text/plain" whereas for a JSP it is "text/html". I added the line

 response.setContentType("text/html");

and then it worked like a charm in all browsers. FF and Chrome does not recognize the content as HTML code unless specified but IE somehow recognizes it. A small concept on which i had struggled for 1.5 days made me laugh at myself. In future if someone asks me the difference between JSP and Servlet then this would definitely be in my list. This is what they call learning the hard way!

Project Euler problems 8,10,11 in Clojure

2011-07-24T09:03:00.000-07:00

I have been working on the other problems of Project Euler now, it is interesting to solve it myself and look into Clojure solutions from experts to understand how elegant the problems can be solved with minimal LoC and many inbuilt but unknown features in Clojure. Each problem is a learning experience both mathematically as well as programatically.

This is problem 8 and my solution is below:

And for Problem 10 my solution was faster than some others, i used a sieve to generate all primes less than a given number and added the same.

And Problem 11
i wrote a very bad version of the code first to solve the problem, then revisited each expression to arrive at a better solution as below:

Looking forward to solve as much as i can for the betterment of myself as a programmer...

Project Euler - Problem 9 in Clojure

2011-07-21T19:45:00.000-07:00

I have been following this Blog for quite sometime now the current post is about the pythagorean triplets i.e. the numbers (a,b,c) which obeys the principle of a^2 + b^2 = c^2 i.e. the Pythagoras theorem. The site also says about the Euclid's formula with two variables m and n where m < n which can be used to determine the Pythagorean triplets as shown below:

a = n*n – m*m
b = 2*n*m
c = n*n + m*m

The problem is to find out the triplet whose sum will be 1000. i.e. a + b + c = 1000. I thought of solving this in Clojure and swore to myself to avoid loops :-). I have to find the value of 3 variables a,b,c with the equation above. I thought of reducing the variables to 2 instead of 3, i did this by substituting the Euclids formula in the expression i.e.

n*n – m*m + 2*n*m + n*n + m*m = 1000
After some high school maths the equation deduced to
n * (n +m) = 1000/2 i.e. 500
My idea was to solve this equation to calculate n and m using brute force of incrementing them by 1 while maintaining the condition that m < n and then calculate a,b,c based on the Euclid's formula instead of brute force attack with m and n starting from 1. I wrote the Clojure code as below:

which gave me this output:

375+200+425=1000

"Elapsed time: 0.797227 msecs"

The values 375,200,425 obey the formula of pythagoras theorem with 375^2 + 200^2 = 425^2.

Then i searched the net for fellow human beings who would ve solved this problem in Clojure, i found this page which contained 2 solutions, both of them were smaller and nicer than mine especially the second one which was too concise. But i found that both of them involved finding the 3 variables a,b,c with incrementing m and n. So i measured the time taken of their solutions with mine for this problem. It turned out that my code executed in 0.7 - 0.9 ms whereas the other solutions took 700-800 ms (due to difference in algorithm).

Eventhough the whole purpose of this exercise was to learn Clojure which i did only from the other solutions quoted in the above link I was happy that my code performed well inspite of the fact that it was clumsy and i did not use loops and used recursion instead and my solution was different from the others.

DISCLAIMER: I tried the code for multiple inputs like 2000, 4000 etc and found it was working fine. But i am not sure whether my solution is fool proof in all cases. The guys quoted with alternative solutions are Clojure experts and i dont claim that my code is better. Somehow the performance was good due to a different algorithm.

Why Clojure matters?

2011-07-19T09:29:00.000-07:00

I got fed up with Java for a year now and been searching for a new language that would make my life interesting. First I played with Scala which is an awesome language and makes life far easier. I read an article on Javalobby by Mark Needham the author says that a new language that we learn should change the way think of Programming. Scala did it to some extent but I ended up writing Java sans boiler plate code in Scala and naming methods like operators. Since it allows OO i was still caught in the OO design principles cage which I have been living for 7 years now.

I thought I should give Clojure a try. But learning ((((lojure was not as simple as Scala. When I first looked into a Clojure code I thought WTF is this? A debris of parentheses spread across my screen which makes no sense to a coder. Then I googled and found out this link the author says that i have to speak Lisp if i had to learn Clojure. All that i know about Lisp was it is an ancient language invented in the Pre C era i.e. 1960s. Pacifying myself i proceeded to google for Lisp. I landed at a site by Paul Graham which contained few essays that increased my interest in Lisp.

Roots of Lisp
Revenge of Nerds
Power of Lisp

After reading these articles i prepared my mind to learn Lisp through Scheme (a dialect of Lisp invented in MIT) accompanied by SICP book touted as the bible for a good programmer. I downloaded the PDF and saw few lectures of the creators. It started normally, as i entered the 3rd chapter i had a feeling of reading Electro Magnetic Field theory in my college 3rd sem which is by far the most driest subject i have studied. I felt that i am too old to read this theory as i am not from a Comp Sci background. By this time i have tried few programs in Scheme with SICP exercises and was flabbergasted on how a language can exist without looping constructs and be so powerful. The book said while and for are bad which i felt as an insult to the programming i have done for years. But later understood the truth.

I was able to implement the standard functions of filter, map and reduce in Scala or any other functional language with few lines of code and recursion which eliminated the necessity for loops. I struggled(ing) a lot to change from 1 + 1 to (+ 1 1 )paradigm. Lisp was written with just 7 basic functions i.e.

quote, atom, eq, cons, car, cdr, cond

as mentioned in the link

I could not stop myself from comparing these 7 functions to the 7 swaras in Carnatic music from which great composers like Thyagaraja, Oothukadu, Ilayaraja etc. who churned out amazing compositions. Lisp is just a composition of these 7 functions to write code that can do amazing things e.g. macros.

I learned some basics of Lisp with Scheme and took the dive into Clojure accompanied by some books and simple exercises. The first reason as to why Clojure matters is because it is a Lisp. Experts like Paul Graham have already explained the benefits of using Lisp in the aforementioned links. In addition to the above Clojure matters because it is a dynamic language, i don't need to worry about language constraints like data types and keywords like static, volatile and stuff. Second it removes the restrictive mindset of using Object Oriented design which Scala did to an extent. Writing multi threaded code in Clojure is far more easier than Java since there is no need to worry about low level concepts like synchronization and locking in Clojure. With Clojure i am easily able to decompose my problems into small functions which can be composed to resolve the problem statement which is the essence of functional programming.

Dynamic languages in JVM have the disadvantage of performance overhead involved in using reflection. Clojure also has the same. To confirm this i wrote a small program to generate the first N prime numbers as a series with N as the input. The algorithm that i used may not be the fastest, but i implemented the same algorithm in Clojure and Java and found out Clojure code took 8-10X more time than Java. I was sceptical about sacrificing performance by 10 folds for conciseness and reduced lines of code in favour of Lisp dialect. I googled and found out a good link on language performances in Ubuntu with quad core and single core processors. Although Clojure is nowhere near to Java or Scala (obviously due to the dynamic typing) it faired well enough compared to other popular languages used for Web development like Python and (J)Ruby.

Clojure vs JRuby

Clojure vs Ruby

Clojure vs Python

Since i am primarily a web developer and if Clojure is faster than these languages which is popular next to Java with Rails and Django frameworks i feel it can be used for web development without any hassles. I see the future of JVM development with a team using Clojure (or Scala) for implementing primary dev tasks with a specialised micro team of core Java developers who write performance intensive code and provide Clojure (or Scala) wrappers for the same to the rest of team to use it. This prediction may never become true or may not happen atleast for next 10-15 years but i would love to watch this becoming a reality.

I had the photos of my son taken through the last few months in my system on a single folder, i wanted to organise the files into folders based on date of the picture taken and keep the photos inside the folders named on date. I thought of writing a program in Clojure to do this and wrote it as below:

Note: I suppose the clojure code above can be written in a much more concise manner considering that i am just 2 weeks old in Lisp and 1 week old in Clojure.

I wrote the same logic in Java as below:

At first glance the Clojure code may look obscure and Java code might look elegant. But once we read the basic philosphies of Lisp and understand why it is written that way we will be able to appreciate the code. Clojure does not have a complex type system like Scala. I feel clojure is closer to Java than Scala not syntactically but the way it is implemented.

I may never get a chance to use Clojure in my professional career, but i will use the same in my personal projects and may be if i reach a point in my career where i am able to drive the technical path of an organisation i will definitely use Clojure for all its merits.....

Fedora on my VAIO EA 46!

2011-03-04T09:37:00.000-08:00

Finally got it installed with all drivers in my VAIO. Thanks to Mac4Llin , Cairo dock and the fedora community!

Using Scala with MIgLayout

2011-01-28T10:07:00.000-08:00

Most of us would have faced the hell of GridBagLayout and other crappy layout managers available with Swing. I found MigLayout sometime ago which is a savior, it is very much easy to use with string constraints and saves us from the wrath of default layouts. Since i have been learning Scala i though of venturing into Scala swing which is a thin wrapper around Java Swing APIs in Scala for use in Scala style. Scala Swing contains nice Scala wrappers for FlowLayout, BorderLayout etc. in the form of FlowPanel, BorderPanel respectively. Unfortunately the package does not have a similar panel for MigLayout. So after browsing through the code for these panels and layout container implementations i wrote my own MigPanel which will enable adding of components to a JPanel with MigLayout and constraints. Since i wanted to learn event handling as well i tried a small simple calculator program Calculator using MigPanel. The nice part is that i used partially applied functions for calculation part. Learnt lots of syntactical stuff in this exercise. It looks like below:

Ensime + SBT + Emacs + Scala + Vibrant Ink

2011-01-22T01:41:00.000-08:00

finally was successful in integrating the above mentioned to create a comprehensive development environment for Scala....

My first Android App with Scala (or any other language)

2011-01-14T22:31:00.000-08:00

After a long struggle with the help of this post managed to develop my first application for the Android platform using Scala. Faced a few challenges initially in getting a simple Hello World up and running. Proguard removed my action handler methods since it is invoked thru reflection. I found it after too much struggle.Later i had to change the configuration file for Proguard. The application code and the layout XML, i used TableLayout within LinearLayout

This is how it looks on the phone, the logic is based on the hashcode value of the names, and the nice part is that i did not use the android eclipse plugin and did this entire development using command line tools and emulators. The emulator makes it very easy to test applications. The android team has done an awesome job in providing developer tools, kudos to them......

Desktop Tweak

2011-01-13T07:33:00.000-08:00

I have been using Fedora 13 for quite sometime now and tried to imitate a Mac look and feel using various themes etc. I installed Gnome Do which provides a Dock similar to Mac OS. And now my desktop looks like..........

Scala with gedit

2011-01-10T06:29:00.000-08:00

This post is an extension to an existing post by Lousycoder. I always thought GEdit was a Linux alternative to notepad. Later i discovered how wrong i was. GEdit can be used as a full fledged code editor with just some plugins and syntax highlights. There are lots of plugins available for Gedit. I installed the below mentioned:
1. Bracket Completion
2. Embedded Terminal
3. File Browser Pane
4. Session Saver
5. Snippets (very useful to create code templates like Eclipse)
Slightly tweaked version of the scala language specification for GEdit is available here. This has to be copied into /usr/share/gtksourceview-2.0/language-specs. I downloaded the darkmacs.xml GEdit theme from here and tweaked a few things to create a new colour scheme for GEdit which is available here. This XML has to be imported into the GEdit using Edit -> Preferences -> Font & Colors -> Add option pointing to the XML. Once all the above is done Gedit looks something like this

I use Maven currently to compile the scala files and run them outside on a separate terminal. I also use some snippets which can be imported using the Snippets plugin in GEdit for faster coding.

Disjoint Sets....

2011-01-03T07:34:00.000-08:00

27th problem in Scala is about generating disjoint sets of specified sizes from a set of N elements. i.e. In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons?
Wrote a program that uses recursion with the help of combination generator i used previously.


object DisjointSets {

 def generateCombinations[A](l: List[A], k: Int): List[List[A]] = {
  l match {
    case Nil => Nil
    case _ => {
      if (k > 1)
        (0 to l.size).flatMap({ i => 
    generateCombinations(l.drop(i + 1), k - 1).map({ tmp => (l(i) :: tmp) }) }).toList
      else
        l.map(List(_))
    }
  }
 }

 def group[A](specList : List[Int], dataList : List[A]) : List[List[List[A]]] = {
  specList.size match {
   case 1 =>  List(List(dataList))
   case _ => generateCombinations(dataList,specList.head).flatMap({ tmpList =>
     group(specList.drop(1),dataList.filterNot({tmpList.contains(_)})).map({i => tmpList :: i})
    })
  }
 }

 def main(args: Array[String]) {
  val sizeList = args(0).split(",").map(_.toInt).toList
  val dataList = args(1).split(",").toList
  val groups = group(sizeList,dataList)
  groups.foreach({k => k.foreach(l =>print("["+l.mkString(",")+"] "));println()})
  println("No. of groups : "+groups.size)
 }
}

And the output::


[raam@localhost scala-learning]$ scala DisjointSets 2,2,1 Red,Black,Green,Yellow,Blue
[Red,Black] [Green,Yellow] [Blue] 
[Red,Black] [Green,Blue] [Yellow] 
[Red,Black] [Yellow,Blue] [Green] 
[Red,Green] [Black,Yellow] [Blue] 
[Red,Green] [Black,Blue] [Yellow] 
[Red,Green] [Yellow,Blue] [Black] 
[Red,Yellow] [Black,Green] [Blue] 
[Red,Yellow] [Black,Blue] [Green] 
[Red,Yellow] [Green,Blue] [Black] 
[Red,Blue] [Black,Green] [Yellow] 
[Red,Blue] [Black,Yellow] [Green] 
[Red,Blue] [Green,Yellow] [Black] 
[Black,Green] [Red,Yellow] [Blue] 
[Black,Green] [Red,Blue] [Yellow] 
[Black,Green] [Yellow,Blue] [Red] 
[Black,Yellow] [Red,Green] [Blue] 
[Black,Yellow] [Red,Blue] [Green] 
[Black,Yellow] [Green,Blue] [Red] 
[Black,Blue] [Red,Green] [Yellow] 
[Black,Blue] [Red,Yellow] [Green] 
[Black,Blue] [Green,Yellow] [Red] 
[Green,Yellow] [Red,Black] [Blue] 
[Green,Yellow] [Red,Blue] [Black] 
[Green,Yellow] [Black,Blue] [Red] 
[Green,Blue] [Red,Black] [Yellow] 
[Green,Blue] [Red,Yellow] [Black] 
[Green,Blue] [Black,Yellow] [Red] 
[Yellow,Blue] [Red,Black] [Green] 
[Yellow,Blue] [Red,Green] [Black] 
[Yellow,Blue] [Black,Green] [Red] 
No. of groups : 30

I managed to complete this in 1 hour.... :-)

Pascal's Triangle in Scala

2010-12-28T23:55:00.000-08:00

Might be the Nth post on this topic in Scala where N > 10000000 but for this is the first time am coding Pascal's Triangle. I tried implementing this using the formula nCr and also using recursion (Scala way ;-)) as shown below:


  //Based on calculation using nCr formula without recursion - less efficient
  def genTriangle(numRows: Int) = {
    def fact(i: Long): Long = if (i <= 1) 1 else i * fact(i - 1)
    def getValue(row: Int, col: Int) = if (row == 1) 1 else fact(row) / (fact(col) * fact(row - col))
    (0 to (numRows - 1)).foreach(rIdx => println((0 to rIdx).map(getValue(rIdx, _)).mkString(" ")))
  }

//Based on recursion i.e. arriving at the current row based on previous row values - more efficient
  def genTri(numRows: Int) = {
    def genTriangle0(curRow: Int, arr: Seq[Int]): Unit = {
      def genArray = for (i <- 0 to curRow) yield if (i == 0 || i == curRow) 1 else arr(i - 1) + arr(i)
      println(arr.mkString(" "))
      if (curRow < numRows) genTriangle0( curRow + 1, genArray)
    }
    genTriangle0(1, Array(1))
  }

And the output


scala> genTriangle(8)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

scala> genTri(8)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

scala>

Definitely this is elegant and lesser LoC than Java

26th Problem in scala

2010-12-25T04:12:00.000-08:00

Since i have been learning Scala and trying out few coding exercises from 99 Problems in Scala. I tried to code the 26th problem which was to generate all the possible unordered combinations of K elements from a set containing N elements which is nCk. The site says the same should be coded in 30 minutes. I took almost 5 hours for me to get it right in Scala.
I tried to implement the Revolving door algorithm by Knuth. It was somehow suitable for imperative programming since it involves variables. I managed to find an alternative algorithm using recursion in stackoverflow which suits the FP style. I tried very hard to be FP without mutable data structures. But finally implemented 2 versions of the algorithm one with mutable ListBuffer and a better version with immutables and vals.


package combinations

import collection.mutable._

object CombinationGenerator {
//mutable implementation
  def generateCombinations[A](l: List[A], k: Int): List[List[A]] = {
    if (k > 1) {
      val lb = new ListBuffer[List[A]]()
      (0 to l.size).foreach({ i => generateCombinations(l.drop(i + 1), k - 1).foreach({ tmp => lb += (l(i) :: tmp) }) })
      lb.toList
    } else
      l.map(List(_))
  }
//immutable implementation
  def generateCombinationsFP[A](l: List[A], k: Int): List[List[A]] = {
    l match {
      case Nil => Nil
      case _ => {
        if (k > 1)
          (0 to l.size).flatMap({ i => generateCombinations(l.drop(i + 1), k - 1).map({ tmp => (l(i) :: tmp) }) }).toList
        else
          l.map(List(_))
      }
    }
  }

  def main(args: Array[String]) {
    //    val l = List("a", "b", "c", "d", "e", "f", "g", "h", "i")
    val l = (1 to 8).toList
    val k = 7
    val c = generateCombinations(l, k)
    println("===========================Dirty FP Version======================")
    println("No. of combinations: " + l.size + " C " + k + " = " + c.size + " from set :: " + l)
    c.foreach(println(_))
    println("====================Partially PURE FP Version====================")
    val fpc = generateCombinationsFP(l, k)
    println("No. of combinations: " + l.size + " C " + k + " = " + c.size + " from set :: " + l)
    c.foreach(println(_))
  }

}

The algorithm involves separating the first element i from the set and joining the same with all the combinations of retrieving k-1 elements generated recursively from the remaining i+1,1+2....n set. The output is as follows:


===========================Dirty FP Version======================
No. of combinations: 6 C 4 = 15 from set :: List(1, 2, 3, 4, 5, 6)
List(1, 2, 3, 4)
List(1, 2, 3, 5)
List(1, 2, 3, 6)
List(1, 2, 4, 5)
List(1, 2, 4, 6)
List(1, 2, 5, 6)
List(1, 3, 4, 5)
List(1, 3, 4, 6)
List(1, 3, 5, 6)
List(1, 4, 5, 6)
List(2, 3, 4, 5)
List(2, 3, 4, 6)
List(2, 3, 5, 6)
List(2, 4, 5, 6)
List(3, 4, 5, 6)
====================Partially PURE FP Version====================
No. of combinations: 6 C 4 = 15 from set :: List(1, 2, 3, 4, 5, 6)
List(1, 2, 3, 4)
List(1, 2, 3, 5)
List(1, 2, 3, 6)
List(1, 2, 4, 5)
List(1, 2, 4, 6)
List(1, 2, 5, 6)
List(1, 3, 4, 5)
List(1, 3, 4, 6)
List(1, 3, 5, 6)
List(1, 4, 5, 6)
List(2, 3, 4, 5)
List(2, 3, 4, 6)
List(2, 3, 5, 6)
List(2, 4, 5, 6)
List(3, 4, 5, 6)

Even though i am not from a computer science background and these algorithms are new to me and i would have completed this faster in Java (apdinu sollika vendiyadhu thaan) still this shows my programming skills are bad and requires improvement, hope it happens before i complete the 99 problems......

Scala and FP!

2010-12-12T00:41:00.000-08:00

Off late i have become bored with Java (not because i ve learnt everything in it, there is still lot to learn....) I am trying to learn Scala which is a mix of OO and Functional Programming (FP). I am so excited to learn FP since it is so easy to write code. I have always (for atleast 3 years) wanted to write a small utility code that organizes the MP3 files in my collection in a proper way i.e. sequential numbering of songs starting from 001 to 999 and remove unwanted strings from the song names i.e. tamilmp3world-.mp3 etc.
Since i have been learning Scala for more than 2 weeks now i thought of writing the utility in Scala using the power of FP. I wrote the code below and was successful in organizing my files.


object OrganizeFiles {

 val removables = List("copy of ", "tamilbeat.com - ", "ajraj-", " - tamilwire.com", "tamilmp3world.com - ", " mazhai - ",
    "rehman - ", "baba__", "artist - track ", "may_maadham_[0-9]", "lagaan - ", "lagaan- ", "lagaan-", "lagaan -",
    "roja_[0-9]", "roja_", "bombay_[0-9]", "guru - 0[0-9] ", "puthiya_mannarkal_[0-9]", "sok-", "0[0-9]-", "indra_[0-9]", "0[0-9]\\_", "divya\\_-\\_",
    "- ", "0[0-9]", "ilayaraja ", "[0-9][0-9]\\.", "[0-9][0-9]\\. ", "\\. ", "vanna vanna pookal ", "bharathi ", "kaasi-",
    "aranmanai kili ", "poonthalir-", "nilave mugam kaatu ", "--a, ", "--", "veera ", "thoongathe thambi thoongathe ",
    "voice ", "--", "ilaiyaraj", "illayaraaj", "orkaidhiyidair", "radha\\_-\\_", "divya__", "tamiljoy.com-", "\\_smk", "tamilvibez.com\\_",
    "[\\s]{2,}", " _ mella thirandhadu kadavu", "1\\.", "mouna\\_geetham\\_-\\_")

  def removeUnwanted(s: String) = {
    //form the regular expression string with mkString from above list to invoke replaceAll
    s.toLowerCase.replaceAll(removables.mkString("|"), "").trim
  }

  def capitalize(str: String, i: Int) = {
 //split the folder names with file separator so that each folder name goes into a String array
    val arr = str.split(java.io.File.separatorChar)
    val fName = removeUnwanted(arr.last)
    //pad required 0s in the start to generate 001, 011, 111 etc.
    arr(arr.length - 1) = "0" * (3 - i.toString.length) + i + "-" + fName.charAt(0).toUpperCase + fName.substring(1)
    //assemble the modified file name 
    arr.mkString(java.io.File.separator)
  }

  def changeFiles(f: java.io.File) {
 //filter the MP3 file alone from the folder and sort based on name
    val s = f.listFiles().filter { i => i.getName.endsWith(".MP3") || i.getName.endsWith(".mp3") }.sortBy(_.getName)
    for (i <- 0 until s.length) {
      val newName = capitalize(s(i).getAbsolutePath, i + 1)
      println(newName)
      //rename the file
      s(i).renameTo(new java.io.File(newName))
    }
    //call the function recursively on all sub-directories
    f.listFiles().filter { i => i.isDirectory }.foreach { changeFiles(_) }
  }
  
  def main(args: Array[String]) {
    val f = new java.io.File(args(0))
    //call it in each sub directory
    f.listFiles.filter { _.isDirectory }.foreach(changeFiles(_))
  }
}

I was able to do what i wanted to in just 37 lines of code ignoring comments. Since Scala integrates well with Java i used the java.io.File api methods for this purpose. I did not write this in Java because i felt lazy since this would be tedious and cumbersome and consume atleast 100 lines of code....

Java Sine wave program

2010-11-20T19:04:00.000-08:00

My sister has just joined her training with an IT company. Just went through some of her exercises. Once of them was to generate a sine wave. Had a look in to the formula from here. Spent some 2-3 hrs in coding a small utility program that can draw a sine wave based on the given input.

HTF did the guy invent this formula???


import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.font.FontRenderContext;
import java.awt.font.TextLayout;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;

import javax.swing.JFrame;

/**
 * A simple utility class using Java swing to generate sine wave based on input params
 * @author raam
 *
 */
public class SineFrame extends JFrame{

 private static final long serialVersionUID = 1L;
 
 //1d array to store the amplitude data, time data is represented or derived from the index of array
 double[] amplitude;
 
 int center;
 
 double H_STEP_SIZE = 1d;
 
 int t,amp;
 
 float omega;
 
 /**
  * Overloaded constructor
  * @param t
  *    Time part
  * @param amp
  *    Maximum amplitude of the generated sine wave
  * @param omega
  *    Frequency
  * @param hSize
  *    Horizontal size of the frame
  * @param vSize
  *    Vertical size of the frame
  */
 public SineFrame(int t,int amp,float omega,int hSize,int vSize){
  this.t = t;
  this.amp = amp;
  this.omega = omega;
  //to check integer overflow when multiplied with horizontal step size
  amplitude = new double[t*(int)H_STEP_SIZE < t?Integer.MAX_VALUE:t*(int)H_STEP_SIZE]; 
  setDefaultCloseOperation(EXIT_ON_CLOSE);
  center = vSize/2;
  setSize(hSize,vSize);
  //calculate the co-ordinates based on input params to draw the wave
  calculateCoords(t,amp,omega);
 }
 

 private void calculateCoords(int t, int amp, float omega) {
  for(int i=0;i<amplitude.length;i++)
   amplitude[i] = amp * Math.sin(omega*(i/H_STEP_SIZE));  
 }

 @Override
 public void paint(Graphics g){
        Graphics2D g2 = (Graphics2D) g;
        Point2D prev,cur;
        double y;
        Line2D lin;
        Font font =  new Font("Times", Font.BOLD, 25);
        FontRenderContext frc = g2.getFontRenderContext();
        TextLayout layout = new TextLayout("A = "+amp+"; Omega = "+omega+"; t = "+t, font, frc);
        layout.draw(g2, 10f, 50f);        
        cur = new Point2D.Double(10,center);
        //iterate thru' the calculated co-ordinates and draw lines between adjacent points
        //to generate the sine wave
        for(int i=0;i<amplitude.length;i++){
         prev = cur;
         y = getCoOrdsFromAmplitude(amplitude[i]);
         cur = new Point2D.Double(10+(i/H_STEP_SIZE), y);
         System.out.println("Co-ordinates--{x="+cur.getX()+"},{y="+cur.getY()+"}");
         lin = new Line2D.Double(prev,cur);
         g2.draw(lin);
        }

        
 }
        
 private double getCoOrdsFromAmplitude(double amp){
  return center + amp;
 }
 
 public static void main(String[] args) {
        java.awt.EventQueue.invokeLater(new Runnable() {
            public void run() {
                new SineFrame(1000,200,.07f,1000,600).setVisible(true);
            }
        });
 }
 
}

and the output

Groovy vs Java

2010-10-15T22:59:00.000-07:00

I have been trying to learn Groovy for sometime now. Was wondering how the code compares with Java that i have been writing all these 6 years. I felt too happy that i am able to do wonderful collection operations with just few lines of code in Groovy. Let us take an example programming problem statement which needs to be realized using Java and Groovy.

Statement:

Consider the currency notes available in India and US as follows:

India - 1000,500,100,50, 20, 10, 5, 2, 1

US - 1000,100,50,25, 10, 5, 1

Given the amount as an Integer the output should be calculated denominations in the above mentioned notes based on the country. For e.g. if 55 is given with Country India the output should be 50 x 1, 2 x 2, 1x1

I wrote a sample code GChange.groovy as shown below:


def getChange(Integer amt, String ctry = 'in'){
 def coins =  ['in':[1000,500,100,50, 20, 10, 5, 2, 1],'us':[1000,100,50,25, 10, 5, 1]]
 change = [:]
 //closure 1
 coins[ctry].each {i ->
  while(amt > 0){
   if((amt - i) >= 0){
    amt -= i
    if(change[i]!=null)//increment the count if already exists
     change[i]++
    else//add to the map with count 1 if it does not exists
     change.put(i,1)
   }
   else
    break;
  }
 }
 println ctry.center(10,'-')
 //closure 2
 change.each {k,v -> printf("%5s x %2s \n",k,v)}
}

getChange(1327)
getChange(1327,'us')

This code produces an output as shown below:


----in----
1000 x  1
100 x  3
20 x  1
5 x  1
2 x  1
----us----
1000 x  1
100 x  3
25 x  1
1 x  2

The same code in Java is shown below:


import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Change {

 static Map<String,List<Integer>> coins = new LinkedHashMap<String,List<Integer>>();
 
 static{
  Integer[] a = {1000,500,100,50, 20, 10, 5, 2, 1};
  coins.put("in", Arrays.asList(a));
  Integer[] b = {1000,100,50,25, 10, 5, 1};
  coins.put("us", Arrays.asList(b));  
 }
 //additional method
 public static void getChange(Integer amt){
  getChange(amt, "in");
 }
 
 public static void getChange(Integer amt,String ctry){
  Map<Integer,Integer> change = new LinkedHashMap<Integer, Integer>();
  for(Integer i:coins.get(ctry)){
   while(amt > 0){
    if((amt - i) >= 0){
     amt -= i;
     if(change.get(i)!=null)//increment the count if already exists
      change.put(i, change.get(i)+1);
     else//add to the map with count 1 if it does not exists
      change.put(i,1);
    }
    else
     break;
   }
  }
  System.out.println("----"+ctry+"----");
  for(Map.Entry<Integer, Integer> e:change.entrySet()){
   System.out.printf("%5s x %2s \n", e.getKey(),e.getValue());
  }
 }
 
 public static void main(String[] args) {
  getChange(1327);
  getChange(1327,"us");
 }
}

Even though the above program produces the same output, there are few things to be noted here:

a. Lines of Code: 46 lines of Java code is required to implement the solution, whereas Groovy requires just 22 lines which almost half

b. Variable declarations: Java variable declarations are complex and require the generic types and collection implementations to be specified before hand. Also adding the list of Map has to be done separately in a static block. In Groovy the formation of the data structure containing country to currency notes mapping is possible in a single line and much more elegant than Java

without having to specify the type information before hand.

c. Iterations: Code within the iteration of collections is easy in Groovy using Closures. We have used 2 closures for calculation of denomination as well as for printing the contents of final result. In Java we need to iterate with enhanced for loops and Map.Entry variables which is not as simple as the Groovy way.

d. Unwanted additional methods: Since Groovy supports default method parameter values we can invoke the getChange() method in two ways i.e. getChange(amount) or getChange(amount,country). If the country is not provided then by default India is considered.

To realize this in Java we need an additional method named getChange() with one argument that internally calls getChange() with two arguments with India as the second argument value.

It is obvious from the above example that Groovy improves developer productivity with initial training investment even though it is all the same byte code running in the JVM.

P.S: The above logic can be made simpler using a divisor and remainder method, but the purpose of this entry is to compare the syntax of Java and Groovy, hence i have not implemented the same.

Unique values in List

2009-11-15T04:58:00.000-08:00

The easiest way according to me to populate a list with unique values i.e. eliminate duplicates is

List l;
.
.
.
LinkedHashSet ls = new LinkedHashSet(l);
l = new ArrayList(ls);

The elements in the List should have proper overriding of equals() and hashCode() method

Java sizeof .....

2009-11-11T18:37:00.000-08:00

Previously i used to find out the approx size of a Java object using the naive method of creating N objects and measure the increase in heap size without doing a GC, but after some digging in the net i found a new way using Java Instrumentation APIs to get the size of an object. From the experiment done in a 32 bit Windows JVM it seems that the size of an Object i.e. class A{} is 8 bytes i think 4 bytes for the int hashCode and 4 bytes for the Class reference of this object. If we add one more byte variable to this class then the size expands by another 8 bytes. It remains the same for addition of another 7 bytes. Hence it is found that JVM expands the size in steps of 8 bytes.
I found the answer to one of my long pending doubts, what is the size of a boolean variable in Java, yes it is a byte!
I used the below mentioned code to test the same

import java.lang.instrument.Instrumentation;import java.util.HashMap;
interface I{ }
interface K{ }
class C implements I,K{
String s = new String("jkashdkjhsjkafsd"); }
class D extends C{
}
class A{
// byte b1;
// byte b2;
// byte b3;
// byte b4;
// byte b5;
// byte b6;
// byte b7;
// byte b8;
// byte b9;
// byte b10;
// byte b11;
// byte b12;
// byte b13;
// byte b14;
// byte b15;
// byte b16;
// byte b17;
// int a;
// int b;
// boolean b2;
// boolean b3;
// boolean b4;
// boolean b5;
// boolean b6;
// boolean b7;
// boolean b8;
// boolean b9;
// boolean b10;
// boolean b11;
// boolean b12;
// boolean b13;
// boolean b14;
// boolean b15;
}
class B{ }
public class SizeTester {
public static void premain(String agentArgs, Instrumentation inst){ System.out.println("A - "+inst.getObjectSize(new A()));
System.out.println("B - "+inst.getObjectSize(new B()));
System.out.println("I - "+inst.getObjectSize(new I(){})); System.out.println("C - "+inst.getObjectSize(new C()));
System.out.println("D - "+inst.getObjectSize(new D()));
System.out.println("S1 - "+inst.getObjectSize(new String "jkashdkjhsjkafsd")));
System.out.println("S2 - "+inst.getObjectSize("jkashdkjhsjkafsd"));
}
public static void main(String[] args) {
}
}

The manifest file contains

Manifest-Version: 1.0
Premain-Class: SizeTester

The jar file has to be given as VM argument javaagent:

My first post

2006-06-20T07:09:00.000-07:00

Just wanted to consolidate all the information i learn day to day about Programming, Computers, Technology, database etc. in a useful manner which prompted me to create this blog. Will keep posting useful info.