message by Carfield Yim

I think so. Not all algorithms are 'Algorithms'. Every time you write a loop, or code a recursive procedure, you're committing your code to run for a period of time, or use memory, dependent on some variable. How long will that time be? More importantly, how that time or memory requirement change as the variable changes?

Then, say that something you've written using nested loops is O(n^2), and you find it's running too slowly. Knowing something about estimating complexity, you look for a divide-and-conquer approach that will reduce the time to O(n log n). Without understanding the issues, you might be hacking around and hoping.

I find myself thinking about the complexity and runtime of code as I write it. It's never a formal analysis. It's just a quick check that what I'm doing makes sense.

Regards

Dave

-- Thomas Consulting.
Innovative and successful developments with Unix, Java, C, and C++.

Now in bookstores:

Carfield Yim wrote:

message by Carfield Yim

Even you don't do the complete analysis in practice, it is of help if you know about complexity analysis. There are patterns which always result in the same complexity behaviour. Knowing such patterns together with their complexity helps in reducing bottlenecks in programs. But first you have to know about the patterns. And as always: there is no better way of learning then doing by yourself.

Carfield Yim <c8133594@comp.polyu.edu.hk> wrote:

Yes, I applied them in work. I remember clearly when a piece of code was getting slower and slower as the data set size increased. We profiled it to see where the problem might be. The profile pointed us to a linked list routine. As we thought about it, we realized the implementation, which was quick and simple the first time, took O(n^2) time! A small addition to the data structure reduced it to O(n), which we confirmed with experiments.

I vaguely remember many other times when we designed various data structures or algorithms and informally reviewed their complexity to reduce the chance of performance problems.

-paul-

"Paul E. Black" wrote:

message by Paul E. Black

Hello Carfield, Paul, and everyone else,

O() expressions, like the many abstract formulas you will learn, do have meaning. They help gie you a framework upon which to think. If you know something about your problem domain, such as a very large 'n', you may consider that in your design of a solution. If the problem is speeding up a slow program, it may help you decide what parts of the application can be improved. This may be hardware, algorythm comlexity, or something else.

I'll relate last week's disaster for you. I've been working for a company that rushed to get one of its product out the door. This was done at least twice. Once for Unix and more recently a port to W98/NT. Most of the original developers have moved on. Since I now own the code I must deal with it. Here is an example of a somewhat typical workplace.

Monday morning I started my work for the day. Not long after that Customer Support called with a customer whose reports were taking too long. It seems that they had made several improvements to their hardware and software to keep up with the monitoring of a very large network of computers, which was also going. This customer is running a Quad 500Mhz Pentium XEON Server. Their 100+ reports for 50+ customers are taking a little longer. One group of reports were taking 1.5-2 hours each. So the Monday reports were probably going to finish on Thursday. That wasn't a good thing. I have a hot, but understanding and intelligent customer. We work through it and decide that the problem is with our software.

In the lab I recreate a similar experience on a much smaller scale. Even on a mostly idle machine the reports had slowed to almost an hour to complete. We start our reports with the base SQL statements and then let the customer decide add selection criteria through a program that schedules everything. This is also a mess in that MS SQL was the DB, the report generator was Crystal Reports, the custom code was modifying a 900 line(!!!) SQL query, and Crystal was calling some DLLs. It didn't take long to find that the data based on the DLLs was the trouble maker. The SQL query was approximately O(n^2) with n=12040 in the lab. Records were output at about 2 per second. All these pieces of the puzzle were fighting one another and had optimized solutions that together were clearly not optimal.

After deciphering the SQL, I found it to be close but wrong. It really needed an O(n^4) solution to be accurate. This actualy ran much better and the report ran in about 15 minutes. I already knew from experimentation that the report could be run in seconds if the problem fields were removed. The question was still how fast is reasonably possible?

I found that after examining the entire problem set, including the original specs, the problem data were partial tuples (rows) that were being combined with other records. It was sort of like finding the maximum value and placing it with another days data. I won't go into the meaning of the report. I saw that we weren't printing raw data, just summary info. The real mistake was that we asked SQL to do all the work and printed the info in the headers of each of the report groups.

The solution was simple. Reduce the SQL to about 30 lines of simple sselect and sort criteria. The program still adds whatever additional criteria it wants. The output was moved from the headers to the footers of the report generator. This now allowed me to place all my logic in the detail (processing of each row) section. Crystal Reports has a fairly rich formula library. I was able to keep track of the problem data and when the footers came around the data was ready to be displayed. The problem reduced itself to O(n). In the lab my time went from 72 minutes for a given report to 2 seconds.

The customer is happy; they already have the fix. Management is happy. What does everyone reading this think? My take is that poor design, poor implementation, a lack of quality standards or perhaps recognizing what is a realistic solution are the key problems here. How did the customer ever put up with this? How did Quality Assurance? Why did I get congratulated for good work and the ultimate culprits go unrecognized?

You will find O() concepts in everything if you recognize it. Whether it is a sort routine, a client-server connection, an SQL query, or whatever. Some tools provide performance analysis. This info combined with your knowledge of the problem domain can help you make decisions about possible alternatives. You may not scratch out a formula on paper or even discuss it will a fellow programmer. It will become as second nature as logic. It will be part of your though processes.

Everything is worth learning, whether or not we know the use we will put them to. I learned SQL from IBM 20+ years ago and just now have a job dealing with it. It hasn't changed that much. OO for C++ can be used in Java.

Enjoy everything, especially your chosen career,

David LaRue

In <385B4BA0.AE6D3362@comp.polyu.edu.hk>, Carfield Yim <c8133594@comp.polyu.edu.hk> writes:

message by Carfield Yim

message by Carfield Yim

Yes, though most of the time on an informal basis. I'm currently working on an information system that is pretty light on algorithms -- the problems are elsewhere, say requirements and UI. Thus I rarely have to think about the complexity of the stuff I write myself, but I have to think about the complexity of the stuff I use.

Here's a very small piece of the puzzle: We're working in Java and use the recently added Collection classes. For the various interfaces, such as List and Map, there are various implementations available and these implementations differ in their time and space complexity. To come to a reasonable decision which implementation to use you need to know something -- if only informal -- about complexity.

Recently I was using a Map and felt a little uneasy about the choice of implementation. I know the map will contain about 10 elements, i.e. hardly the size that warrants a HashMap; a linear search in an array may easily be more efficient. Now, this case isn't sensitive to performance, but if it was, I would write my own, linear-search SmallMap implementation of the Map interface to find out which one is better for the task.

Michael

message by Carfield Yim

I am also learning these tools. Are there any resources that have the complexity of common algorithms (such as euclid's algorithm) along with an explanation?

It would be useful to me to have an online resource that has such a list but if that is not available, does anyone know of any particularly good books on the subject?

Also (this may be in the FAQ) can anyone recommend any books on 'general programming' i.e. algorithms, good programming style etc. that are not language-specific?

Thanks