Filip Ekberg's blog

April 23, 2010

Use Test Driven Development to verify that the code will Always work!

Filed under: .NET, C#, Programming — Tags: , , , — Filip Ekberg @ 1:51 pm

After attending Scandinavian Developer Conference in Sweden 2010 and attending the talk from Roy Osherove ( http://osherove.com/ ) Test Driven Development ( TDD ) has been something that I have tried to focus a bit more on.

Roy talks about some really important aspects of programming that should be printed into the programmers brain. I for instance is one of these people that like to verify everything that I do; Did I Really lock the door? So when I’ve turned the keys in the lock, I verify that the locking mechanizm worked and that the door is no indeed locked.

So what does my weird habbit have to do with TDD?

Driving the development with tests is not the only part of TDD; as with anything else there are a lot of people that like to think a lot of different things about this method. I like to think of tests as a way to Verify that my code runs as expected.

This is not a case of miss-trust!

Don’t missunderstand the above as see me as someone that does’t trust anyone or anything created by others than myself, that’s not the case. But by verifying that things runs properly, the door is properly locked I know that everything is OK from my part in the scenario.

What if I didn’t run the tests on the code and handed it over to the next developer that Did not in fact know that the method he works in affects everything else? And what if I didn’t verify the lock; I was in a big hurry and someone just went into the appartment and stole my TV?

In my opinion, test driven development is way to:

  • Verify that Code runs as it should
  • Decrease mistakes in the future
  • Help others gain knowledge of parts in the code faster

To take the locking mechanizm-checking even further and really turn it into something that is Driven you can follow these three very simple steps that Roy also talks about in his speeches:

  • Make it fail
  • Make it work
  • Make it better

How do you make the lock fail to lock? Well you simply Don’t lock it!

So let’s head over to the development aspect of this, you want to make your code fail? No code means it will fail right? When I do this step 1 and 2 always go together, especially when I demo TDD for co-workers or others. I will use the same good example as Roy used in his demo on SDC 2010, let’s try to put our heads around a simple Calculator project.

Defining the requirements

For this “project” we only have fourrequirements:

  • A method called Sum
  • This method parses a String
  • This method should return String.Empty when you pass Invalid or Empty data
  • Adds two integers in the String together “1 1″ would be 2

So if we follow the above we would end up with a test that looks like the following:

1
2
3
4
5
6
7
8
9
[TestMethod]
public void Sum_EmtpyString_ReturnsZero()
{
    var calculator = Calculator.GetInstance();
    var actual = calculator.Sum("");
    var expected = string.Empty();

    Assert.AreEqual(expected, actual);
}

Since we haven’t really implemented Calculator, GetInstance or Sum yet, we made it fail, there is no Code. Visual Studio helps us out a bit and makes the process a bit faster, by simply pressing alt + enter when selecting Calculator or Sum we can select to create the Class and create the Method Stub.

So we actually finished both Step 1 and Step 2 at the same time, even though Step 2 isn’t complete yet, we are nearly there!

Now we need to make it work, what is the simpliest way possible to make it work for the above test-case?

1
2
3
4
public string Sum(string input)
{
    return string.Emtpy();
}

This will actually work and it will indeed check this test as Passed. But it’s not really what we want. So how do we proceed?

Another Great point Roy pointed out is that, if there isn’t a test, there’s no code and if there’s code there’s gotta be a test! And if one test passes and you want to Change the code to behave different with other input; You need to prove it with a test!

So we can test if

1
Sum("1")

will return 1, which we from looking at the code will see that it wont!

1
2
3
4
5
6
7
8
public void Sum_ValueContainsADigit_ReturnTheDigitThatIsPassed()
{
    var calculator = Calculator.GetInstance();
    var actual = calculator.Sum("1");
    var expected = "1";

    Assert.AreEqaul(expected, actual);
}

This test will most defently fail because of our implementation! So we need to go back to Sum and change this method.

Once all tests passes and the test case is approved, we head on to the next step, which is make it better! In other wors we need to refactor some code! Try to follow these steps to refactor ( i use ReSharper, which is a Great tool! ).

  • Move the Library to an appropriet Class Library / Project
  • Optimize the code
  • Refactor your test to look better
  • Comment the code

So you got a little peek at what TDD is and how it can be used, if everyone would use TDD, it would be so much easier to take on new projects that have already been started. You never know what your changes will impact on.

March 25, 2010

Using Parallel Extensions in LINQ

Filed under: .NET, C#, Programming — Tags: , , , , — Filip Ekberg @ 4:16 pm

Once again, there was a little mistake in the last post I posted here which clearly didn’t effect the result that much. But it is still worth mentioning again. The ^ was not meant to be XOR, I was clearly thinking of Math.Pow.

In the last post I didn’t spend to much time talking about the Parallel Extensions for LINQ which are Really great and helpful; If you just love to replace traditional loops with LINQ-expressions you will probably find this post somewhat amusing.

So let’s dig down to the coding shall we!

First of all I have set up a smaller list with numbers, in this scenario we will just assume that we have a list of something and depending on the contents of that list, the time it takes to perform an action on that result, will differ. So here’s my list

1
var latency = new[] {1, 2, 4, 8};

Side note: new[]{} is really helpful, especially when you are creating examples like this!

And then I have a method that I want to run for each element in my list, which I will call PerformLogic

1
2
3
4
5
6
7
8
static int PerformLogic(int latency)
{
    var ms = 500 * latency;

    Thread.Sleep(ms);

    return ms;
}

In “traditional” programming, you would maybe do something like this:

1
2
3
4
for ( int i = 0; i < latency.Lenght; i++ )
{
    PerformAction(i);
}

But I don’t find that so amusing anymore, using LINQ is so much neater so instead of that for-loop we can actually do this:

1
(from i in latency select PerformAction(i)).ToList();

We don’t really have to write the expession like this though, since LINQ + .NET 4.0 is so smart, we can Refactor this to look somewhat like this:

1
(latency.Select(PerformLogic)).ToList();

The previous one is a bit more elaborate but this is fine aswell.

Making it parallel

We’ve reached the place where we no longer can refactor our code to make it faster, we can’t replace anything in the logic to make everything faster; We need to parallelize it!

Let’s have a look at what LINQ provides us with, oh, there’s an method called

1
.AsParallel

.

All I did now was changing the above code to this:

1
var result = (latency.Select(PerformLogic)).AsParallel().ToList();

And we have a parallelized query. For those with a fast mind can see that it will take about 7,5 seconds to run this since each of the “latency”-points will take itself times ½ second.

My final test-code looks like this

1
2
3
4
5
6
7
8
9
10
11
var latency = new[] {1, 2, 4, 8};

var start = DateTime.Now;

var result = (latency.Select(PerformLogic)).AsParallel().ToList();

var end = DateTime.Now;

Parallel.ForEach(result, Console.WriteLine);

Console.WriteLine("Execution time: {0}", (end - start));

And this is the output
LINQ Parallelism

March 24, 2010

Using the Parallel Extensions in .NET 4.0 with C#

Filed under: .NET, C#, Programming — Tags: , , , , — Filip Ekberg @ 10:59 am

As .NET 4.0 will be released in a couple of weeks and the RC has been out for a while. It’s about time that I write something about the new helpful features of .NET 4.0. One of these helpful things are the Parallel Extensions and Parallel helpers that allowes you to do parallel programming.

Parallel computing is a form of computation in which many calculations are carried out simultaneously

In this example I will be using a WebRequestPool which just helps me out a bit to carry on this example. You might think if it like this: You have different request types which takes different long to execute you might be doing some WebDAV uploading, Image Fetching and other Over-The-Web-Access which takes time. Instead of waiting for each request to stop, you might as well run them simultaneously.

1
2
3
4
5
6
internal delegate void WebRequest(int ms);

internal class WebRequestPool
{
    public List Requests { get; set; }
}

So to make it easy I just have a simple Delegate which will allow us to Run/Invoke our WebMethods which all takes some input parameter that will, in some way, make the requests take longer / shorter.

Inside of the WebRequest class all we have is a Requests Pool, a simple list of delegates.

To make the whole a little bit interesting we have three different types of Requests: Standard Request, Long Request and ExtremeRequest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void StandardRequest(int ms)
{
    Thread.Sleep(ms);
}

static void LongRequest(int ms)
{
    Thread.Sleep(ms^2);
}

static void ExtremeRequest(int ms)
{
    Thread.Sleep(ms^10);
}

So now we have three different types of methods that all validate with our delegate! Let’s head on and fire up this pool

1
2
3
4
5
6
7
8
9
10
11
12
13
var pool = new WebRequestPool
{
    Requests =
        new List
        {
            StandardRequest,
            LongRequest,
            ExtremeRequest,
            StandardRequest,
            LongRequest,
            ExtremeRequest
        }
};

This actually demonstrates something new too, the object initializers. So the list now contains six requests, All we want to do now is Processes these.

First of all we want to do it like we did in the old days, so I’ve created a method called ProcessPool which looks like this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void ProcessPool(WebRequestPool pool)
{
    var start = DateTime.Now;

    foreach (var item in pool.Requests)
        item.Invoke(2000);

    var end = DateTime.Now;

    var span = end - start;

    Console.WriteLine(
    string.Format("Execution time: {0}", span));
}

Of we run this the output is
Execution time

Now, that’s a bit too slow for me, so Let’s Parallelize that! All i’ve done now is to creat a new method called ProcessPoolAsParallel which takes the same input and expects to give the same result. There’s a little bit difference though, the foreach is now replaced with the

1
Parallel.ForEach

method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void ProcessPoolAsParallel(WebRequestPool pool)
{

    var start = DateTime.Now;

    Parallel.ForEach(pool.Requests,
        item => item.Invoke(2000));

    var end = DateTime.Now;

    var span = end - start;

    Console.WriteLine(
        string.Format("Execution time: {0}", span));
}

So if we run this now the result is:
Parallel run 2

So this increased significally!

This is just a small example of the power in using Parallel programming patterns. Look into the Task class to head on!

Edit

There’s a slightly miss-used method in the code above, the ^ in C# is XOR and I was thinking of the Math.Pow, however, this doesn’t really matter in this case since the result is still Parallel = Faster.

November 30, 2009

Function pointers in C and Python and their possible usage

Filed under: Architecture, Programming, Python, c-programming — Tags: , — Filip Ekberg @ 4:07 pm

Function pointers? you might ask yourself, well this little trick gets handy sometimes, I will provide an example of a practical use in a later post on the next euler solution. Might actually do it in C too just to prove that C is still neat.

So to kick this off, what are function pointers? Well for those deep down the rabbit hole ( .NET guys that is ), might not really have a clue on the matter, and others might dissaggree and now exactly what it is. So just to keep the air clear here, function pointers are “pointers” that direct you to a function, easy huh?

Well, you probably got as much from just reading the phrase but, it’s not really rocket science. If you are familiar with references or reference types, such as Strings and Objects, you know that there are different types of memory in which your program operates. When you create an Object you store your data on a shared memory place. There are shared memory and program reserved memory ( the stack! ). So you might want to look at this as a “reference” to a function.

So when would this be nessecary? Imagine the scenario where you might want to performe some calculation but you don’t know what type of API the end user which will end up using your API have. Let’s say that the method “square” ( x^x ) would not be defined. So you might end up having to use function pointers, where you ask the user to suppy the function for calculating square of x.

In Python the Square function for x^x will look like this

1
2
3
4
5
6
def square(i):
        result = i;
        for x in range(i-1):
                result *= i

        return result

In C it will look like this

1
2
3
4
5
6
7
8
9
10
11
12
int square(int i)
{
        int result = i;
        int x = 1;

        for ( x = 1; x < i; x++ )
        {
                result *= i;
        }

        return result;
}

Now these two look fairly similar don’t they? Well sure, the only real difference is the dialekt right? It’s just programming. So let’s get to the cool parts. In python, we would solve this problem easy, since it’s not a strongly typed language everything could be a function, right. So let’s check the decleration for calculate.

But before we check that out, let’s just make it clear that our Usage will be somewhat like, give me a function that calculates square of a+b, this means, the result should be (a+b)^(a+b).

So this is the function decleration in Python

1
def calculate(func, a, b)

Not that hard, right? Well, keep in mind that Python is a “modern” language, it’s more of a scripting language.

Check this out and notice the fairly big difference

1
int calculate(int (*func)(int c), int a, int b)

If you are not familiar with pointers I would suggest you dig down the archive on my blog and check out the chapters about that. So what this really does in C is that you tell the compiler that, okay this function takes a pointer to something that will look like this, and you write the declaration of the function again. So, in this case you really need to know what it looks like. With standard parameter values in Python you could acheive some really cool things without knowing the decleration of the function.

Now we’ve seen how to Create the methods, taking arguments that are functions, how about using them inside your code?

Check this C example of the whole Calculate function

1
2
3
4
int calculate(int (*func)(int c), int a, int b)
{
        return (*func)(a+b);
}

And in Python the following will look like this

1
2
def calculate(func, a, b):
        return func(a+b);

There is a notable difference here, but I can honestly say that I like the C-style.

Try out the python version!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/python

def square(i):
        result = i;
        for x in range(i-1):
                result *= i

        return result

def calculate(func, a, b):
        return func(a+b);

def main():
        print calculate(square, 1, 1)

if __name__ == "__main__":
    main()

Happy Coding!

Solving the first problem

Filed under: Python — Tags: , — Filip Ekberg @ 11:06 am

So I’ve decided to start a new project, to solve as many euler problems as possible from http://projecteuler.net/, in Python! The task in hand is not only to solve them but to think outside the box and add new features to the code which might become suitable in the future, who knows.

Let’s start off by solving the first problem!

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000

Now you might think it’s useless if you Only can solve this for 3 and 5, so why don’t we just make a tuple with the appropriet set of numbers?

My function declaration ended up looking like this

1
def sum_naturals(max, dividers=[3,5])

Where the variable max is, in this case, 1000. to test it out, I want the following to be true

1
2
# Prints 23
print sum_naturals(10)

This problem is not really rocket science so I’ll just let you guys look at the code and try to figure out what I was thinking, and please leave comments if you like or disslike it.

1
2
3
4
5
6
7
8
9
10
11
12
def sum_naturals(max, dividers=[3,5]):
result = 0

# Iterate through the numbers from 0 to max
for i in range(max):
# Iterate the dividers and divide i with each Divider
possibleDivision = 0
for divizor in dividers:
if (i % divizor) == 0 and possibleDivision == 0:
possibleDivision = 1
result += i
return result

This is actually a perfectly good example on “How to start python programming”. If requested or if i just feel like it, I might create a serie where I break these or similar problems into smaller pieces and explain them. Maybe I’ll throw in a couple of C#, C and PHP examples aswell. You decide.

Happy coding!

Testing the new Code-tag

Filed under: Programming — Tags: — Filip Ekberg @ 10:47 am

Testing testing…

1
2
3
4
    <?php
        // some code
        $i = 1;
    ?>

Seems like it works?

November 13, 2008

Polymorphism – A Practical Example

Filed under: C/C++, Programming — Tags: , — Filip Ekberg @ 7:01 pm

Classes, inheritance and polymorphism can sometimes be somewhat hard to understand. So a practial example suits many well. Therefore this will be a tutorial where i will touch the areas of classes, pointers, inheritance and polymorphism.

So to just clearify some expressions i will add a little dictionary at the top:

Class
A class can somewhat be seen as a blueprint of your object. I.e. having a blueprint for a building, then this would be the class. Then a Constructor would build this to become an actuall touchable object.

Inheritance
When you inherit something you can think of it more like you extend this thing. I.e. having a Car and then having a Sports Car where there are some new variables to it. The Sports Car is actually a Car but it’s also extended with new properties.

Polymorphism
This is taken from Wikipedia: “In simple terms, polymorphism is the ability of one type, A, to appear as and be used like another type, B. In strongly typed languages, this usually means that type A somehow derives from type B, or type A implements an interface that represents type B”. Read more here

Pointer
For a pointer explenation look here

I will be using Visual Studio 2008 with the built in C++ compiler for the following examples.

A good practice will be to create a Bank, when you get a new assignment or just want to create something new, start by thinking about the structure, what actuall needs does this have? Well when creating a Bank i think to myself that i’d like to be able to create Bank Accounts, attatch these to People and you can go on and on.

But, for the example i will only go as far as creating a Bank, a Bank Account ( Abstract ) and a Student Bank account which is the only Bank account you can actually get.

So creating a simple diagram over the project, i got something like this:diagram So now we have a Bank, Account and Student Account, what kind of variables do we need?

Bank
Bank Name
Accounts

Account
Balance
Interest
Max Loan
Account Holder

Student Account
Amount of Deposits
Last Deposite Month

So the big difference between Account and Student Account is that the Student Account have different rules than Account and therefore calculate a lot of things differently. We won’t go through all the logics. There will of course be a window for you to evolve this application as you feel nessesary.

Now when we have a defined structure we can start by creating a new Project and it’s files. My project will be called Bank and the following files will be placed in it:

  1. main.cpp
  2. Bank.h
  3. Bank.cpp
  4. BankAccount.h
  5. BankAccount.cpp
  6. StudentAccount.h
  7. StudentAccount.cpp

When all my files are created a start by definint my program entry point, this being my main. Notice that i will be posting code snippets as pictures, because you should Write this yourself and not copy my code!

1

We prepare for an input/output stream by including <iostream> and setting using namespace std;

Now the next part is to define the Bank.h We need an appropriet constructor, desctructor and some access methods, remember to never open up member variables publicly!

The #ifndef part is important for the compiler, we dont want to define our header file more than once, because that is not nessesary!

2

I assume all the parts are clear except the last one, read more about how that pointer type works in the previous post here on my wordpress.

The implementation itself will be up to you, i will only be showing the structure, header-files and some code from main and where polymorphism is concerned!

The next file to create would be the BankAccount, remember to add #include “BankAccount.h”  to Bank.h when it has been done. Otherwise the BankAccount *accounts array will fail because undefined symbol.

Back to the third file, the BankAccount.h this is how i would structure it:

3

The part to look deeply on here is the Deposite method, watch closely, it’s defined as followed: virtual void Deposite(double amount) = 0; So this method is expected to be overrided in a inherited class and it has the return type of void and an in parameter of the type double.

Now the next file to create is the StudentAccount.h where we will be deriving from BankAccount.

4

So the following class StudentAccount is extending a class called BankAccount. So this means that StudentAccount is a BankAccount with extended properties and/or overrided functions.

Now, look closely again, here we have the virtual void Deposite part again, but without the =0, so this means we will be creating a definition for this function.

Also the Amount of Deposits and Last Deposit Month is just there to simulate some properties that might be nessesary to do something on a student accont. In my case this is for the Deposite. A Student Can’t deposite money more than three times per month, this is because a student gets 2% interest everytime they deposite money.

This is my Constructor for StudentAccount

5

As you can see, we pass the Variables Owner and Deposite back to the constructor of the base type, being BankAccount.

Now this is how my Deposite Method is implemented:

6 

Now the last think i want you to look at, is my final Main:

7

dth="450" border="0" />

I want you to try and create all the nessesary functions in Bank.cpp, BankAccount.cpp and in StudentAccount.ccp to get the following output from this Main.cpp:

8 ‘

I would happily answer any questions about this project. A link to the complete source code is here

November 11, 2008

Pointers & Double Pointers

Filed under: C/C++ — Tags: , , , — Filip Ekberg @ 9:50 pm

Definitions
First off, we need to clearify what a some of the expressions i will use mean. These are the following expressions:

Stack
Assuming that you know about a computer having RAM ( Random Access Memory ) which allows you to store information and have this accessable faster than you would on a secondary memory like a harddrive and/or cd-rom.

When a program is executed there is a part in the memory reserved for this application to use, this “space” is called the Stack; The stack is always the same size and it’s not possible to change it’s size on any way.

Heap
The Heap is also a “space” on your memory, actually it’s all the memory not allocated as a stack. So when your stack is defined, everything else can be expressed as the Heap.

Pointers
What is a pointer really? A pointer is a globally used expression to reference that your somewhat “point” to something. See the following illustration

p1
On this image we have something that we point to, let’s call A our Object. So having A as the actualy object, play with the thought that B and C isnt there, and there are no pointers to it.

This would infact mean that we had A allocated on the Stack. When does this become a problem? So play with the thought you have a really big information base such as a User Layer where you store a lot of data on each user. Then havnig a big register on all the people attending a course would take up somewhat a bigger space than we have free.

When is is an issue, we can use a pointer, to reference to this object. You can of course point to an object that you have on the stack, but that’s not. afaik, what it’s initially intended for.

So we tell our program that we want to create a Pointer, this pointer will in fact be stored on the stack, but a pointer only takes up 4 bytes so this wont be a problem.

After creating the pointer, we create the object itself and have the pointer B point to this.

Pointer, Objects s & Arrays
Assuming you know about some object orientation and how an object is constructed i will not go in to this very deeply. I.e. we have a class called Person and we want to create somewhat a register over students attending a course, what we initially want to do is create an object array, where we can store all our persons, using c++, as i will do in the following examples you would write something like this:

1
Person *attendingStudents = new Person[size];

Where size is equal to the max amount of students.

Running this code, the constructor of Person will be runned as many times as the size of the array attendingStudents. How is this a problem? This becomes a problem when we dont want to run the default constructor and allocate the object size  as many times as the total array size, this has too much overhead.

First of all, how does this look in memory? 

p2

On adress 0 to adress 3 wnicn means 4 bytes; every memoy block is 4 bytes; the pointer attendingStudents is allocated and on that area a 4 byte long adress is stored which in our case is 84. The size of the given Person object is not given but just play with the thought that its 4 bytes and the size is 10 this would mean the total size of the Person array would be 10 * 4 = 40 Bytes going from the address 84 to 124.

However, let’s say that the Person object takes up 4 times as much so it takes up 16 bytes per Person object, this would result in 16 * 10 = 160 bytes, going from address 84 to 244. Now, there is a big overhead if we dont use all the persons and it would be stupid to call the constructors twice.

So, how about, we just point to something that we know is a pointer, and then let this poitner take care of the rest? But we just initialize the first step?

Double pointers
Thjis is were double pointers comes in handy, look at the following code:

1
Person **attedningStudents = new Person*[size]:

This code is not as straight forward to look at, as the pervious one, but it basically means, 

1
Person **attendingStudents

  = Create a reference, to a pointer, what is a pointer? A pointer is something that will in the end point to a data type, so what we do here is saying that Point to a Pointer, this pointer will eventually have the data type Person.

Just to clearify, a pointer to an array, initially points to the first index in that array. So after creating the Pointer to a Pointer we tell it to point to a new list of Pointers, the amount of pointers to create is the same as the digit in size.

This might not make any sense, but take a look at the following

p3

Initally these pointers don’t point to anything at all so what we can do is: attendingStudents[i] which will take us to the adress 84 and then create an object on this index by doing this:

1
attendingStudents[i] = new Person();

Why is this method better than the one before? Well this assures that we Only have the 11 pointers which takes 4 bytes per pointer. 1 pointer on the stack, referencing 10 pointers on the stack. When does this give us overhead? This gives us a 4 byte overhead when we start creating our Persons. But the execution time saved and just given 4 bytes ovearhead per pointer, this is a preffered method by me.

August 22, 2008

Importance of good Architecture, Structure and Patterns

Filed under: Architecture — Tags: — Filip Ekberg @ 9:54 pm

Often when developing software such as websites, windows ( or any other operative system for that matter ) programs, the begining of the progress is quite simple; you have your ideas and may have some thoughts about how to implement everything. But what often is forgot when developing software is the importance of thinking ahead, thus, planning for a larger software that you have in mind.

For an example, when i started developing SmartIT Invoice i thought of it as a software that would generally help me organize my small amount of invoices. But as the years pass my company grows bigger and bigger and once im up to n-numbers of invoices, a simple List View won’t be sufficient. Therefore after implementing my Invoice software, i started thinking about how i could change everything and structure the code for helping me in the future. I had in mind that i might not always want to use the Windows Graphical Interface for input and output so as i always do, i seperate the Design code from the Logical Code. This meaning that my application has three layers. Them being:

  • Application Layer, code for display, handling window events
  • Logic data layer, database connections, objects
  • Data layer, this being the database with functions, views and procedures

By having these three layers i can easily change one of the layers without changing the next. Of course this is not entierly true, i would have to change some parts in the Logic Data Layer if i changed the DBMS.  I would however not have to change that much if i just changed the behaviour of a Stored procedure.

Again takng my Invoice softwre as an example, i recently released a software called Webexpress.nu which allows customers to create their own website and for this i need somewhat of a payment system. Of course using Credit card payments is nice and easy but not entierly nessesary. So by just adapting my Webste to the current Logic Data Layer of my SmartIT Invoice software, i could easily get an intergration that allowed me to create customer invoices that pops up on the user account, when they are online on the page of course and even directly to my software, withouth any adjustments in the Data Layer or in my Windows Software.

This proves the point that well structured code and seperate layers will help you along the way of program development.

As a side note the Data Layer in this case is a Windows DLL with .NET 3.5 code which makes it even easier to implement when the website itself is asp.net with .net 3.5.

There are a lot of good design guidelines out there which will help you structure your software better and help you understand how to always follow a pattern. A pattern doesn’t, in my point of view, have to be a pattern like Singelton etc, it can by any means be a way for yourself to regocnize your own code, thus following a pattern. Example, i often tend to use m_ before member variables and write all functions and access methods with a capital letter.

Have fun programming!

August 18, 2008

Big O-notation

Filed under: Algorithms & Data structures — Tags: , — Filip Ekberg @ 9:55 pm

So starting school in a couple of weeks and being told that you wont get any “allowance” from the state makes you think twice about your current situtation. Not that this has anything ( directly  ) to do with o-notation. However this is how i forced myself into learning it. I have to re-take an exam in Algorithms and Datastructures this upcoming week and i want to share my experience in big o-notation.

So basicly we have an array, a list of some sort and somehow we need to go through each element in this list. Having ‘n’ elements we need to create some kind of look like this:

1
2
3
4
5
6
7
void walkList(int[] numbers)
{
for ( int i = 0 ; i &lt; numbers.lenght(); i ++ )
{
print numbers[i];
}
}

Now this will print all the elements contained in the list of numbers. Lets look at this from a time complexity way, 4 constant operations these being:

  • function input
  • int i assignment
  • i < numbers check
  • increment

And the loop will run ‘n’ times meaning we have n + 4 this will give us O(n + 4), but constant access times are irrelevant talking about runtime so all we do is write O(n). O, ordor as it is pronounced, is a way of stating the time complexity.

Now lets say we need to process ths array in another way, play with the thought that we have this list of numbers and for each number we want to go through the list again. This would give us a nested loop and give the time complexity O(n^2). This meaning that we need to process the list twice for each item, hence n ^ 2.

Looking at a sorting algorithm like Merge Sort that first divides the list into 2 peices untill its at the last item, then merges them. We see the typical behavior of a log() with the base 2. So, the split / sort part is basicly log(n) while the merging part is n and log (n) * n = nlog(n) which is slower than log(n). There are however no “standard” sort algorithms that can do better than nlog(n), in a random case that is. Best case for i.e. bubblesort is log(n)  and worst case for bubblesort is log(n^2) which is slower than mergesort.

Mergesort

When is time complexity nessesary? I would say that during all my years of programming, learning speed, size and other performance parts the hard way, i would say that this is a very good complement to fast calculate time complexity of your algorithm. You can be a very good programmer without knowing a lot about this. A lot of this is just something that a programmer knows how to handle without knowing O-notation. But as said, a good complement.

Older Posts »

Powered by WordPress