Thursday, July 22, 2010

Factorial Function in C#

 The Factorial Function is a classic interview question. It opens the doors to a discussion about stack overflow (if done recursively) and integer overflow (if the param is too large) as well as discussions around how to handle and catch errors.

Here is one way to do it using recursion:

static Int64 Factorial(int factor)
{
    if (factor > 1)
    {
        return factor * Factorial(--factor);
    }
    return 1;
}

Here is another way to do it using a loop: 

static Int64 Factorial(int factor)
{
    Int64 factorial = 1;
    for (int i = 1; i <= factor; i++)
    {
        factorial *= i;
    }
    return factorial;
}

Neither function does any sanity checks for input (e.g. >= 1) and assumes that we're looking for a factorial of 1 or greater.

There's a third and much better way to do factorials if you are going to use them in code that needs to be optimized. In fact I can't think of a reason why you wouldn't want to use the following method. If you are calculating an Int64 factorial then the maximum factor that you can calculate it for is 20. After that it will overflow the Int64 type. If you are calculating an Int32 factorial then the highest you can go is 12. 

static Int64[] factors64 = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
1307674368000, 20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000 };
 
static Int64 Factorial(int factor)
{
    return factors64[factor];
}

The tests that I ran showed the recursive factorial function to run 14 times slower than the array lookup and the loop to run 5 times slower.

Friday, July 9, 2010

Google AdSense Best Day Of Week

I've just been doing some Google AdSense analysis for some web sites that have moderate traffic. The owner said that I can publish this bit of information from her site. She's interested to hear if other AdSense publishers have had similar results.

The objective was to find out which day of the week the Cost Per Click (CPC) was the highest. So we ran the averages across a number of pages and the average CPC by day of week ranked the days in order from worst to best as follows:

  1. Monday
  2. Sunday
  3. Thursday
  4. Friday
  5. Wednesday
  6. Tuesday
  7. Saturday

Before running the analysis she was pretty certain that Tuesday was the best day of the week and was surprised to see that Saturday was in fact the best.

Monday, July 5, 2010

Parallel For and ForEach in .Net 4

I've started looking at the Parallel.For and Parallel.ForEach methods from .Net 4's Task Parallel Library. Before I use something as complex and potentially dangerous as this I like to test it out to make sure I'm going to get that performance boost before going down that path.




Here's the console app that I wrote to do the test:

static void Main(string[] args)
{
    int[] someInts = Enumerable.Range(0, 100).ToArray();

    Stopwatch timer = Stopwatch.StartNew();
    foreach (int item in someInts)
    {
        DoItem(item);
    }
    Console.WriteLine("Sequential: {0}", timer.Elapsed);

    timer.Restart();
    Parallel.ForEach(someInts, item => DoItem(item));
    Console.WriteLine("Parallel: {0}", timer.Elapsed);

    Console.ReadKey();
}

static void DoItem(int item)
{
    Random r = new Random((int)DateTime.Now.Ticks);
    for (int i = 0; i < (item * 100000); i++)
    {
        int j = r.Next(0, 10000);
        j = j * j;
    }
}


I ran this a number of times on a quad core machine (Intel Core2 Quad Q9400 @ 2.66GHz) on Windows 7 x64. Average time for the sequential loop was 14.7 seconds and for the parallel loop was 5.6 seconds for a ratio of 2.6 times faster using the parallel loop. This is seems right., you're going to get a loop like this to be about Core-1 times faster because the thread management will "cost" you one of your cores. So on an 8 core machine expect this loop to be 7 times faster and on a quad expect 3 times which is what I almost got.


Saturday, July 3, 2010

CREATE FILE encountered operating system error 5 Access is denied

I have an MSSQL 2008 R2 installation and was trying to attach a DB from a non-R2 installation using SQL Server Management Studio (SSMS) and I was getting the following error:

CREATE FILE encountered operating system error 5(Access is denied.) while attempting to open or create the physical file 'C:\Program Files\Microsoft SQL Server\MSSQL10_50.MSSQLSERVER\MSSQL\DATA\MyDataBase.mdf'. (Microsoft SQL Server, Error: 5123)

Found plenty of Google results pointing me to suggestions about SQL Server 2000 and 2005 with instructions on how to add user permissions and which user account needed to be added.

Turned out that all I needed to do was to run SSMS as an administrator and the attach worked.