Thursday, March 22, 2012

Efficient Programming?

Hola!

What is an efficient program?

In a layman term - A program which does, what its "supposed to do", in a "fast" and "cheap" way...

A program can be very fast...

  • If we decrease the number of loops inside it
  • By choosing the "right data-structure" which can be used to efficiently manipulate the data, the program uses etc...


A program can be cheap...

  • If it consumes less memory (RAM space while it runs)
  • By using as less "Objects" as we can
  • Or by again using right data-structure


Ok... theory.. its always boring...  :-)

Lets jump on to solving an interesting problem... Take up a role of  Server-side Developer of a reputed website company, where the first task given to you is to validate the user password!

Here is the requirement -

You should reject a password if it contains a "repetitive sequence". A password is said to contain "repetitive sequence" if it has same sequence repeated one after the other (adjacent to each other).

Eg : 123123aaa (sequence "123" is repeated and adjacent), AbcAbczzsdkjksd, hhhsdsaBCDBCD are passwords with "repetitive sequence", where  passwords like 123abc123 (even though "123" is repeated, they are not adjacent), 12345678, abcdfgh are not.

And a sequence can be a word with at least 2 or more  distinct characters. For Eg: if 123abc123 is a password, then "12", "23, "3a" can be sequence of length 2, and "123", "23a", "3ab" can be sequence of 3 characters etc.


Once the requirement is understood.. You tend to develop a vague algorithm of your own!.. that's good...  then you start working on it.

Similarly I made my own vague thought and came up with following algorithm...

First -
      Let me start dividing my password into List of Sequences
Second -
     I use a Set to determine repetitive sequence

Fair enough... So I started coding... and came up with following listing -


public class DoubleSequenceCheck {


       // Method which generates distinct sequence out of my password string       
public List<String> getSequenceCombination(String pwd) {
List<String> list = new ArrayList<String>();
for(int i=0; i<pwd.length(); i++) {
for(int j= i+1; j<=pwd.length(); j++) {
if((j-i) > 1)
list.add(pwd.substring(i, j));
}
}
System.out.println(list);
return list;
}

       //Method which does Double Sequence check
public boolean containsDoubleSeq(String pwd) {
List<String> combi = getSequenceCombination(pwd);
Set<String> set = new HashSet<String>();
for(String s : combi) {
                        /*Here Set.add returns false, if theres already a sequence present inside it; hence, the pwd contains double sequence*/
boolean res = set.add(s);
if(res == false) {
return true;
}
}
return false;
}

public static void main(String [] args) {
DoubleSequenceCheck dc = new DoubleSequenceCheck();
dc.getSequenceCombination("AbcAbc1231234***");
}
}




Now, its time to Test... so I input - "123123aaa" - And my program returned "true" (saying yes the password contains repetitive double sequence)... Wow! nice...
Now I input - "123aaa123" (Expecting my program to return "false") and my program still returns "true".....

Since I am not keeping the track of "Index" of sequences, above program fails to find out "repetitive double sequence"  but it surely finds out "double sequence"...  fine.. let me fine tune it again....

Now when i think of storing "index" of a sequence along with the "sequence" itself - I can think of the data-structure called Map (a key, value pair holder)

Lets see the improvised version of my program "in making" ..  in the below listing...


public class DoubleSequenceCheck {


Map<String, Integer> map = new HashMap<String, Integer>();

public void getSequenceCombination(String pwd) {
map.clear();
for(int i=0; i<pwd.length(); i++) {
for(int j= i+1; j<=pwd.length(); j++) {
if((j-i) > 1) {
                 //Store the starting index of a sequence, along with the sequence
map.put(pwd.substring(i, j),i);
}
}
}
System.out.println(map.keySet());
}

public boolean containsDoubleSeq(String pwd) {
getSequenceCombination(pwd);
Set<String> set = new HashSet<String>();
for(String s : map.keySet()) {
boolean res = set.add(s);
if(res == false) {
return true;
}
}
return false;
}

public static void main(String [] args) {
DoubleSequenceCheck dc = new DoubleSequenceCheck();
System.out.println(dc.containsDoubleSeq("123em123"));
}
}


Now wait a minute, a Map's keys cannot be repeated, is there really a need of using Set again to check duplicates? Yeah! Set is redundant... lets remove it and do all stuffs using Map...

Also, make use of "Index" stored within Map to find-out the presence of repetitive sequence. The logic would be to calculate the difference in position of the 2 sequences.
If the difference  ==  the length of sequence
then they are adjacent to each other and hence are repetitive.

Eg:

If we consider a string array "123123ss"

and its index arranged as                         1  | 2 |  3 |  1 | 2 | 3 |  s |  s                    
                                                              0  | 1 |  2 |  3 | 4 | 5 | 6 |  7

Now the start index of first "123" sequence = 0 and the start index of next "123" sequence is = 3
The difference between indices = (3 - 0 )= 3 which is length of sequence "123".

Implementing all this in one method leads to a even more improved version of the program ....



public class DoubleSequenceCheck {


Map<String, Integer> map = new HashMap<String, Integer>();

public boolean containsDoubleSeq(String pwd) {
map.clear();
for(int i=0; i<pwd.length(); i++) {
for(int j= i+1; j<=pwd.length(); j++) {
if((j-i) > 1) {
String key = pwd.substring(i, j);
if(map.get(key) != null) {
int pos = map.get(key);
int len = i - pos;
if(len < 0) {
len = -(len);
}
if(key.length() == len) {
return true;
}
}
map.put(pwd.substring(i, j),i);
}
}
}
System.out.println(map.keySet());
return false;
}

public static void main(String [] args) {
DoubleSequenceCheck dc = new DoubleSequenceCheck();
System.out.println(dc.containsDoubleSeq("123ssBssB123em"));
}
}


Looks, good.. :-) and works fine too!

So, improvisation... yes.. the key to write efficient program is improvisation...

  1. Given an algorithm, first try to bring desired output. Don't worry about the efficiency, just try to create a solution.
  2. Once you have a solution, re-scan your program to check whether it contains redundant loops? redundant data-structure? unnecessary block of code which is delaying execution? - get rid of them!
  3. After each improvisation, do regression testing and repeat Step 2 until you see no scope for improvisation.


The above listing is not a perfect solution, and can be still improvised. Do leave a comment if you see any scope for improvisation.

Happy programming :-)



Thursday, February 23, 2012

GXT - ComoboBox with Multi select feature

Hi There! :-)

Its been a while since I am working on GWT(Google Web Toolkit) and its wrapper framework like ext-GWT (which is called as GXT) and have come across lots of new widgets and containers.

One recent feature request, I had to work on recently, which caught my attention was Mutli-Select ComboBox.

What does it mean ?
Its a ComboBox (a widget which will allow user to edit - as well as select values from multiple options it provides)

How its different from normal ComboBox?
Multi-ComboBox allows you to select multiple values from options (unlike normal combo which allows to select only one value at a time)

Now as I went on to analyse the implementation of this widget, I remembered a component from GXT called CheckBoxListView. Which is a list view comprising of CheckBox components. As I found this component perfect to select multiple values, I went on to integrate it with TriggerField.

I thought of creating a Dialog widget which will act as ComboBox "option provider" and reacts to the user click event on  TriggerField  to either hide OR show the options.

To create such kind of Dialog which looks like plain floating window, I set its properties as follows


checkBoxListHolder = new Dialog();
checkBoxListHolder.setClosable(false);
checkBoxListHolder.setHeaderVisible(false);
checkBoxListHolder.setFooter(false);
checkBoxListHolder.setFrame(false);
checkBoxListHolder.setResizable(false);
checkBoxListHolder.setAutoHide(false);
checkBoxListHolder.getButtonBar().setVisible(false);
checkBoxListHolder.setLayout(new FillLayout());



To integrate above Dialog with  TriggerField , make the Dialog respond to the click event on the  TriggerField overriding the following method was heplful,



        @Override
protected void onTriggerClick(ComponentEvent ce) {
super.onTriggerClick(ce);
checkBoxListHolder.setSize(getWidth(), 200);
listView.setWidth(getWidth());
checkBoxListHolder.setPosition(getAbsoluteLeft(), 
getAbsoluteTop() + getHeight());
if(checkBoxListHolder.isVisible()) {
checkBoxListHolder.hide();
}
else {
checkBoxListHolder.show();
}
}




Finally, add the CheckBoxListView component to the Dialog and now the Multi-Select ComboBox is ready to use!
             
                listView =  new CheckBoxListView();

       checkBoxListHolder.add(listView);

And it looks like...




Here is the complete code listing..


package com.ui.test.client;


import java.util.List;


import com.extjs.gxt.ui.client.data.ModelData;
import com.extjs.gxt.ui.client.event.ComponentEvent;
import com.extjs.gxt.ui.client.event.WindowEvent;
import com.extjs.gxt.ui.client.event.WindowListener;
import com.extjs.gxt.ui.client.store.ListStore;
import com.extjs.gxt.ui.client.widget.CheckBoxListView;
import com.extjs.gxt.ui.client.widget.Dialog;
import com.extjs.gxt.ui.client.widget.form.TriggerField;
import com.extjs.gxt.ui.client.widget.layout.FillLayout;
import com.google.gwt.user.client.Element;


public class MultiSelectComboBox<D extends ModelData> extends TriggerField<String> {


private Dialog checkBoxListHolder;
private CheckBoxListView<D> listView;
private ListStore<D> store;


private String delimiter = ",";
private boolean readOnly;




public MultiSelectComboBox() {
store = new ListStore<D>();
listView = new CheckBoxListView<D>();
}







@Override
protected void onTriggerClick(ComponentEvent ce) {
super.onTriggerClick(ce);
checkBoxListHolder.setSize(getWidth(), 200);
listView.setWidth(getWidth());
checkBoxListHolder.setPosition(getAbsoluteLeft(), 
getAbsoluteTop() + getHeight());
if(checkBoxListHolder.isVisible()) {
checkBoxListHolder.hide();
}
else {
checkBoxListHolder.show();
}
}








@Override
protected void onRender(Element target, int index) {
super.onRender(target, index);

checkBoxListHolder = new Dialog();
checkBoxListHolder.setClosable(false);
checkBoxListHolder.setHeaderVisible(false);
checkBoxListHolder.setFooter(false);
checkBoxListHolder.setFrame(false);
checkBoxListHolder.setResizable(false);
checkBoxListHolder.setAutoHide(false);
checkBoxListHolder.getButtonBar().setVisible(false);
checkBoxListHolder.setLayout(new FillLayout());
checkBoxListHolder.add(listView);
listView.setStore(store);


checkBoxListHolder.addWindowListener(new WindowListener(){


@Override
public void windowHide(WindowEvent we) {
setValue(parseCheckedValues(listView));
}


});


}








private String parseCheckedValues(CheckBoxListView<D> checkBoxView) {
StringBuffer buf = new StringBuffer();
if(checkBoxView != null) {
List<D> selected = checkBoxView.getChecked();
int index = 1, len = selected.size();
for(D c : selected) {
buf.append(c.get(listView.getDisplayProperty()));
if(index < len) {
buf.append(delimiter);
}
index++;
}
}
return buf.toString();
}


public CheckBoxListView<D> getListView() {
return listView;
}


public void setListView(CheckBoxListView<D> listView) {
this.listView = listView;
}


public ListStore<D> getStore() {
return store;
}


public void setStore(ListStore<D> store) {
this.store = store;
}


public String getDelimiter() {
return delimiter;
}


public void setDelimiter(String delimiter) {
this.delimiter = delimiter;
}


public boolean isReadOnly() {
return readOnly;
}


public void setReadOnly(boolean readOnly) {
this.readOnly = readOnly;
}




}


And it can be used from any part of your application like below example.. 

     public void onModuleLoad() {
MultiSelectComboBox<ModelData> combo1 = new MultiSelectComboBox<ModelData>();
combo1.getListView().setDisplayProperty("label");
combo1.getStore().add(getModelData());
combo1.setWidth(200);
RootPanel.get().add(combo1);
MultiSelectComboBox<ModelData> combo2 = new MultiSelectComboBox<ModelData>();
combo2.getListView().setDisplayProperty("label");
combo2.getStore().add(getModelData());
combo2.setWidth(300);
 
RootPanel.get().add(new Label("Multi-Select-Combo : "));
RootPanel.get().add(combo2);
}  
 
 
private List<ModelData> getModelData() {
List<ModelData> list = new ArrayList<ModelData>();
for(int i=0; i< 10; i++) {
ModelData m = new BaseModel();
m.set("label", "Label " + i);
list.add(m);
}
return list;
}
    



Share your comments and thoughts!... 

Tuesday, June 21, 2011

Mutual Exclusion among 2 different classes

Hello There!,

Recently I came across a very interesting problem, and the problem statement is as follows


There are 2 classes called A and B, with the methods - methodA() and methodB(). The class definition vaguely looks like this.

class A {


  public methodA() {
      statementA;
  }




}


class B {

    public methodB() {
         statementB;
   }
}

Now the 2 classes's methods contain a set of statements represented by statementA and statementB. Our goal here is to make these 2 statements in 2 different class, execute in a mutually exclusive manner. That means, when any thread executes statementA, none of the threads must be allowed to execute statementB. And when any thread executes statementB, none of the threads must be allowed to execcute statementA. Meanwhile, unlimited threads can simultaneously access statementA alone or statementB alone.


methodA and methodB can be changed in any form (making them synchronized or whatever). But method signatures are not allowed to be changed.




My Solution -

I thought of creating a new class - say Class C, which will have statementA and statementB, enclosed within 2 separates methods. These 2 methods will be static and synchronized.

class C {


   public static synchronized methodASync() {
         statementA;
   }




 public static synchronized methodBSync() {
         statementB;
   }


}

Now the call from methodA of Class A will be delegated to C.methodASync() and call from methodB of class B will be delegated to C.methodBSync().



class A {


  public methodA() {
      C.methodASync();

  }





}




class B {

    public methodB() {
         C.methodBSync();
   }
}


Since the methods in this class are static synchronized, any thread which executes any method of this class, first will try to acquire lock on this class and execute the methods. Now, when say thread1 executes methodASync none of the threads will be allowed to execute methodBSync or viceversa.

But there's one disadvantage. My problem says statementA; and statementB; should be executed in mutual exclusive manner, but it can allow multiple threads executing statementA at the same time. Since I am using Class level synchronization, even multiple calls to execute statementA/statementB happens synchronously.

Do you have a proper fail-safe solution?