Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

But I imagine there are still areas where such considerations do remain of paramount importance. Two that come to mind are in algorithmic trading, where thousands of transactions must be conducted in fractions of a second, and embedded systems programming, where memory and power are often scarce. Am I right about these examples ? and what other areas would also be examples?

share|improve this question
1  
The LMAX disruptor might interest you: infoq.com/presentations/LMAX –  user1249 Feb 11 '12 at 11:25
    
"algorithmic trading" is a bad example. The algorithms are often trivial; overall low-latency performance is more a matter of dedicated resources, than clever algorithm design. –  S.Lott Feb 11 '12 at 13:30
4  
Complexity is always more important than hardware resources as the size of the data increases. An O(n*log(n)) algorithm will finish faster on an 30 years old computer than an O(n!) or O(n*n) on today's most expensive hardware if n is big enough. –  vsz Feb 11 '12 at 18:19
1  
You can think of it like O(c * f(n)) Where the constant c is based on the inefficiency of the hardware. You can have a 1000 times faster system, as n goes to infinity, it will matter less and less. I would choose an O(10000 * log(n)) instead of an O(n) any day if I suspect that n can be large. –  vsz Feb 11 '12 at 18:23
add comment

10 Answers

Speed is always in demand. I guess you are correct. Here are some examples were neat algorithms are in demand:

  1. Cryptography

  2. Searching large databases

  3. Sorting and merging

  4. Text searching (non-indexed), including wildcards

  5. Math problems with intensive calculations

  6. Simulation

  7. Data Mining Applications

  8. Animation

  9. AI

  10. Computer vision

share|improve this answer
2  
I would like to add to this "life-critical" application such as medical equipment. –  stuartmclark Feb 11 '12 at 8:32
    
@stuartmclark, you are quite correct. I also forgot to mention Automatic Control Systems and Navigation Systems! –  Emmad Kareem Feb 11 '12 at 11:13
2  
Speed is not terribly relevant in crypto unless you're trying to crack passwords. I would put "large databases" first. The volume of information available on the internet is staggering. A dumb large-data algorithm can kill a good idea by making it seem infeasible. –  S.Lott Feb 11 '12 at 13:29
2  
@S.Lott, speed is extremely relevant. A web site serving thousands of SSL requests per second would choke if crypto algorithms are not optimised well enough. Some are even using hardware acceleration. –  SK-logic Feb 11 '12 at 16:53
    
@SK-logic: While true, it's not the same kind of algorithmic consideration that the others have. Most crypto processing has a relatively simple algorithm with lots of super-clever optimizations to reduce the "computation" to table lookups and bit-fiddling. I suppose this is "algorithmic", but crypto always seems like lots of super-clever optimizations more than algorithm design. That's why I suggest that it's not first. –  S.Lott Feb 12 '12 at 17:18
show 3 more comments

There are some cases where algorithm run-time might not be a big deal, because we've gotten to the point that you can simply punch through a longer-running algorithm with more powerful hardware. But there are definitely some places where speed-ups are essential.

Generally speaking, anything using huge datasets will be a problem. When you have something that scales poorly with n, and then you make n a really huge number, you have a problem. I suspect if you went over to the Computational Science beta site and poked around a bit, you could find plenty of problems in need of better, faster algorithms. Some areas that I've run into:

  • Particularly complex statistical analysis. A combination of inefficient algorithms and large data sets can mean massive slowdowns. For some studies, this might not matter, but what if you're trying to do something with fast turn around? "It will come off the server in a month" is probably a bad thing when you're running a chemical/nuclear/biological threat surveillance system.
  • Data mining on large data sets.
  • Simulations involving many variables.

Generally speaking, scientific computing generally seems to be an area where the complexity of what's being programmed generates opportunities for serious slowdowns if your algorithm is sluggish (many of them suffering from very large n's). And, as you mentioned, there's financial applications. When milliseconds can determine whether you make or lose money on a trade, "good enough" algorithms aren't going to cut it if there's something better that can be done.

share|improve this answer
add comment

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

Take it with a grain of salt. More computing power basically just means that your n can become much larger before it significantly slows down. For most everyday problems, this n is now large enough that you don't need to care. However, you should still know the complexities of your algorithms.

With more available resources, it may need to crunch more data later. Today you need to analyze a 10MB log file with 100,000 lines. In a year you may have a 100GB log file with 1,000,000,000 lines. If the amount of data grows faster than the resource powers, you run into problems later.

With more available resources, more layers are stacked upon each other. OS, OS framework, 3rd party framework, language interpreter, and finally on top your own tool. All unnecessary inefficiencies in all the different layers multiply up. Tomorrow your tool may run on a new OS with more bells and whistles, that itself eats more cycles and more memory, leaving less for you.

So to answer your question, you still need to care where more and more data needs to be crunched (enough examples given in the other answers), and where you do not provide the final tool, but another abstraction layer for other tools.

share|improve this answer
add comment

A few years ago I had to write an algorithm that sorted test tubes arranged on n racks into two distinct partitions: i.e. one subset of the tubes were 'chosen' and the rest were 'not-chosen' and the end result would be that no rack would have both a 'chosen' and 'not-chosen' tube on it (there were some extra requirements such as compression). Each rack contained a maximum of 100 tubes.

The algorithm was to be used to drive a tube sorting robot in a pharmaceutical laboratory.

When the original specification was given to me I was allocated in the region of 1 minute of calculation time to sort around 2000 tubes as we thought that usability wise that was not too painful. There was a requirement that number of moves was to be minimal over all possible combinations as the robot itself was slow.

The implicit assumption was that the complexity would be exponential with the number of tubes. However, whilst working on the algorithm design I discovered that there is a fast O(n) algorithm where n is the number of racks that performed an optimal partitioning of the tubes. The result of that was that the algorithm sort time was instant so the sorting display would be updated in real time as the user configured their sort operation.

For me the difference between the user sitting for a minute after every change and having an instantly responsive GUI was the difference between a piece of software that was functionally sufficient and a piece of software that was a pleasure to use.

share|improve this answer
    
Nice example! Sounds like you did something akin to a radix sort? –  Barry Brown Feb 12 '12 at 1:58
    
@BarryBrown - not sure what the name of the algorithm I used was as I made it up myself. Essentially it was simultaneous sort of two lists with competition. So each rack could appear in either the "chosen" or the "not-chosen" list and the cost of it being in that list was the cost of removing all tubes that were illegal. –  user23157 Feb 13 '12 at 10:04
add comment

Other areas include many kinds of real-time signal processing, feedback control systems, oil exploration deconvolution, video compression, ray tracing and movie frame rendering, virtual reality systems, games where high frame rate might be a significant competitive advantage, and smartphones and other mobile device apps, where large numbers of CPU cycles will consume the users battery life faster.

I'm quite surprised this question would even be asked, since for any Top-500 supercomputer ever built, there is likely a waiting list of researchers who can max it out and wish for magnitudes more compute power or magnitudes better algorithms to solve some problem (fold some protein to decipher cancer, etc.) before they retire.

share|improve this answer
add comment

Algorithm efficiency isn't a major concern nowadays because we're using efficient algorithms. If you used an O(n!) algorithm, it would be slow on any kind of hardware.

share|improve this answer
    
That's an interesting point of view. "It's not an issue, because it should go without saying" rather than "it is an issue, but not an important one". –  leftaroundabout Feb 11 '12 at 13:31
add comment

Algorithm complexity is becoming more and more important as the sheer amount of data increases. Fortunately, efficient generic solutions for common programming problems (searching and sorting, mainly) are included in pretty much every modern programming language's standard library, so normally, a programmer doesn't have to worry about these things much. The downside is that many programmers do not know at all what is going on under the hood and what the characteristics are of the algorithms they use.

This becomes especially problematic as many applications aren't properly stress-tested: People write code that works well for small test data sets, but when confronted with a few thousand times more data, the code grinds to a halt. Something that works well for ten records quickly explodes when the data set grows. Real-world example: a piece of code that was supposed to clean out items that weren't linked to any category anymore used a three-level nested loop, which is O(n^3). With just 10 records in the test database, this meant 1000 checks - perfectly doable, and doesn't introduce a noticable delay. However, the production database quickly filled with around 1000 rows, and suddenly the code does a billion checks each time.

So: No, you don't need to know the ins and outs of implementing all sorts of neat algorithms, and you don't need to be able to invent your own, but you do need some basic knowledge of common algorithms, what their strong and weak points are, when and when not to use them, and you need to be aware of the possible impact of algorithmic complexity, so that you can decide which level of complexity is acceptable.

share|improve this answer
add comment

I think search engines like Google and Bing are one of the biggest areas where complex algorithms are used and they play a key role in speeding up results with relevance ( page ranking ) bringing more utility to the users.

share|improve this answer
add comment

It's not a question of what application domains are runtime-sensitive. Any program, anywhere, has a minimum performance below which it is effectively worthless. The point of algorithm complexity is how it varies with increasing input size. In other words, the areas where speed particularly matters are those where you expect to have to scale beyond not just your current problem size, but the order of magnitude of your current problem size. If you process the tax applications of the citizens of a département of France, the task may be large, but it's not likely that either the population size or the complexity of processing one record will ever increase ten or hundred-fold, so whatever works for you now, will probably keep working. But if you try to create something that will take off at internet volumes, algorithm complexity is key: anything that depends more than linearly or log-linearly on the input size will become much more expensive very fast, and eventually processor speed just can't keep up with the growth.

share|improve this answer
add comment

Three more that haven't been mentioned:

1) Many real time strategy games. Look at those which have units which can't share a position. Watch what happens to the pathfinding when a large group of units moves through restricted terrain. I have yet to encounter a game without some sort of substantial problem with this because there simply isn't enough CPU power available.

2) Many optimization problems.

3) Things which must operate on large amounts of data in realtime. Consider a DVD: You usually get 2 hours of video in 4.7gb. Consider a typical video file at the same resolution: Those 2 hours of video will generally come in under 1gb. The reason for this is when the DVD spec was laid down you couldn't make a reasonably-priced DVD player that could decode the more modern formats fast enough.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.