Java Collections hierarchy

Collection Hierarchy

How to choose collection for my use case?

Locale character sorting - java

I am currently working on multilingual site development. Yesterday I faced an interesting requirement to sort the locale characters.

Assuming the english text sorting, we have written the code as Treemap based sorting.

Map data = new TreeMap();  

     data .put("sarav", "000");  

     data .put("rohit", "002"); 

As i18n involved, what happens all locale based text got the last position in the sorting.

data .put("ärav", "003"); 

Interestingly Treemap has a constructor with Compartor

TreeMap(Collator.getInstance(Locale.GERMAN))

The Collator class performs locale-sensitive String comparison. By using this Collator, we will be able to build searching and sorting routines for natural language text.

Collator is an abstract base class. Subclasses implement specific collation strategies. One subclass, RuleBasedCollator, is currently provided with the Java 2 platform and is applicable to a wide set of languages.

Like other locale-sensitive classes, you can use the static factory method, getInstance, to obtain the appropriate Collator object for a given locale, as I used above.

We can set a Collator's strength property to determine the level of difference considered significant in comparisons. Four strengths are provided: PRIMARY, SECONDARY, TERTIARY, and IDENTICAL. The exact assignment of strengths to language features is locale dependant. For example, in Czech, "e" and "f" are considered primary differences, while "e" and "ê" are secondary differences, "e" and "E" are tertiary differences and "e" and "e" are identical.

I didn't set any strength for my requirement, it worked as-is. I found a sample for this in the below URL

http://stackoverflow.com/questions/7502642/sort-a-list-of-hungarian-strings-in-the-hungarian-alphabetical-order

How to do parallel processing in java?

I have this question in my mind for long time. We have dual processor/multi processor whether we are using the full power of those. How JVM itself can split the task across the processor and make the instruction set execution more efficient?

As usual before I move 5 steps in my thought process, industry will move 50 steps. No wonder, we have solve for this in Java 7.

It's the fork/join framework is an implementation of the ExecutorService interface that helps you take advantage of multiple processors. As with any ExecutorService, the fork/join framework distributes tasks to worker threads in a thread pool. The fork/join framework is distinct because it uses a work-stealing algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy.

 If you are not using Java 7 you also need to have "jsr166y.jar" in the classpath.

package com.sarav.forkjoin;

import java.util.Random;

public class Problem {
private final int[] list = new int[2000000];

 public Problem() {
  Random generator = new Random(19580427);
  for (int i = 0; i < list.length; i++) {
   list[i] = generator.nextInt(500000);
  }
 }

 public int[] getList() {
  return list;
 }

}

RecrusiveAction implementation

package com.sarav.forkjoin;

import java.util.Arrays;

import jsr166y.forkjoin.RecursiveAction;

public class Solver extends RecursiveAction {
 private int[] list;
 public long result;

 public Solver(int[] array) {
  this.list = array;
 }

 @Override
 protected void compute() {
  if (list.length == 1) {
   result = list[0];
  } else {
   int midpoint = list.length / 2;
   int[] l1 = Arrays.copyOfRange(list, 0, midpoint);
   int[] l2 = Arrays.copyOfRange(list, midpoint, list.length);
   Solver s1 = new Solver(l1);
   Solver s2 = new Solver(l2);
   forkJoin(s1, s2);
   result = s1.result + s2.result;
  }
 }
}

Test to verify my understanding

package com.sarav.forkjoin.testing;

import jsr166y.forkjoin.ForkJoinExecutor;
import jsr166y.forkjoin.ForkJoinPool;
import com.sarav.forkjoin.Problem;
import com.sarav.forkjoin.Solver;

public class Test {

 public static void main(String[] args) {
  Problem test = new Problem();
  // Check the number of available processors
  int nThreads = Runtime.getRuntime().availableProcessors();
  System.out.println(nThreads);
  Solver mfj = new Solver(test.getList());
  ForkJoinExecutor pool = new ForkJoinPool(nThreads);
  pool.invoke(mfj);
  long result = mfj.getResult();
  System.out.println("Done. Result: " + result);
  long sum = 0;
  // Check if the result was ok
  for (int i = 0; i < test.getList().length; i++) {
   sum += test.getList()[i];
  }
  System.out.println("Done. Result: " + sum);
 }
}

I didn't apply this in my real time application to give some performance report. Soon I will :)

Linked List - Reverse & identifying the cycle

Linked List- another interesting and simple data structure. Most of the interviewers ask for reverse and identifying the cycle in linked list.

Identifying the cycle
Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track of what nodes have been encountered.


One idea is to mark nodes that have been seen, either by adding a flag to the node itself or storing information about the node in a separate data structure. Unfortunately, this method requires modification of the node and/or additional space.


Interviewers won't accept this way as they want to understand/see how we traverse across nodes.

Another idea is to move the pointers in different speed to identify a cycle as below. To make one pointer faster than the other, just advance it two nodes instead of one.

public static boolean hasCycle(Node head) {

Node fast = head;
Node slow = head;

while (true) {
if (fast == null || fast.next == null)
return false;
else if (fast == slow || fast.next == slow)
return true;
else {
fast = fast.next.next;
slow = slow.next;
}
}
}
Reverse


With three pointers, reverse will be pretty straight forward to move on.



Node previous = null;
Node current = head;
Node forward;

while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}

Download the code (Just copy & paster in your editor)

Social Commerce - my view

What is Social commerce?

Social commerce is a another dimension of e-commerce. With the social media interaction and user contributions in its side, it will promote/drive online user to buy and sell products or services.

Why it gets big hype in recent timings?
E-commerce sites target the big user bank in social networking sites like Facebook, Twitter etc. E-commerce sites want to drive traffic to their site with these platform which they can convert as a purchase.

Why Facebook is in the top compared to other sites?

It's because of its user bank -

More than 800 million active users

Average user has 130 friends

More than 70 languages available on the site

More than 7 million apps and websites are integrated with Facebook

More than 350 million active users currently access Facebook through their mobile devices

Data from http://www.facebook.com/press/info.php?statistics

Which industries are getting hot?

Fashion (Clothing & shoes) , Electronics (which includes mobile phones, tech gadets)

How I see its different from traditional E-commerce?

• Group Buy – With friends and family, I can buy and make them buy.Buying something together.
• Advise - I can get friend's advice on a prospective purchase. Same I can provide too.
• Recommend/Review - suggesting a specific item to a friend who is looking for one with some review.
• Share - Something like show off, what I own
• Trust - Trust will be/can be created not only by item description but from my friends and family.

Readymade Solutions:

IBM social commerce, Microsoft Commerce

Though we can say solutions, but it has to be tied with different departments Marketing, Analytics, PR etc

Prediction: $30billion revenue from social commerce market in 2015

Data fromhttp://www.digitalbuzzblog.com/infographic-the-value-of-social-commerce/

Reverse an Integer and String

Just tried out the very basic problem today. How to reverse an integer and string? Please let me know, if i can improve anything on this.

Integer logic 1234 = 4 *10^3+3*10^2+2*10^1+1*10^0
String logic Sarav= replace the indices value till you reach the middle.

package com.sarav.util;
/**
* @author sparamasivan
*
*/
public class ReverseUtil {

public static void main(String[] args) {
System.out.println(reverse(1234));
System.out.println(reverse("Sarav"));
}

public static int reverse(int number){
int length=String.valueOf(number).length();
int reverse=0;
while(length>0){
//int tens=(int)(Math.pow(10.00,length-1));
//reverse=reverse + ((number%10)*tens);
reverse=(reverse*10) + ((number%10));
number= number/10;
length--;
}
return reverse;
}

public static String reverse( String s ) {
int length = s.length(), last = length - 1;
char[] chars = s.toCharArray();
for ( int i = 0; i < length/2; i++ ) {
char c = chars[i];
chars[i] = chars[last - i];
chars[last - i] = c;
}
return new String(chars);
}
}

Protocol Buffers & Avro

I am consuming service from world's biggest market place for my site inventory. Current SLA for their services - ~200msec. I was stunned on hearing their new SLA for us ~20msec. Heard about their optimization happened on data serialization and digged little bit today to upgrade myself.

Most server-client platforms use a serialization technique to serialize into a leaner data format, and then de-serialize on the receiving end.Many languages offer native serialization APIs, but when serializing the data using the native API, Metadata about the class is serialized into the output too. is it possible to serialize only data and not with metadata?

Yes we have - Google Protocal Buffers & Apache Avro

Google Protocol Buffers
Protocol Buffers is a serialization format with an interface description language developed by Google. It is available under free software, open source license. Protocol Buffers design goals are emphasized performance and simplicity. It is a language and platform neutral technology that is an extensible mechanism for serializing structured data.

It works by you defining how you want your data to be structured via proto files, which are simply structure text files. Once you have decided the structure in your proto file, the proto executable is called on it, and a generated class (Adobe Actionscript 3, Java, C, C++, Python) is produced. The class can be generated into multiple different technologies, which means the class can be generated for the client and server technologies. Thus securing a data contract (which is type safe) between the two. The protocol buffer technology provides the ability to update the data structure without breaking deployed programs that are compiled against the old format.

Protocol buffers claims it takes between 100 to 200 nanoseconds to parse. As the overhead of the data structure is not needed in protocol buffers, only the object fields’ values is serialized. Protocol buffers will find the most compact serialization technique for a particular data type (always primitives), and only serialize fields that are not null.

Apache Avro
Avro is another very recent serialization system. It provides rich data structures that are compact, and are transported in a binary data format.

Avro relies on a schema-based system that defines a data contract to be exchanged. When Avro data is read, the schema used when writing it is always present. Similar to Protocol Buffers, it is only the values in the data structure that are serialized and sent. The strategy employed by Avro (and Protocol Buffers), means that a minimal amount of data is generated, enabling fast transport.

The schemas are equivalent to protocol buffers proto files, but they do not have to be generated. The JSON format is used to declare the data structures.

Protocol Buffers & Avro

Google’s Protocol buffer provides a much richer API for defining a data contract than Avro. Below is a list of features available to Protocol Buffers and not Avro:

• Declare nested types


• Define requires, repeated and optional fields


• Specify default values on fields


• Declare enumerations and set a fields default value from it


• Multiple message types in the same document


• Import other proto files


• Declare a range of field numbers in a message available for third party extensions (Extensions) Nested Extensions


• Define services

Avro is only compatible with C, Java and Python, but Protocol Buffers is compatible with C, C++, Adobe Actionscript 3, Java and Python.

Now you would have guessed what that company applied for their middleware solution as a push mechanism between server and client.

How to disable the Enter key while doing form posting?

I got a problem last week in IE browser only which blocked my production roll out. As form fields, i had a quantity field with one form refresh to update the quantity and another form button to submit.

Order of my fields- Quantity , Refresh button and submit button.
We didn't specify any tab order. In all the browsers after entering the quantity,if user click enter button, it went to update the quantity. And only in this crapy IE, it went for form submit.

Here is my simple javascript which helps to solve this problem


function handleEnter(inField, e) {
var charCode;

if(e && e.which){
charCode = e.which;
}else if(window.event){
e = window.event;
charCode = e.keyCode;
}

if(charCode == 13) {
alert("We will update the quantity here what happen today: " + inField.id);
}

}

Attaching the event to field
Quantity: input type="text" id="someInput" onkeypress="handleEnter(this, event)"


Did they not code properly, while writing their user agents or did they handle unwanted usecase in which my case fell down? Why this Crap alone behaving like this?

Why Set collection has no get method?

It's a interseting question.

When we are developing a tool (kind of crawler), we had this requirement.

We used our own object and over ride the equals method. We were abou to use the get method in the set and finally realized set has no get method :)

Pasted in the sun forum for the experts view

http://forums.sun.com/thread.jspa?threadID=5375529&tstart=0

Didn't get the exact answer :(

Solution: Set internally has a Map to identify and store the unique objects. In simple whatever objects we wil place in Set, it will go as a key in the internal Map with dummy optimized value.

Carefully watching the iterator implementation of Set, it is like
return map.keySet.iterator();
Seems to be pretty simple implementation.

But get method is not such simple implementation, it needs to be iterated the whole map to identify an object.

I donno how optimized it is to traverse in HashMap, TreeMap whatever map implementation has....

But still doable, I donno Why it is missing in JDK API ?

Even eclipse has dependency graph.Why it is building all the projects?

Scenario:

Project A, B and C is dependent on say X.jar. I am updating the X.jar where those files are only related to Project A. But eclipse builds all the three projects,if the jar gets updated.

Problem: Eclipse has all the dependencies graph(I believe) and why it is behaving like this?
If its build only project A then lot of time will be saved.

Worst case scenario will be when JDK changes (I am seeing this also as a JAR changes),so only the files which are compatiable with the latest versions and it dependencies shuld be built.

It should try for the incremental build . Any thoughts guys......

Escape Analysis in Mustang (Java SE 6)

Escape analysis
The Java language does not offer any way to explicitly allocate an object on the stack, but this fact doesn't prevent JVMs from still using stack allocation where appropriate. JVMs can use a technique called escape analysis, by which they can tell that certain objects remain confined to a single thread for their entire lifetime, and that lifetime is bounded by the lifetime of a given stack frame. Such objects can be safely allocated on the stack instead of the heap. Even better, for small objects, the JVM can optimize away the allocation entirely and simply hoist the object's fields into registers.
Escape analysis in Mustang
This analysis is an optimization that has been talked about for a long time, and it is finally here -- the current builds of Mustang can do escape analysis and convert heap allocation to stack allocation (or no allocation) where appropriate. The use of escape analysis to eliminate some allocations results in even faster average allocation times, reduced memory footprint, and fewer cache misses. Further, optimizing away some allocations reduces pressure on the garbage collector and allows collection to run less often. Escape analysis can find opportunities for stack allocation even where it might not be practical to do so in the source code, even if the language provided the option, because whether a particular allocation gets optimized away is determined based on how the result of an object-returning method is actually used in a particular code path.
Conclusion
JVMs are surprisingly good at figuring out things that we used to assume only the developer could know. By letting the JVM choose between stack allocation and heap allocation on a case-by-case basis, we can get the performance benefits of stack allocation without making the programmer agonize over whether to allocate on the stack or on the heap.

is all string manipulations requires synchronization?

The Java language specification assures us that strings are immutable, so most operations on a string destroy the original object and create a new one. But in reality the compiler can optimize the operation and reuse the same memory as the original string. For instance we have a string ‘String stringSample = "Saravanan";’ stored in memory at memory location m1. The compiler will store this String in memory as origin location = m1 and offset = 12.

Now when an operation ‘stringSample = stringSample.substring(4);’ is done, stringSample will contain "vanan".

As per the Java specification we would assume that stringSample will be moved to a new location m2 and the old memory location is left for the garbage collector, but compilers can reuse the same memory location and update the offsets. So the new string after the sub string operation would read as origin location = m1+4 and offset = 8. This does not break the Java specification, as the old reference is lost and a new reference is created with a new origin location and a new offset. The problem is when two threads try to access this string at the same time; the second thread might get the wrong starting location.

is this a java bug?

class ArrayTest{
public static void main(String arg[]) {
int a[]=new int[0];
a[0]=5;
}
}
It will compile fine,when I run this code,its saying ArrayIndexOutOfBoundException....
As we know array declaration should have one integer value,even if I give -1 also it will compile. But in runtime it is saying NegativeIndex or ArrayIndexOutOfBound for -1 or 0 respectivley.

Why it is doing like this? While doing compiling itself why don't the compiler has do that? I accept for the variable initialization since it has clue for the variable in the compilation time,but for straight forward initialization like above should caught by the compiler... is my understanding is wrong?