Counting Sort

Counting Sort is an integer sorting algorithm. It is not very famous when somebody talks about sorting algorithms but it is great when sorting integers. In fact, many a times it may even beat other Sorting Algorithms. The highlight of Counting Sort is that it creates a bucket array (to keep track of frequency of numbers) whose size is the maximum element in the provided array.

We are looking to compare most of the sorting algorithms to find out which one performs better under different circumstances. One of the ways is to compare the complexity for each algorithm. The other way is to compare how well they perform based on the input they are all provided. I will post my code on Github but will start with Counting Sort here.

Here are some pointers about Counting Sort:

• Linear sorting algo with O(n+k) when the elements range from 1 to k

  • On
    

• It is really good when the numbers range from 1 to n which means the max between them is not going to be very high

How do we compare all Sorting Algorithms?

We are going to look at the following scenarios across all Sorting Algorithms:

• 10 numbers - Random + Sorted

• 1000 numbers (1K) - Random + Sorted

• 1,000,000 numbers (1M) - Random + Sorted

• 20000 iterations for each one of these scenarios

• For good measure we will look at the average time required to sort 100 numbers in each one of these cases

  • This will allow us to compare all algorithms against each other by looking at the average times

  • It means we will be multiplying the results of 10 numbers by 10 (to get the “average” for 100 numbers) and also

Machine Setup

The setup of my machine is as follows:

| Hardware: x86_64 | Processor: 16 x Intel® Xeon® E5540 2.53 GHz | Compiler: gcc version 4.8.2 (GCC) | Redhat Version: Red Hat 5.3

The Source Code

I am trying to do this all together in a single place so that it is easy for anybody to pick up the code, either for their own testing or going through the Sorting Algos. All of the source code for this can be found here:

https://github.com/abhi1010/Algorithms

Numbers

Without further ado, let’s delve into the numbers for Counting Sorts. Here’s the result from the code:

Visual Studio 2008 crashes while adding items

Had this problem cropping up since months where I was trying to add items to Visual Studio 2008 Toolbox and it kept crashing.

Finally got a work around, you should start it in safe mode. Here’s the procedure:

devenv /safemode

Then use Choose Items on toolbox and run through each of the tabs. Once you accept any exceptions raised on loading controls, you can then open Visual Studio normally and add items.

The reason for this has to be pretty simple - I have installed way too many beta/refresh version on Visual Studio 2008, something had to give up. I can’t really complain.

Google Analytics & SWFAddress

Recently found a bug slash issue with Google Analytics new javscript software (post-urchin v5). I had written the internal documentation for the company standards and somehow when those standards were put into practice, SWFAddress feature of flash stopped working the moment google analytics feature was enabled. Worst of all, the web pages failed to load! To cap it off, the website was working perfectly fine on Firefox 2, 3 and IE 7!! It was having trouble only on IE6.

I tried a lot of ways but none seem to worked. Finally found a blog that remotely talked about SWFAddress!

Well, the problem turns out that SWFAddress uses ExternalInterface.call() instead of getUrl() function internally and they don’t go well together if used together.

The solution was simple, since flash is using SWFAddress feature, every getUrl should be replaced with ExternalInterface.call(). Needless to say, everything seemed perfect again.

Full Trust on Mapped Drive

Sometimes, when opening a web project from another mapped drive (not your own computer’s hard disk) Visual Studio may complain something like this:

The project location is not trusted.

Running the application may result in security exceptions when it
attempts to perform actions which require full trust.

The problem here is that .Net does not want to fully adhere to all security policies as your hard disk to this mapped drive as well as it does not know what kind of data it might have. If you want it to fully trust this mapped drive then you will have to use caspol for this purpose. Here’s how it is done:

c:\>caspol -q -machine -addgroup 1 -url file://W:/* FullTrust -name "W Drive"

Once this new code group is in place, any new .NET processes you start will give any assemblies on the W drive full trust.

Tag your namespaces

Recently discovered a nifty little feature on .Net and though of sharing it.

You can tag an assembly by giving it a name and then use this name throughout your class to access the classes inside this namespace.

<span style="color:#0000ff;">using</span> asp=CompanyName.Data;

Now all the classes inside CompanyName.Data namespace can be accessed using the name asp (as if it was an instance of the namespace).

One thing to note, however, is that the classes inside this namespace cannot be accessed directly and the word “asp” has to be used.

Let’s see an example to understand it.

This function, btw, is going through a namespace called Company.AspFunctions and we give it a tag asp to access all classes under it by its tag instead. Date_Format() fn is a static function inside Conn Class. Basically it takes your “asp style” datetime strings and returns you the correct date in yyyyMMdd format.

How to protect from SQL Injections in ASP.NET

Some good links to figure out how to save your code’s ass from being thrashed by SQL Injections

http://msdn2.microsoft.com/en-us/library/ms998271.aspx#paght000002_step2

http://msdn2.microsoft.com/en-us/library/bb355989.aspx#paght000003_step4

Creating Custom Web Controls

How do you extend a control? Let’s figure it out.

Why would you want to extend existing controls?

Because some functionality may not exist exactly as you may need it. For example, let’s take up ImageButton control example. It is a great control but it falls short when it comes to real world scenario. Mostly websites do a hover image clickable button where the text or background color of the button changes once you hover your mouse over it.

How to Extend?

_I assume that you use C# code but there is not going to be any difference even if you wanted to do in VB.Net. _

Create a project for creating custom web control library. It automatically includes a C# class that says something like

<span style="color:#0000ff;">public</span> <span style="color:#0000ff;">class</span> WebCustomControl1 : WebControl

Now ask yourself, what do you want to extend? A GridView? Replace WebControl with GridView. Let’s follow our example with Hover Image Button Control. If you recall .Net already has ImageButton control that accepts one url for the image to be shown for that button, let’s extend that one to include two Images rather than just one. In that case I would replace WebControl with ImageButton since I am going to extend ImageButton control. Let’s call it HoverImageButton. Hence, the line changes to some thing like this:

<span style="color:#0000ff;">public</span> <span style="color:#0000ff;">class</span> HoverImageButton : ImageButton

The class also includes a property called Text for you so that you can see that and figure out how to use properties in custom web controls. It also includes attributes that start off just before the property itself. It is used by Visual Studio for showing this property on Properties pane. It is definitely a very useful feature.

You can change this property to anything you like. Since we are creating a HoverImageButton control we want a property to save another url for the hover image’s source. Let’s change Text to “ImageHoverUrl”. ImageButton already has a property called “ImageUrl” and it belongs to “Appearance” group in Visual Studio Properties window. Notice the similarity in “ImageHoverUrl” and ImageUrl so that they appear together in Properties window. Sometimes, little deeds go a long way.

Writing JS file

Now let’s add a javascript file to the project. Add one function called “ShowImageHoverButton()” that takes in two parameters, the control’s id and the new image to be shown for that control. The control image’s source is changed everytime when this function is called. We can call this function on mouse out and on mouse over events.

That’s all you need to do for this control.

Linking JS and Custom Control them together

This is a very simple process. You have the javascript file and you know for sure that the control will be loaded into the webpage, so you need a mechanism inside the control so that you can tell that “hey, include this javascript file whenever you have this control on a page”.

This is how you do that.

Please note that the name of the javascript file is “HoverImageButtonJS.js”. ExtendedControls is the name of the project/assembly that I have created for this custom web control.

How to assign javascript functions to the control?

Now the next problem is how would you tell the control that call this javscript function function on “mouseover”? We use OnInit function for this process. We override the function and make use of the control’s Attributes property.

What is Attributes property for anyway? Well, it adds any extra “property” or “style” that you may want to add to the control when it is rendered to the client.

Let’s see how that’s done.

Over here, I have told the class to include "onmouseover=ShowImageHoverButton(this, 'IMAGE_SOURCE')" as a property.

This is how it is rendered on the client browser:

Add the javascript file also to the AssemblyInfo.cs class

For the control library to properly include the js file, you have to add the js file in AssemblyInfo.cs class as well. This is how it is done:

[assembly: WebResource(<span style="color:#006080;">"ExtendedControls.HoverImageButtonJS.js"</span>, <span style="color:#006080;">"text/javascript"</span>)]

Test Drive!

That’s all. A few simple steps and your control is ready to be tested. Still, let’s not rush and see the steps required:

• Add this control’s library to any web project.

• Register the dll on web.config. This makes the control available automatically on all the pages.

• Go to the design view of any page. Open up the Toolbox pane and you will automatically see the name appear “HoverImageButton”. Double click and you are ready to go!!

Easy as it may sound but it may not be that smooth a ride for you.

Just take care of few pointers and you should be fine. Here they go:

• The JScript file that you have added sometimes doesn’t get linked properly to the control. Right click on the js file and check it’s properties. It’s compile action should be “Embed Content” rather than anything else. That way everytime you compile this control, this js file gets “embedded” into the control’s library.

• Take care of the naming convention for the js file.

  • If your control’s namespace is ExtendedControls, then while “Registering” it in the control’s class you should give the JS file’s name as “ExtendedControls.CustomControl_JS.js” where “CustomControl_JS.js” is the name of the javascript file. Basically, another shortcut to learn it is whatever is the name of the project/assembly that you are creating, you have to append that name before the file name. **Follow this logic strictly, otherwise you will be left high and dry. **
    
    

• You should also remember to register this name inside AssemblyInfo.cs class (“ExtendedControls.CustomControl_JS.js” as per our example here).

• If you want Visual Studio Design support then remember to add the attributes that define where can you see the custom properties of this control in the “Properties” pane.

• Whenever you are putting your code files inside some folder, try to keep the JS files in the root folder.

  • When I tried putting them inside the folder it did not work, i took them out to the root folder and it worked instantly. I have not tried changing the JS file names but I am sure you can figure out some solution.

Here’s all the code in case somebody needs it:

StringBuilder vs String joins

For those who do not want to waste their time, here’s the gist for this whole article: StringBuilder performs better but you should try to use it when there’s lot of concatenation involved (normally more than 7 joins - start thinking about StringBuilder.

Let’s move on for the lesser mortals. There has been a lot of debate about using StringBuilder instead of adding string like

<span style="color:#606060;">   1:</span> strVariable += <span style="color:#006080;">" Add this string to my variable string"</span>;

What’s the darn difference?

If you remember your schooling concepts string objects are fixed, their values cannot be changed. So, how can you change the value of a string? Well, you do NOT change the value, you change the object altogether! Every time you assign a value a new object of type string is created with the given value and is returned to you. hence, you discard the old string and actually come up with a new string.

On the other hand, when you use StringBuilder, it is the same object, that you are working on. It keeps appending to the same object and the heap is not changed. Then why don’t you use it always? Because there are “appending” costs. Everytime you append something, it is checked against the buffer and if it falls short of space needed, a new buffer is allocated. Let’s see how that works inside the dll:

How about some proof?

Fortunately somebody did the hard work for all of us and actually came up with the statistics. You can find all of that over here:

http://www.heikniemi.net/hc/archives/000124.html

Blogs I like

Two blogs i really like and follow many a times are:

SqlAuthority.com - Excellent blog for Sql Server 2005. The guy has a very in-depth knowledge of Sql Server and I appreciate the way

Scott’s Blog - Another great blog where Scott Guthrie talks quite a bit about ASP.NET and tells the latest details coming in from Microsoft.

Just today I found another interesting blog. This guy talks about the interesting aspects in programming.

http://blogs.msdn.com/ericlippert/default.aspx

http://blogs.msdn.com/brada/

Following is an interesting link that talks about a lot of topics.

http://weblogs.asp.net/scottgu/archive/2008/01/24/jan-24th-links-asp-net-asp-net-ajax-visual-studio-net-iis.aspx

Recursively read directories and list all files under it