Friday, July 29, 2011

Optimizing use of page persisted properties by using session variables and local pointers

You have a variable that needs to be persisted between postbacks. How do you do this?
Your first instinct might be to use static variables. This is WRONG!

I am maintaining (and fixing lots of bugs) a website where I discovered that almost every page had a big bug in it. The following is what's wrong:

In Page class
protected static Account acct = new Account();

The problem is when multiple people are currently on this page, when Person1 sets fields in acct, it's going to change Person2's acct field too. This is because it's declared as static, which means it's shared between all instances of the page class!

So how do you handle this? Simple, use the Session variable like this:

//First create a const string that represents the location in Session
private const string SESSION_ACCT = "PAGENAME_ACCT";
//Now create a property that looks in the Session and creates a new object if it's
//not found
protected Account part
{
get
{
Account ad = null;
if (Session[SESSION_ACCT] == null)
{
ad = new Account();
Session[SESSION_ACCT] = ad;
}
else
ad = (Account)Session[SESSION_ACCT];
return ad;
}
set
{
Session[SESSION_ACCT] = value;
}

}

You will most likely want to populate the acct variable during page load. This is assuming you're pulling the account id out of QueryString and that you have a data access layer class called AccountDB with the method Account GetAccount(Guid AcctId).

protected void Page_Load(object sender, EventArgs e)
{
if (!Page.IsPostBack)
{
acct = AccountDB.GetAccount(new Guid(Request.QueryString["id"]));
}
}

This is simply going to the acct property's set method. So it's going to do Session[SESSION_ACT] = AccountDB.GetAccount(new Guid(Request.QueryString["id"]));

Here's how you use acct

public void showAccountDetails()
{
Account localAcct = acct;
txtName.Text = localAcct.Name;
txtCreated.Text = localAcct.Created;
}

Why did I use Account localAcct instead of just using acct? This is because using acct means calling the getter everytime. So the above code would make two calls to the getter, meaning it runs through this code twice:
get
{
Account ad = null;
if (Session[SESSION_ACCT] == null)
{
ad = new Account();
Session[SESSION_ACCT] = ad;
}
else
ad = (Account)Session[SESSION_ACCT];
return ad;
}
This is alot more expensive than just creating a local pointer and directly accessing the fields. Every time it calls the getter it's going to be pulling out of Session and converting to Account. Whereas creating Account localAcct means you're storing the result of acct's getter in a local pointer and then directly accessing its fields.

Wednesday, July 27, 2011

Refactoring data access layer

I refactored a highly used data access layer method and achieved 50% reduction in lines of code, 20% reduction in execution time, and increased readability and error checking.

Optimizations:
1. Combined several separate SQL statements into one long statement with multiple joins. This reduces the number of trips to the SQL Server.

2. Former code was using multiple separate try catch blocks to test for null values in the output. I removed all of these and replaced them with ISNULL in the sql statement.

3. Moved SQL statement to a stored proc instead of building a big statement in the code. This reduces the amount of data traveling over the network, because I'm only passing in the stored proc's name, and reduces execution time because stored procs are compiled and reused, as opposed to rebuilding a command text string every execution

4. Instead of doing "if (statement) boolval = true else boolval = false; I did boolval = statement instead. This is a readability issue more than anything.

Thursday, July 21, 2011

String.Format formatting options in C#

Found a good site for this here: http://www.dijksterhuis.org/formatting-strings-stringformat/


Here's a trivial example showing the difference between Java and C#:

Java:
String.Format("Hello %s", "World");

C#:
String.Format("Hello {0:G}", "World");

Wednesday, July 20, 2011

Geolocation with SQL Server 2008 and geocoding an address

Let's say you have a mobile app / website and you want to allow the user to search for whatever within X miles. To find the distance between two points, you first need the coordinates of the two points.

If you're using a device that has GPS, this is easy. It's just a call to the system API or whatever. If you're using a website that asks the user for their address then you need to do something called geocoding. Luckily there are several web services available to do this for you. So on your website, if you were using Google's web service, you would use this javascript:
        function btnGeocode_onclick() {
            var geocoder = new google.maps.Geocoder();
            var address = document.getElementById("txtAddress").value;
            geocoder.geocode({ 'address': address },
            function(results, status) {
                if (status == google.maps.GeocoderStatus.OK) {

                    document.getElementById("txtGeolocation").value = results[0].geometry.location;
                }
                else {
                    document.getElementById("lblResults").value = status;
                }
            }

            );
        }

What this does is takes the address in the txtAddress TextBox, and then puts the coordinates of that address in the txtGeolocation TextBox.

So now you have the points, now you need a way to determine the distance between two points. Well, this is really easy with SQL Server 2008, using the new geography data type.

So first, here's how you would insert the coordinates into the database:
latlong is type geography

INSERT INTO [test]
           ([latlong])
     VALUES
(geography::Point(37.7926969,  -122.405512, 4326))


Next, get all whatevers that are within 2 miles of (37.7926969, -122.405512)
For this you use the STDistance function, creating a geography point from a passed in value (37.7926969, -122.405512)

SELECT latlong.STDistance(geography::Point(37.7926969,  -122.405512, 4326))/1609.344 as [miles] FROM test
WHERE latlong.STDistance(geography::Point(37.7926969,  -122.405512, 4326))/1609.344 < 2
ORDER BY lat.STDistance(geography::Point(37.7926969,  -122.405512, 4326))


Saturday, July 16, 2011

File IO and bit counting

I made this problem up to practice doing file IO, bit manipulation, and using data structures.

Problem:
1. Generate a file where each line is a random integer
2. Read the file
3. For each line count the number of set bits (1's) in the integer, and order the output in ascending order of most bits set.

Example:
File=
4
1
6
2
1
5
1
7
0
6


Output should be this:
-------------
Ones=0
0
-------------
-------------
Ones=1
4
1
2
1
1
-------------
-------------
Ones=2
6
5
6
-------------
-------------
Ones=3
7
-------------

Solution


In Main
       int[] arr = getRandomArray(10);
       String fileName = "D:/Test/BitManip.txt";
       FileIO.Write(fileName, arr);
       FileIO.OrderByNum1s(fileName);

In FileIO.java
public class FileIO {

    public static void Write(String fileName, int[] arr)
    {
        try
        {
           BufferedWriter bw = new BufferedWriter(new FileWriter(new File(fileName)));
           for(int i = 0; i < arr.length; i++)
           {
               bw.append(String.valueOf(arr[i]));
               bw.newLine();
           }
           bw.close();
        }
        catch(IOException io)
        {
            System.out.println(io);
        }
       
    }
    public static void OrderByNum1s(String fileName)
    {
        try
        {
            BufferedReader br = new BufferedReader(new FileReader(new File(fileName)));
            Integer i = 0;
            TreeMap<Integer, ArrayList<Integer>> tree = new TreeMap<Integer, ArrayList<Integer>>();
            String input = null;
            while((input = br.readLine()) != null)
            {
                i = Integer.parseInt(input);
                int count = countOnes(i);
                if(!tree.containsKey(count))
                {
                    ArrayList<Integer> numList = new ArrayList<Integer>();
                    numList.add(i);
                    tree.put(count, numList);
                }
                else
                {
                    tree.get(count).add(i);
                }
                   
            }
            br.close();
            ArrayList<Integer> ints = new ArrayList<Integer>();
            for(Map.Entry<Integer, ArrayList<Integer>> entry : tree.entrySet())
            {
                System.out.printf("-------------\nOnes=%d\n", entry.getKey());
                for(Integer k : entry.getValue())
                    System.out.println(k);
                System.out.printf("-------------\n");
            }
           
        }
        catch(IOException io)
        {
            System.out.println(io);
        }
    }
    private static int countOnes(Integer i)
    {
        int count = 0;
        for(int j = 0; j < Integer.SIZE; j++)
        {
            int bitmask = 1<<j;
            if((bitmask & i.intValue()) == bitmask)
                count++;
        }
        return count;
    }
}
 

Friday, July 15, 2011

Sort algorithm implementations and comparison

I implemented several sorting algorithms: bubble, insertion, selection, bucket, quick, and merge. I generated a random int[] and passed it to each sort. The sorts first created a local copy of the array, and then performed sort. I used NetBeans profiler on various input sizes to compare the speeds.


Comparison from NetBeans profiler
1. Elements =  1,000, Variation = 100,000,000

2. Elements = 10,000, Variation = 100,000,000







3. Elements = 100,000 Variation = 100,000,000, I left out Selection() and Bubble() because they were so much worse than the others that they made it hard to see the results





4. Elements = 100,000 Variation = 10,000




Conclusion
Timewise, with large variation in the data Quicksort is the fastest, while with small variation Bucketsort is the fastest. Spacewise, Insertion/Selection/Bubble are all better, whereas Quick/Merge recurse, therefore creating a tree in memory, meanwhile Bucket sort creates an extra array for the buckets, whose size depends on the variation in the data. So when choosing which sort algorithm to use you should compare time and space complexity based on your expected # elements and variation in data values.


Implementation

In Main
       int[] arr = getRandomArray(1000);
       Sorts s = new Sorts(arr);
          s.Merge();
          s.Quick();
          s.Selection();
          s.Insertion();
          s.Bubble();
          s.Bucket();
In Sorts.java
public class Sorts {
    private int[] arr;
    public Sorts(int[] arr)
    {
        this.arr = arr;
    }
  
    public int[] Insertion()
    {
        int[] a = copy();
      
        for(int i = 1; i < a.length; i++)
        {
            int tmp = a[i];
            int j = i - 1;
            while(j >= 0 && a[j] > tmp)
                a[j + 1] = a[j--];
            a[j + 1] = tmp;
        }
        return a;
      
    }
    public int[] Selection()
    {
        int[] a = copy();
        for(int i = 0; i < a.length; i++)
        {
            int minIdx = i;
            for(int j = i + 1; j < a.length; j++)
            {
                if(a[j] < a[minIdx])
                    minIdx = j;
            }
            int tmp = a[i];
            a[i] = a[minIdx];
            a[minIdx] = tmp;
        }
        return a;
    }
    public int[] Bubble()
    {
        int[] a = copy();
        for(int i = 0; i < a.length; i++)
        {
            for(int j = 0; j < a.length - 1; j++)
            {
                if(a[j] > a[j + 1])
                {
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                }
            }
        }
        return a;
    }
    public int[] Bucket()
    {
        /*
         * Create a bucket array with minimized number of
         * buckets, which is Minimum Value to Maximum Value
         * use the minimum value as an offset
         *
         * For example,
         * [8][5][3][4][7][3][6][4][5][6]
         * min = 3, max = 8
         * So at most we need 6 buckets (8 - 3 + 1 = 6)
         * and 3 is the offset, so every value is stored in Value - 3
         *
         */
        int[] a = copy();
      
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int m = 0; m < a.length; m++)
        {
            max = Math.max(max, a[m]);
            min = Math.min(min, a[m]);
        }
        //Create bucket with minimized number of buckets
        int[] buckets = new int[max - min + 1];
      
        //Put integers into buckets
        for(int i = 0; i < a.length; i++)
            buckets[a[i] - min]++;
      
        //output the buckets
        int index = 0;
        for(int b = 0; b < buckets.length; b++)
        {
            for(int k = 0; k < buckets[b]; k++)
            {
                a[index++] = b + min;
            }
        }
        return a;
    }
    public int[] Merge()
    {
        int[] a = copy();
        mergesort(a, new int[a.length], 0, a.length - 1);
        return a;
    }
    private void mergesort(int[] a, int[] helper, int left, int right)
    {
        if(left >= right)
            return;
        int mid = (left + right)/2;
        mergesort(a, helper, left, mid);
        mergesort(a, helper, mid + 1, right);
      
        //merge results
        int leftPos = left,
                leftEnd = mid,
                rightPos = leftEnd + 1,
                rightEnd = right,
                tmpPos = left;
        while(leftPos <= leftEnd || rightPos <= rightEnd)
        {
            if(leftPos <= leftEnd && rightPos <= rightEnd)
            {
                if(a[leftPos] < a[rightPos])
                    helper[tmpPos++] = a[leftPos++];
                else
                    helper[tmpPos++] = a[rightPos++];
            }
            else if (leftPos <= leftEnd)
                helper[tmpPos++] = a[leftPos++];
            else
                helper[tmpPos++] = a[rightPos++];
        }
        //copy back into a
        for(int i = left; i <= right; i++)
            a[i] = helper[i];
      
    }
    public int[] Quick()
    {
        int[] a = copy();
        quick(a, 0, a.length - 1);
        return a;
    }
    private void quick(int[] a, int left, int right)
    {
        int pivot = (left + right)/2;
        int pivotVal = a[pivot];
        int i = left;
        int j = right;
        while(i <= j)
        {
            while(a[i] < pivotVal)
                i++;
            while(a[j] > pivotVal)
                j--;
            if(i > j)
                break;
            int tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
            i++;
            j--;
          
        }
        if(left < i - 1)
            quick(a, left, i - 1);
        if(right > i)
            quick(a, i, right);
      
    }
    private int[] copy()
    {
        int[] copyarr = new int[arr.length];
        System.arraycopy(arr, 0, copyarr , 0, arr.length);
        return copyarr;
    }
    public boolean same(int[] a, int[] b)
    {
        if(a.length != b.length)
            return false;
        for(int i = 0; i < a.length; i++)
        {
            if(a[i] != b[i])
                return false;
        }
        return true;
    }
}

Learning Integration Services

Follow this tutorial:
http://msdn.microsoft.com/en-us/library/ms169917.aspx

Gotchas
1. If your server instance isn't the default then you'll need to update the ODBC connection in every lesson. It's set to by default, which points to the default (unnamed) instance of SQL
2. In lesson 3 where you create a package configuration, make sure to keep two variables, one for folderName and one for fileName. FolderName is pulled out of the XML config file, while the filename is gotten by traversing the folderName.

Wednesday, July 13, 2011

Graph, Path, Node, and Edge classes in Java, along with algorithms

I created Graph, Path, Node, and Edge classes for playing around with graph algorithms. I didn't use best practices when designing the access etc... example: Node's members are all public. This is strictly for learning purposes!

Note: I forgot to escape the generic left/right brackets in LinkedList, so it's not showing up here. Add them if you're gonna use them

In Graph.java
public class Graph {
    private class Path implements Cloneable
    {
        GNode start = null;
        LinkedList edges = new LinkedList();
        private int weight = 0;
        public Path(GNode start)
        {
            this.start = start;
        }
        public void AddEdge(GEdge e)
        {
            weight += e.weight;
            edges.add(e);
        }
        @Override public String toString()
        {
            StringBuilder sb = new StringBuilder(1 + edges.size() * 2);
            sb.append("(" + start.data + ")");
            
            for(GEdge e : edges)
                sb.append(String.format("-%d->(%s)", e.weight, e.n.data));
            sb.append(" total weight=" + weight);
            return sb.toString();
        }
        @Override public Object clone() throws CloneNotSupportedException
        {
            Path p = new Path((GNode)start.clone());
            p.edges = (LinkedList)edges.clone();
            p.weight = this.weight;
            return p;
        }
    }


    
    public LinkedList nodes = new LinkedList();
    private Path searchPath = null;
    public void DFS(int value)
    {
        
        if(nodes.isEmpty()){
            System.out.println(
        "No nodes exist");
            return;
        }
        searchPath = null;
        DFS(value, nodes.getFirst(), new Path(nodes.getFirst()));
        System.out.println(searchPath.toString());
    }
    private void DFS(int value, GNode cur, Path curPath)
    {
        if(searchPath != null)
            return;
        if(value == cur.data)
        {
            searchPath = curPath;
            return;
        }
        else
        {
            for(GEdge e : cur.adjacent)
            {
                try{
                Path newPath = (Path)curPath.clone();
                newPath.AddEdge(e);
                DFS(value, e.n, newPath);
                }
                catch(CloneNotSupportedException c)
                {
                    System.out.println(c);
                    return;
                }
            }
        }
    }
    public void BFS(int value)
    {
    }
    public void Dijkstra(int fromVal, int toVal)
    {
    }
    
}

In GNode.java
public class GNode implements Cloneable
{
    public int data = 0;
    public boolean visited = false;
    public LinkedList adjacent = new LinkedList();
    public GNode(int data)
    {
        this.data = data;
    }

    @Override
    protected Object clone() throws CloneNotSupportedException
    {
        GNode gnode = new GNode(this.data);
        gnode.adjacent = (LinkedList)this.adjacent.clone();
        gnode.visited = this.visited;
        return gnode;
    }
    
}
In GEdge.java
public class GEdge implements Cloneable
{
    public int weight = Integer.MIN_VALUE;
    public GNode n = null;
    public GEdge(int weight, GNode N)
    {
        this.weight = weight;
        this.n = N;
    }
    @Override public Object clone() throws CloneNotSupportedException
    {
        GEdge gedge = new GEdge(this.weight, (GNode)this.n.clone());
        return gedge;
        
    }
}
 
Example of building a graph and running depth-first search for an element
public static void main(String[] args) {
        Graph g = new Graph();
        GNode node1 = new GNode(1);
        GNode node2 = new GNode(2);
        GNode node3 = new GNode(3);
        GNode node4 = new GNode(4);
        node1.adjacent.add(new GEdge(2, node3));
        node1.adjacent.add(new GEdge(1, node2));
        node2.adjacent.add(new GEdge(2, node3));
        node3.adjacent.add(new GEdge(3, node4));
        node4.adjacent.add(new GEdge(1, node1));
        g.nodes.add(node1);
        g.nodes.add(node2);
        g.nodes.add(node3);
        g.nodes.add(node4);
        g.DFS(3);
        
    }
This will print out: (1)-2->(3) total weight=2

Tuesday, July 12, 2011

Mergesort in Java

private static void mergesort2(int[] arr, int[] helper, 
int left, int right)
    {
        if(left < right)
        {
            int center = (left + right)/2;
            mergesort2(arr, helper, left, center);
            mergesort2(arr, helper, center + 1, right);
            int rightPos = center + 1;
            int tmpPos = left;
            int i = left;
            while(left <= center || rightPos <= right)
            {
                if(left <= center && rightPos <= right)
                {
                    if(arr[left] < arr[rightPos])
                        helper[tmpPos] = arr[left++];
                    else
                        helper[tmpPos] = arr[rightPos++];
                }
                else if (left <= center)
                    helper[tmpPos] = arr[left++];
                else
                    helper[tmpPos] = arr[rightPos++];
                tmpPos++;
            }
            for(; i <= right; i++)
                arr[i] = helper[i];
            
        }
    }

Friday, July 1, 2011

Generate scripts for multiple databases for the same table

Problem:
How do you delete the same table and stored procs from a bunch of different databases all in one instance? For example, we have 100 companies in an organization, and we install our product on a per company basis. If we have 20 tables for our product and it's installed on every database, we have 2000 tables to delete. There's no way I'm doing this by hand! *Note: We can't just delete the database, because our product is only a module within a larger system containing multiple products.I did this with some vicious looking SQL. For each company database it executes dynamic SQL creating a cursor on dynamic SQL statements for dropping tables. The reason i'm dynamically creating cursors is because they have to be in the context of the company database. This has to be dynamic SQL otherwise i'd have to know the name of the database beforehand, and remember how I have 100 companies? Yeah, definitely not going to do 100 different use statements by hand.

Solution:


USE <SharedSystemDatabase>
DECLARE @dbName varchar(500), @sql varchar(500), @dropTbl varchar(500)
--Get all company databases + system database
DECLARE DBs CURSOR FOR
SELECT INTERID FROM SY01500 UNION SELECT '<SharedSystemDatabase>'
OPEN DBs

WHILE 1=1
BEGIN
FETCH NEXT FROM DBs INTO @dbName
IF @@FETCH_STATUS != 0
BREAK
--Generate drop statements for all this DB's specified tables
SET @sql =
'USE ' + @dbName +
' DECLARE tbls CURSOR FOR SELECT ''USE ' + @dbName + ' DROP TABLE ['' + TABLE_NAME + '']'' FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_NAME LIKE ''<Our Product Tables System-unique Prefix>%'''
EXEC(@sql)
OPEN tbls

WHILE 1=1
BEGIN
FETCH NEXT FROM tbls INTO @dropTbl
IF @@FETCH_STATUS != 0
BREAK
print(@dropTbl) -- Change this exec(@dropTbl)
END
CLOSE tbls
DEALLOCATE tbls


--Notice, the loop is unrolled. This is because it would've been a pain to try to concat @sql even --more than it already is
SET @sql =
'USE ' + @dbName +
' DECLARE tbls CURSOR FOR SELECT ''USE ' + @dbName + ' DROP PROCEDURE ['' + SPECIFIC_NAME + '']'' FROM INFORMATION_SCHEMA.ROUTINES WHERE SPECIFIC_NAME LIKE ''zDP_
Our Product Tables System-unique Prefix%'''
EXEC(@sql)
OPEN tbls

WHILE 1=1
BEGIN
FETCH NEXT FROM tbls INTO @dropTbl
IF @@FETCH_STATUS != 0
BREAK
print(@dropTbl) -- Change this exec(@dropTbl)
END
CLOSE tbls
DEALLOCATE tbls

END
CLOSE DBs
DEALLOCATE DBs
There was an error in this gadget