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.

I solve many problems, mostly from Top Coder. I will get answers for many, but most times I end up with an inefficient solution.

In real-world implementations - does it really matter that a solution to the problem is efficient? If so how I can improve it?

share|improve this question
4  
Are you asking from a contest standpoint or a real-world implementations standpoint? –  rjzii Feb 13 '12 at 2:27
    
@RobZ : In real-world implementations –  Ant's Feb 13 '12 at 10:00
1  
"real-world" covers a lot of ground. Embedded? Server applications? Mobile applications? Single-user personal computer software? Scientific simulations? The answers are not necessarily the same for them. –  David Thornley Feb 13 '12 at 17:15
add comment

6 Answers 6

up vote 34 down vote accepted

The best solution is the one that is (in order of increasing importance) efficient, maintainable and done.

^^^That is the only thing you really need to take from this answer.^^^

Efficiency is important. Maybe a little less so than it used to be due to our abundance of hardware, but Performance is a Feature. In a contest, efficiency is obviously important. You should know how to write efficient code. More importantly you should know the best practices that will yield efficient, good performing code without sacrificing on the timeliness or maintainability of an application. This is really where depth of experience with a platform and language returns many yields.

More important though(in 95% of cases), is having a finished, maintainable solution. Without a finished product, it doesn't matter how efficient or maintainable the solution. If it takes you an extraordinary amount of time to track and fix a bug or add a new feature, it doesn't matter how efficient the solution. But, efficiency and performance are undoubtedly important, no matter what anybody might say.

share|improve this answer
3  
Yup. And a terribly inefficient program that's both correct and done gives you something to test your improvements against. –  Mike Sherrill 'Cat Recall' Feb 13 '12 at 13:15
1  
The most important part of this is knowing the best practices for efficiency especially in database development where I personally would put efficiency above maintainability. Users care desperately about performance. I've often seen more efficient code being talked about as harder to maintain but only because of the failure of the developer to understand the more efficient code to begin with, once you get familiar with the techinques, you go to those techiniques as first choice and they become easier to maintian because you understand why they work. –  HLGEM Feb 13 '12 at 15:45
    
@HLGEM If there was any part of this answer that I would like to reinforce as a general principle (besides the first line), it is knowing the best practices for writing efficient code. And you're right on with the comment about efficient SQL being important. –  Mike Cellini Feb 13 '12 at 15:54
add comment

That depends on the structure of the contest, but generally, yes: performance is a consideration most of the time, according to their documentation. Sometimes, as in the later link, you have to hunt, but to quote:

Write clean, clear, efficient code. Even though there is no review line item specifically for this, reviewers are nevertheless likely to react better to code that is easy for them to read and understand. With efficient code you get a potential performance advantage in stress and benchmark testing, as well as likely kudos (and a few extra points) from the reviewers.

The best way to improve at this is to write code that is efficient, which you are already doing. Even if you complete the work, spend time on improving the efficiency of it - even after the competition - and that will pay off.

You probably also want to invest in theory, such as books on algorithms, that can give you two things: more efficient tools to solve a specific problem, and more efficient mechanisms for identifying what the problem you have to solve is.

Finally, computer science courses are increasingly available online, and will cover the background you need to improve.

share|improve this answer
    
There's a newer edition of the algorithm design manual out. (11 years between the two). Is there something wrong with the newer one? Particularly since it is cheaper than the old one. If so, perhaps that should be addressed in your answer. –  World Engineer Feb 13 '12 at 3:38
    
No, I just listed the first one that I found on Amazon, and didn't bother checking that it was the second edition. –  Daniel Pittman Feb 13 '12 at 17:58
add comment

How efficient a solution needs to be is dependent on a number of factors. The biggest thing is knowing what your user wants. Here's a few examples.

  1. If you are the only user of a block of code, and it works just fine for you, then you are probably alright.
  2. If your program is going to be sold, then you need to have a target platform in mind. Test it with this platform. If the program is exceptionally slow, then you need to work on making it more efficient. If it seems fine to you, hand it off to other users, and see if they agree.
  3. Perhaps the program has other considerations. If you are building, say, a server based program, then you might need to work very hard to make the program as efficient as possible. Or, if it runs on a microprocessor, make sure it works there as well.

How to make your code more efficient:

  1. The first step is to get an idea of what is taking the most time. The trick is to do something called profiling code. Look for what is taking the most time, and see if you can figure out a way to make it run quicker.
  2. Perhaps the key limiting factor is memory. If that is the case, look for what is taking up large chunks of memory, and see how you might reduce it.

There is a whole field to optimization, but the two tips above should at least get you started.

share|improve this answer
add comment

For a competition you need to understand who the judges are and what they are about - if they are looking for great coders and nothing more, then you will get kudos for more efficient code.

As a rule, in the real world, it does not matter. One of the key ideas of software development is "Don't optimize what you don't know needs optimizing", then "Optimize only when it has been proven that it is required"

Many practitioners will argue that this leads to bloated, inefficient code that cannot be easily fixed, and in some edge cases (which they will crow about as if that's what most coders do all day every day) they are correct. However not many software development projects has it's measured outcomes "Performance: Faster than needed, Cost: Who cares, Delivery time : Sometime this decade", In the real world, it's usually "I want it cheap, I want it yesterday, I want it to work".

share|improve this answer
add comment

I'd agree with Mike Cellini, the one thing I'd add is.

Is something "efficient enough"? For example from a user point of view, there is not much difference between a function that completes in 0.00001 seconds or one that completes in 0.1 seconds even though one is much more efficient than the other. A function that completes in 10 minutes is not that much different (for the user) to one that completes in 12 minutes. In both cases the user would get a cup of coffee or get on with another task.

I've come to see efficiency as "an efficient user" not an efficient algorithm.

share|improve this answer
    
The rule of thumb I have heard is a 20% improvement can be noticed by a user. Both of those seem to qualify, I think a user could actually feel a difference in responsiveness between .1 and .00001 seconds. –  Chris Pitman Feb 14 '12 at 1:27
    
Chris, you may be right that a user could notice the difference between the two systems side by side, but would one system make a user noticably more efficient at his job? My observation (I've been doing this for over 25 years) is that the two systems would enable the user to do the same amount of work in a given time. –  Jaydee Feb 14 '12 at 9:41
add comment

In general, the most important solution to a problem is going to be the one that actually exists and is valid for the cases as they exist for your problem. In other-words, avoid premature optimization until such time that you actually know you have inefficient code, or efficient code that needs to be faster.

Also, don't forget that the best solution for your application may not be the general case solution. Case and point, a couple years back a professor gave our class a problem in which we were to print the first 10 numbers of a given type (sorry, my memory fails me as to the type, but it was one of the more unusual number classes) and we were given a test to check to ensure that the number was the given type. This was the extent of problem we were given and we were told it was due the next day with the most efficient solution receiving full credit. The following lecture the professor summarized the results:

  • Some students used a simple loop and the formula provided to check to ensure the numbers were correct and displayed them, slow but got the job done, O(n^3).
  • Other students did their research and found a formula that did a better job of checking to ensure that a given number was valid, these programs ran much faster, O(n^2).
  • One student used the slow formula to generate the values and then copied them into a constant array in their code and display the contents of that, O(n).

The final solution was judged the most efficient by the professor. Turns out that the problem was actually an exercise in fully understanding the problem and not just going out and finding the most efficient solution.

The point of the above is that when it comes to finding an efficient solution a problem it is generally better to spend the time to make sure you really understand what the problem is before going off and writing code, or attempting to optimize code. If you can store a set of reference values in a constant array then you are better off doing that from a performance standpoint than trying to write some fancy algorithm.

Likewise, don't forget that for most applications, the only people that tend to see inefficient code (when it is not needlessly inefficient!) are the developers themselves. If you write clean code that only does exactly what it needs to do then odds are that the majority of the time the users aren't going to notice performance issues when working with your program and when they do just optimize the parts that they mention to you.

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.