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.

Reference question: http://stackoverflow.com/questions/4303813/help-with-interview-question

The above question asked to solve a problem for an NxN matrix. While there was an easy solution, I gave a more general solution to solve the more general problem for an NxM matrix. A handful of people commented that this generalisation was bad because it made the solution more complex. One such comment is voted +8.

Putting aside the hard-to-explain voting effects on SO, there are two types of complexity to be considered here:

  1. Runtime complexity, i.e. how fast does the code run
  2. Code complexity, i.e. how difficult is the code to read and understand

The question of runtime complexity is something that requires a better understanding of the input data today and what it might look like in the future, taking the various growth factors into account where necessary.

The question of code complexity is the one I'm interested in here. By generalising the solution, we avoid having to rewrite it in the event that the constraints change. However, at the same time it can often result in complicating the code. In the reference question, the code for NxN is easy to understand for any competent programmer, but the NxM case (unless documented well) could easily confuse someone coming across the code for the first time.

So, my question is this: Where should you draw the line between generalising and keeping the code easy to understand?

share|improve this question
2  
possible repeat: programmers.stackexchange.com/questions/32964/… –  Pemdas Jan 7 '11 at 14:57
    
More complexity means more bugs. Keep it simple. –  mouviciel Jun 2 '12 at 7:44
add comment

14 Answers

up vote 10 down vote accepted
+50

Your question makes a dangerous assumption. It's assuming that generality is the opposite of simplicity.

Since this question, in part, deals with semantics, let's define the terms.

General - applicable to a variety of situations, robust, useful Simple - easy to understand, obvious, having few parts

These are actually two axes. The opposite of general is specific. The opposite of simple is complicated (not complex).

The best solutions in programming are both Simple & General.

Using a language well is the very art of making the general solution a simple one.

Since you're asking about something subjective, here's my view. Your solution to the problem is general, but it's not simple. Other solutions, like those requiring intuition about 0 or 1 being in the matrix are also not simple. In fact, any solution that is described in terms of the algorithm to find the solution is not simple.

This is a mistake many programmers (most?) make. They decompose the problem in their heads, but don't share that decomposition with the code. In this question, the first thing one should do to make it obvious to a new reader of the code is "What are we doing"? Are we turning rows in numbers? Are we navigating a grid of bits? Are we reasoning about matrix properties? Make it explicit. This prevents a new reader from having to reverse engineer the ideas every time he examines code.

Your solution is comparing rows.

You can add to the code the notion that you're comparing rows before you need to worry about whether this is NxN or NxM. Those details are handled in how you compare rows, but at that point the problem has changed from a matrix into two rows (a simpler problem). Then later, even comparing two rows simplifies to comparing two bits in those rows.

Fluent interfaces, declarative code, etc, all try to address these issues. Compilers are getting better and better at inlining efficiency (processors too). The days of needing to write a clever low-level loop algorithm for efficiency are going away.

Consider code like this:

Row smallest = matrix.FirstRow
for each Row r in matrix.rows
 if r < smallest
   smallest = r

Object orientation allows all sorts of state to be stored in a Row object. this allows for the tricks in your solution to be embedded in the Row object (including your 'which row am I on' trick; the < operator can be overloaded to do things like column 0 or 1 compares on that row). The efficiency can be made the same, while still making it simple (obvious) what's going on.

Even before we talk about implementing the 'search' for the best row, there's a bunch of information in the setup of the matrix itself (sorted rows, etc.) In fact, if this were C#, I'd simply write the search as matrix.Rows.Min() and create a representation of the Matrix and Rows that takes these assumptions into its definition. This makes those invariants setup by the question implicit in the code instead of just 'known' by the tricky assumptions the looping algorithm can make.

Once you do that, you'll see all sorts of neat things happen. The tricks people were saying about just looking for the 0000, or 0001 will be obvious because you'll be able to optimize the structure of the matrix itself (think array of NumberOf0's[RowNumber]). That last bit is 'getting complicated' but at least it's complexity in representing the input data and not yet searching for the solution.

Decomposition gives both generality and power, while keeping things simple.

Links:

http://en.wikipedia.org/wiki/Separation_of_concerns

http://en.wikipedia.org/wiki/Declarative_programming

share|improve this answer
add comment

Simple is king. Every bit of complexity that is added needs to justify its existance. How does it make the code better? Is that benefit worth the added complexity? We always approach adding more complexity as an evil act to the code. Only once you determine the code can't really live without it, is it appropriate to add it.

If you can't quantify and justify the complexity then leave it out.

share|improve this answer
2  
It can't be answered any better than this. –  kirk.burleson Jan 27 '11 at 12:01
add comment

The rule of thumb I follow is to generalize the code only after I have reused it a few times. This is usually greater than 3 times. The added complexity involved in generalizing to early is no worth it.

share|improve this answer
3  
Because without reusage experience you won't get it right the first time and will likely have to redo it later anyway. Here goes added effort. –  user8685 Jan 7 '11 at 15:01
2  
I don't think this really answers the question. The OP isn't asking about providing a general API. He's asking about choosing a more general algorithm over a more specialized one that can use the same API. –  Jason Baker Jan 7 '11 at 15:15
    
@Jason is correct. –  marcog Jan 7 '11 at 20:36
    
@Developer - I believe this is a very valid point. Without actual need for reuse you will probably not do the generalisation very well. –  bjarkef Jan 28 '11 at 8:42
add comment

First of all, I would question the assumption that there necessarily is a line between generalization and understandability. In this particular case, it sounds like you're discussing a well-known algorithm, so I don't really see anything wrong with generalizing.

As with most things in programming, there are tradeoffs to be considered. What's most important is that you're thinking of the big picture. It's very rare that you have a piece of code like this floating around in a vacuum. In this particular case, the complexity you're adding is very localized. That's still not ideal, but complexity is much easier to manage if you can close it off in its own little area. When complexity starts to affect other pieces of code, it has a tendency to multiply and get out of control very quickly.

So, since you are:

  • Implementing a well-known algorithm
  • Localizing the complexity

...I say go for it. If you can solve a potential problem ahead of time without too much extra effort and minimal complexity, there isn't any reason not to do it.

share|improve this answer
add comment

In this case your general solution is much simpler. It neither uses the uniqueness assumption nor the squareness assumption which means conceptually it is much easier to understand. The general solution simply depends on the structure of the bit vectors being of a certain form and anyone can verify that your code works by simply looking at 2 cases of 2xM matrices because the path traversal algorithm you describe only needs to look at the next row and then branch according to what it sees. Whereas the more specific solution for the NxN case requires a more global picture because uniqueness is a more global property and I don't see how understanding the solution to the simplest possible case generalizes to the NxN case. You probably would have gotten away with it if you didn't mention that your solution was more general. Some people instinctively reach for the nun's ruler when they see the words 'more general'.

share|improve this answer
2  
+1 for "Some people instinctively reach for the nun's ruler when they see the words 'more general'." –  Jason Baker Jan 7 '11 at 21:27
add comment

I would say that the line is drawn at the spot where there is a likely possibility that it will need to be generalized. Motivation comes into play here - are you generalizing because you want to see a slick, general, man-am-I-cool piece of code, or because you can actually see a good, real world use case for the generalized version?

I think a key phrase here is "unless documented well". A more generalized solution, if well commented, can still be maintainable and understandable. I do not believe in dumbing things down for incompetent programmers that may follow. If you comment the solution well, then most solid programmers should be able to follow behind you and figure out what you are doing.

At the same time, if a generalization does not make any sense, then you are using up resources for no reason. Generalizing by removing the NxN contraint may be a good idea, but generalizing for more dimensions (NxMxKx...) would probably not, because that is a much less likely workspace change. (I know that more dimensions does not make sense in the context of the original question asked, but I just wanted to provide some kind of out-there example).

Waiting to refactor, in my mind, is not a good solution either, if you are dealing with code where there is a decent chance you will need it. That just adds extra work in that you will need to write the whole thing twice, update documentation, push out new versions, etc.

In short, a little bit of foresight goes a long way.

share|improve this answer
add comment

While I agree with MattiasK's answer (+1 from me), I observed many times that coding while keeping the general case in mind helps write cleaner code, because the general case can require concepts to be more precisely defined, which helps writing more specific codes in a sound way.

share|improve this answer
1  
I agree, it can be a tricky judgement thing. You want to keep things as general and without dependencies as possible, without overly complicating things. It's probably one of these things where experience helps you find the sweet spot –  konrad Jan 7 '11 at 14:18
add comment

Sounds a bit like premature generalization, usually it's best to keep things simple if you're not fairly certain you'll need something

If its applicable and you're really worried about future extensions perhaps you can wrap it in a strategy pattern or something similar

Code should be made as simple as possible, but no simpler :)

I have an exception to the generalization rule and that's when something is very general (meaning it can potentially be used in several projects) and you have a bunch of related code, then I tend to build a utility library that I add to my "toolbox". If some project needs some addition that fits into one of those toolbox libs I can add them to the lib instead, tends to speed up development a lot after a couple of years :)

share|improve this answer
1  
+1 for premature generalization. –  back2dos Jan 8 '11 at 13:05
    
Is there medication that can treat premature generalization? +1 I'm using that line at work. Thanks! –  jmort253 Jan 25 '11 at 4:04
add comment

Ever heard of YAGNI?

You could just as well generalize the solution to work with matrices of floats. Or you could remove the constraint of uniqueness. What is the point? Unless there is actual reason to believe this requirement will come up anyway, it is just a waste of time.

When drawing the line between generalizing and keeping things simple, the right place is not compromising on keeping things simple.

Writing good code, i.e. maintainable, flexible, extensible and simple, is not achieved by generalizing individual components to suit a multitude of problems that they actually don't need to solve, but by properly structuring programs and ensuring very low coupling by a healthy use of abstraction and encapsulation.
To illustrate that: It doesn't really matter, whether your algorithm makes the assumption, that the matrix is NxN or not, because to be honest, it is not much code to rewrite. It is far more important, that the rest of your code doesn't break, because that assumption no longer holds and you need to rewrite that bit.

If I had to go to an armed melee fight, I'd rather have a club, than a swiss army knife.

share|improve this answer
3  
Fair enough. But I personally would rather have a club that can hit anyone than a club that can only hit people who are 6'2" and have blue eyes. –  Jason Baker Jan 7 '11 at 21:35
    
@Jason Baker: The specification here is armed melee fight. Full stop. The point is not to remove constraints or to add any, the latter of which you are doing, thus making no point at all. –  back2dos Jan 8 '11 at 13:05
2  
you're missing my point. My point is that you're comparing something that does one thing really well with something that tries to do everything when in reality you should be comparing something that does one thing really well under very limited circumstances with something that does one thing really well under any circumstance. The correct response was "It doesn't matter if I'm only going to fight people who are 6'2" and have blue eyes" ... which would have been a good point. –  Jason Baker Jan 8 '11 at 14:55
add comment

I don't worry about generalizing code until at least the second use case. It can be difficult to predict how code will be used in the future, which makes it more difficult to determine in advance what will need to be generalized. If you have an example on hand, that makes the process much easier and more accurate.

share|improve this answer
add comment

Most of the answers so far do not completely reflect my view.

The most important thing about writing code is to accept that you do not write code in isolation. You may have other developers on the same team as you. Other developers may need to use your code as a library, and after you move on, other developers will maintain and extend your code.

When you start thinking about your team mates, concepts such as consistent solutions for similar issues, using techniques that are understood, rather than obscure C syntax will help you in deciding how to manage complexity.

My final thoughts on this though are to think about the different viewers / users of your code. People that use your classes will appreciate the simplicity of use that you create by doing all the complex stuff internally. The maintenance programmer might however find that having the code spread around several different classes to be disorientating when they are trying to track down a bug.

share|improve this answer
add comment

It's hard to reply without a complete understanding of the scenario. Could be that that function will be used in a (let's say) 3d vg where we know almost for sure we'll need a generic one in near future. Or it could be used for some calculations that needs square matrices only.

When in doubt I try to use the Yagni principle mentioned above, but in the more general case for me the OpenClosed principle is very useful:

"software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification"

http://en.wikipedia.org/wiki/Open/closed_principle

share|improve this answer
add comment

The answer is simple in object-oriented programming: if your class does more than one thing, keep generalizing. http://en.wikipedia.org/wiki/Single_responsibility_principle

Following the SRP will also enhance expressiveness/readability. Your code will be declarative, rather than imperative. The result is code that is easier to understand and maintain in spite of the supposed complexity. Each component is simple and straightforward, though the interaction of the whole becomes something greater.

That said, don't over-engineer solutions to solve problems that you don't yet have.

share|improve this answer
add comment

I don't know who it was that said code complexity scales with the square of the number of features, but that seems relevant here. Development time and complexity are both expenses, the latter to be paid in the future, and any investments there should be justified at least by a plausible explanation for why this functionality will be needed later.

A golden middle way would be to develop with future extensions in mind, using only the clearest names and structures. This would be a double bonus - Code simplicity would benefit both for maintenance and extension.

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.