Algorithm Speed (Part 2)

The Big O Notation

The O() notation is a mathematical way of dealing with approximations. We say that the worst case time complexity of an algorithm is O(n2). It means, for n records, the time taken for the algorithm to run is in the order of square of n. We consider only higher orders while estimating time complexity. For example:

O(n2 + 2n) = O(n2)

The higher order dominates other values while n varies. Since we are eliminating lower order terms, one O(n2) algorithm can be much faster than another O(n2) algorithm.

- summary of Algorithm Speed, from The Pragmatic Programmer: from Journeyman to Master

Algorithm Speed (Part 1)

We estimate the time taken to complete the project, or the time taken to complete a particular task. There is another kind of estimation: estimating the resources used by an algorithm. This includes time taken to complete the algorithm, processor and memory consumption etc.

This kind of estimation is always important. Resource estimation is used to know how long the program takes to run with a particular set inputs. This also helps us to understand how the program scales for large number of records, thereby letting us know which all parts of the code need optimization.

How do we estimate algorithms? 

That is where we get the help of big O notations.

Estimating Algorithms… What does that mean?

Algorithms work with variable inputs: sorting takes an n element array, matrix operations require an n×m matrix etc. The size of the input affects the running time and amount of memory it takes.

But why do we need to estimate algorithm speed? Because the rate at which the execution speed increases is not always linear. An algorithm which takes one minute to process 10 records may take a lifetime to process 1000!

Big O notations allow us to perform a more detailed analysis.

- summary of Algorithm Speed, from The Pragmatic Programmer: from Journeyman to Master

Programming by Coincidence (Part 2)

There is only one way to avoid all these accidents: Always program deliberately.

How to Program Deliberately

• Always be aware of what you are doing. Never let things go out of your hand.
• Don’t code blindfolded. Chances of coincidence are high when we try to build an application without fully understanding it.
• Always proceed from a plan. It doesn’t matter whether the plan is in paper or in your mind.
• Rely only on reliable things. Do not depend on accidents or assumptions.
• Document your assumptions. This helps to recollect and validate the assumptions at a later point of time.
• Don't just test your code, but test your assumptions as well. Write assertions to test your assumptions. Never guess anything; actually try it.
• Prioritize your effort. Spend time on important aspects.
• Don’t be a slave to history. Always be ready to refactor. Never let what you have already done constrain what you do next.

- summary of Programming by Coincidence, from The Pragmatic Programmer: from Journeyman to Master

Programming by Coincidence (Part 1)

Programming is like working in a minefield! An explosion can happen at any moment. Never take chances. Always be careful.

Programming by coincidence is relying on luck and accidental successes.

But, how do we program by coincidence?

Image that we are working on a programming project. We add some code, run it. It seems to be working. Then we add more code. Still it’s working. Suddenly, after several days/weeks, the program stops working. We spend hours to see what went wrong. But we couldn’t figure anything.

Why?  Because, we didn't know why it worked in the first place!

Sometimes, we rely on coincidences. Here are some examples:

Accidents of Implementation

This happens because of the way the code is currently being written. Suppose we call a routing with some data. The routine responds in a particular way. But the author didn’t indent for the routine to work that way. It can happen either due to code, or due to the routine itself. When the routine is fixed, our code might break.

Accidents of Context

We sometimes rely on the context in which we are currently working. We tend to think in such a way that this is for that particular context only. Accidents of context happens while relying on a thing that isn't guaranteed

Implicit Assumptions

We assume things. Assumptions are always poorly documented. It may vary from developer to developer.

How can we avoid these problems?

Simple...

Don’t program by coincidence


- summary of Programming by Coincidence, from The Pragmatic Programmer: from Journeyman to Master

It’s Just A View (Part 2)

Pushing all the events through a single routine is a violation of object encapsulation. It also increases coupling. That one routine has now knowledge about the interactions among many other objects. Because of the same, we are also violating DRY principle, as well as orthogonality.

Objects should be able to register to receive only the events they need, and should never be sent events they don't need.

Model View Controller

Suppose we have a spreadsheet application with some data. In addition to the sheet, we need to show the data as a graph/pie chart, and also a table with total data. But here we don’t want separate copies of data for each representation.

How do we tackle this problem?

We can create a model with the available data and common operations to manipulate it. Then we can create separate views, which use this model to display the data in various formats such as sheets, pie/bar charts  or tables. Each view also has a controller which takes care of manipulating the model data into the particular format.

Our basic objective is this:

Separate Views from Models

As the coupling between model and view reduces, the flexibility and reversibility of the code increases to a very large extend.


- summary of It’s Just A View, from The Pragmatic Programmer: from Journeyman to Master

It’s Just A View (Part 1)

We always use the ‘divide and conquer’ approach to separate big chunks of program into different modules. A module is supposed to have one, and only one, well-defined responsibility.

But here arises a new problem: At runtime, how will these modules communicate with each other? How do we manage the logical dependencies between them? How do we synchronize changes in states or data values between these modules? These things has to be done in a clean and flexible manner. We need make these happen, but we don’t want modules know too much about each other.

Here we introduce the concept of events. An event is a message which says, “something just happened”. We can use events to signal changes in one module that some other module may be interested in. Events helps to minimize the coupling between modules. The sender doesn’t need to know anything about the receiver. There can be multiple receivers also.

It’s a bad idea to have one routine which receives all the events destined for a particular application.


- summary of It's Just a View, from The Pragmatic Programmer: from Journeyman to Master