Category Archives: coding

Branch predictor

Whenever in our code a conditional statement is executed, Branch Precitor tries to predict which way the flow will go and executes that even before conditional statement actually returns the output. This is done to stop wastage of time in waiting for conditional statement execution.


From wikipedia
– In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Here is a good example to see what Branch predictor can do

package Permissions.Permissions;

import java.util.Arrays;
import java.util.Random;

public class test {

public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];

Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster // Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128)
sum += data[c];
}
}

System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}

}

Try uncommenting the sort array part and see the difference.

Source- stackoverflow

Submitting Special characters in your Form

If you will try to submit special characters like chinese or spanish text, you will see some junk boxes being submitted to the server. We need to make sure proper encoding, say UTF-8 is being in place. In your HTML (JSP/PHP etc) page, you will need to let browser know that your page works with UTF-8.

<filter>
<filter-name>SessionFilter</filter-name>
<filter-class>com.mysite.SessionFilter</filter-class>
<init-param>
<param-name>PARAMETER_ENCODING</param-name>
<param-value>UTF-8</param-value>
</init-param>
</filter>
<filter-mapping>
<filter-name>SessionFilter</filter-name>
<url-pattern>/*</url-pattern>
</filter-mapping>

In addition, you might want to enforce the settings onto your server to let it know that you are expecting UTF-8 content in request. For example in JBOSS, we will create a filter and enforce UTF-8 content type

And create the filter class like

public class SessionFilter implements Filter {
private String encoding="";

/**
* destroy method to clean up any activities
*/
public void destroy() {
}

/**
* Override the doFilter method to apply any action, in this case setting request encoding
*/
@Override
public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException,ServletException
{
request.setCharacterEncoding(encoding);
chain.doFilter(request, response);
}

/**
* Override init method to set parameter encoding as provided by web.xml
*/
@Override
public void init(FilterConfig filterConfig) throws ServletException
{
if (filterConfig.getInitParameter("PARAMETER_ENCODING") != null)
{
encoding= filterConfig.getInitParameter("PARAMETER_ENCODING");
System.out.println("encoding "+encoding);

}
}

}

Dust me- clean up unused CSS

Recently came accross a legacy code which had a lot of css code and files, which was written over years and most of it was obsolete. Dust-me, firefox plugin helped to figure out all the unused css code. Though I had to traverse all possible flows in the application, but end result was good as few files were identified which were not being used completely and were removed, saving page load time.

Prototype.js library

Some of my old notes from Prototype (3-4 yrs older so there might be changes)

Overview

Prototype is a JavaScript toolkit. This helps in generation of a application by providing commonly used functionality so that the developer does not have to spend time on them.

The Prototype JS has features provides some basic functions which work as short cuts to already existing functionalities e.g. $() can be used in place of document.getElementById(), there are other complex functions for dealing with XMLHttpRequest. A many other libraries are created by extending this library.

You can download the free prototype.js from http://www.prototypejs.org/download. Once downloaded this JavaScript file can be added to any HTML page just like any other JavaScript file <script type=”text/javascript” src=”prototype.js”></script>

Key Functionalities

Let us look at some of the major functionalities provided by Prototype which makes life of developer simple.

$():

This is equivalent to saying document.getElemetById()
e.g.
var name=$(‘name’);

is same as
var name=document.getElementByID(‘name’);

Where HTML has
<input type= “text” id= “name” value= “John”/>

$$():

This will return you an array of elements from HTML document
e.g.
var eleArray= $$(“#formName input”);

This would return an array of all input type fields inside the form formName. This can be further used like

for(var i=0; i<eleArray.length; i++)
{
valueArray=eleArray[i].value;
}

$F():

To get the value of an element in the page
$F(‘name’) is equivalent to document.getElementByID(‘name’).value;

$A():

$A() Creates an array
var arrayOfNodes= $A(xmldoc.getElementsByTagName(‘abc’));

$H():

$H() Creates a hash table
var employeeHash= $H({
name: “John”,
email: “John@company.com”,
employeeId: “12345”
});

Try.these() Function:

This is an interesting function which lets developer write multiple functions. The code keep trying executing functions until one of them is success. This can be helpful if we are writing code to be supported by multiple versions of JavaScript or multiple browsers

Try.these(
function() {//do something
alert (“first one worked”);
return;
},
function() { // do something
alert (“second one worked”);
return;
}

AJAX Object:

Prototype provides AJAX object to minimize the effort using any AJAX related methods. AJAX object further provides the following classes.

AJAX.Request:

Ajax.Request object encapsulates the commonly used Ajax code for setting up the XMLHttpRequest object, performing cross-browser checking for compatibility and callback handling.

function ajaxFunction() {
var ajaxHandle= new Ajax.Request(
url, {
method: ‘get’,
parameters: { username: ‘Anything’},
onSuccess: process,
onFailure: function() {
alert(“There was an error with the connection”);
}
});
}

AJAX.Updater:

This is similar to the AJAX.Rrquest method above, with an additional feature that it can also update the page with the information returned by server to AJAX call.
new Ajax.Updater(container, url[, options])
function ajaxFunction() {
var ajaxHandle= new Ajax.Request(
‘placeholder’,
url, {
method: ‘get’,
parameters: { username: ‘Anything’},
}
});
}

AJAX.Responders:

AJAX responders are more of global methods which we register and unregister at the start and end of execution of code. They monitor all the AJAX activity going on and show the processing activities (say some animation while the data is being fetched from the server).
Ajax.Responders.register(attributes)
Ajax.Responders.unregister(attributes)
Some of the most common callbacks which are used with responders is
Ajax.Responders.register({
onCreate: showProcessing,
onComplete: hideProcessing
});

Additional Links

http://www.prototypejs.org/
http://www.sergiopereira.com/articles/prototype.js.html
http://attic.scripteka.com/prototype_cheatsheet_1.6.0.2.pdf
http://particletree.com/features/quick-guide-to-prototype/

More on Dependency Injection

Sometime back I talked about dependency injection. Dependency injection is a design pattern that implements inversion of control principal. That is, you take out a dependency from within a class and inject it from outside.

So lets say there are 2 classes, Employee and Address, say Employee is dependent on Address

Class Employee

{

public Address address;

public String name;//other stuff

Employee()

{

address=new Address(‘some values here’);

}

}

Here we are leaving the responsibility of creating the address with Employee class. Using DI (Dependency Injection) we will pull out this responsibility of creating the address object from Employee class and give it to calling/initializing class/container.

There are 2 ways to implement this DI concept

1. Through constructor:

class Employee{

public Address address;

Employee(Address address)

{

this.address=address;

}

}

2. Using a setter method:

Class Employee

{

public Address address;

public String name;//other stuff

Employee()

{

}

public void setAddress(Address address)

{

this.address=address;

}

}

Lets make it a bit more interesting. Say we have a AddressFactory which can create either a LocalAddress or PermanentAddress. Both LocalAddress and PermanentAddress implement Address Interface.

In case of non DI scenario

Class Employee

{

public Address address;

public String name;//other stuff

Employee()

{

//check if employee has local address

address=new AddressFactory.getAddress(“LocalAddress”);

//else case get permanent address

}

}

In this case DI becomes more useful as Employee class does not need to worry about the type of address which will be provided by calling class or container. No need to change the code given for DI implementation, it will work fine.

Using Javadoc for documentation

What is Javadoc? Most of the times people confuse it with the actual HTML documentation for the Java code. This is somewhat true but not entirely. Javadoc, itself is not the documentation, it is a tool from SUN Microsystem that helps you generate the documents.

How does it work? Javadoc allows developers to add documentation for a code in the java file itself in some specially formatted comments. The tool will read these comments and create a HTML document file.

Why do we use Javadoc? Why can’t we just create documents on our own? Well That is possible. Javadoc is there to make your life simpler as a developer. It helps you keep your code and documentation information in the same file. Just imagine if you are keeping the documentation separately, everytime you make a change in code, you ill need to modify the documentation also. What if someone misses it? If it is in the same file it is easier to maintain and hard to miss.  Most importantly, you are not writing the whole documentation, but just adding some quick comments which will be interpreted by the Javadoc tool. Lot more easier and faster than actually writing the documentation.

How to implement it? Simple, just add some specially formatted comments in your code

Class Level comments

@author : Author of the class
@version : automatically provide accurate version and date updates.
@since :  Describes when this functionality has first existed.

Method Level

@param : method or constructor argument names and description
@return :  What does your method returns
@throws : Does this method throw an exception
@deprecated : 	Describes an outdated method.

General Commets

@see : Adds 'See also' entry
@link : Adds an inline link with a label for users of your API documentation

The final code will look something like

import java.util.ArrayList;

/**
 * This is a Java Class to find anagrams. Any class level description goes here
 *
 * @author kamal
 * @version 1.0
 * @since 21-Sep-2011
 */
public class test{

/**
 * This is the main method method
 *
 * use {@link #findAnagrams(String)}
 * @param str
 * 		Any param description goes here
 */
public static void main(String str[])
{
	try
	{
		 String finalString="TestString";
		 test t =new test();
		 t.findAnagrams(finalString);
	}
	catch(Exception e) {
	   e.printStackTrace();
	}
}

/**
 * This is another method and we will add the description here
 *
 * @param input
 * 		Any param description goes here
 * @return
 * @throws NullPointerException
 */
private ArrayList findAnagrams(String input) throws NullPointerException
{
	ArrayList retList=new ArrayList();
	if(input.equals("")) throw new NullPointerException();
	printAnagrams(retList, "",input);
	return retList;
}

/**
 * Yet another method description goes here
 *
 * @param retList
 * @param prefix
 * @param word
 */
public void printAnagrams( ArrayList retList, String prefix, String word) {

if(word.length() <= 1) {
	retList.add(prefix + word);
} else {
for(int i = 0; i < word.length(); i++) {
String cur = word.substring(i, i + 1);
String before = word.substring(0, i); // letters before cur
String after = word.substring(i + 1); // letters after cur
printAnagrams(retList,prefix + cur, before + after);
}
}
}
}

and your javadoc comments will look like

image link

testdoc

Rod Cutting problem

Input: A rod on X inches. Price list of Rod prices on n inches.

Problem: Cut a rod of X inches into pieces so that it can be sold at a maximum price.

Example

Input- 8 inch rod
Price list : 1 inch piece=1 Rs, 2=5, 3=8, 4=9, 5=10, 6=17, 7=17 and so on

Output= maximum price=22 (6+2 inch)


/**
* Problem definition: we need to calculate max revenue that can be generated by cutting
* a rod of given size (in inches)
* @author kamal
*
*/
public class CutRod {

//we will be given price based on an inch, 0 inch=0Rs, 1=1, 2=5 and so on
//append zeros where price is not known, so here we can sell max rod of 7 inches
private int prices[]={0,1,5,8,9, 10,17,17,0,0,0,0,0,0,0,0,0};//append n

//using dynamic programming, we will store any previously calculated max prices
private int revenue[]=new int[20];

/**
* Main Method
* @param s
*/
public static void main(String s[])
{
CutRod cr=new CutRod();
System.out.println(cr.fetchMaxPrice(8));
}

/**
* Recursively calls itself to fetch max price
* @param size
* @return
*/
private int fetchMaxPrice(int size)
{
int price=0;
if(size==0)
return 0;
if(revenue[size]>0)
return(revenue[size]);
//brute force
for(int i=1;i<=size;i++) { //ith cut price price=getMax(price, prices[i]+this.fetchMaxPrice(size-i)); revenue[size]=price; } return price; } /** * Returns maximum of 2 integers * @param a * @param b * @return */ private int getMax(int a, int b) { if (a>=b)
return a;
else
return b;
}
}

Maximum Subarray Problem

Problem Definition- Find out a sub-array from n array of numbers where the sum is highest.

Solution  type: Brute force, find out all the combination of arrays and pick the one with maximum sum

Order of complexity: N^2

Code:
public class maxsubarray {

public static void main(String s[])
{
int arr[]={-1,2,4,60,1,-3,2,-6,7,-9,1};

int maxsum=0;
int maxlow=0;
int maxhigh=0;
int low=0;
int high=0;
int sum=0;
int newsum=0;
for(int i=0;i<arr.length-1;i++)
{
sum=0;
newsum=0;
sum=arr[i]+arr[i+1];
newsum=sum;
low=i;
high=i+1;
for(int j=i+2;j<arr.length;j++)
{
newsum=newsum+arr[j];
if(sum<newsum)
{
sum=newsum;
high=j;

}
}
if(sum>maxsum)
{
maxsum=sum;
maxhigh=high;
maxlow=low;
}
}
System.out.println(“lower bound:”+maxlow);
System.out.println(“higher bound:”+maxhigh);
System.out.println(“maximum sum:”+maxsum);
}
}

Tortoise and Hare algorithm

In last post I discussed an algorithm to find out intersection point in 2 lists. A related problem to that is to figure out if a list has cycles. Say there are 10 nodes in list and 10th node is pointing back to 4th node. How ill we figure out if a list has such a cycle.

There can be many solutions, like storing previously traversed nodes, or simply adding a flag to each node indicating of the node was already traversed or not. But these solutions need extra space of order n.

A classic solution to above problem is ‘Tortoise and Hare algorithm’ or ‘Floyd’s cycle-finding algorithm’. The idea is to have two pointers, one will traverse list node by node or move one node at a time (tortoise) and another pointer moving two nodes at a time (hare). If the list has a cycle, the two pointers are bound to meet at some node, otherwise they will never meet. Try to dry run it, you will know what it means.

How to get intersection point of 2 linked lists.

There are 2 lists A and B (we know the root nodes for both). We know that these 2 lists intersect at some point and after that it is common list (they merge into each other, or think of it as a Y list).

example: list A->1->2->3->4->5->6->end
List B->11->12->4->5->6->end

Both the list intersect at node 4. This is what we need to find.

Solution-
1. Find length of A
2. Find length of B
3. Find diff=length A-length B
4. Traverse larger list diff nodes (we know after this nodes will be equal for both lists).
5. Now traverse both list simultaneously and find out the common node (this is our required node).

More solutions here.

I like the solution 5 as well from solution lists. It is simply reversing the list A (6->5->4->-3->2->1).

So when we are traversing list 2 now we will get like 11->12->4->3->2->1->end (as the pointers are reversed). So we are actually calculating length(sum) of non-common part, And we already know length of 2 lists.

length A=A’+C(Common part)
length B=B’+C
and A’+B’=L (length of non-common part we found by traversing list B after reversing list A)

Three unknowns(A’, B’ and C) and three equations. Can’t get simpler than this.