Adding complexity by generalising: how far should you go? [duplicate]

Question

Reference question: https://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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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'.

Answer 6

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.

Answer 7

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.

Answer 8

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 :)

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

The interview question was probably designed to test the subject would notice that there were only n+1 possible different rows; if any row ended with a zero, it would be the smallest. Otherwise the smallest row would be 000...001. Although in general it is better to design methods that will work with arbitrarily-sized NxM matrices rather than NxN, such an assumption is predicated upon the fact that most methods either only make sense with square matrices or else don't really care about matrix shape. An efficient solution for the general problem will be much more complex than code which simply tests whether the last column contains any zeroes.

To use an analogy, suppose a program will receive a list of 999,999 distinct numbers from 1 to 1,000,000 and tasked to identify the "missing" number. The simplest algorithm would be to "xor" together all the numbers and compare that result with the xor of the numbers from 1 to 1,000,000. If the list had only 999,998 distinct numbers, finding even one of the missing numbers would be much harder, but there's no need for an algorithm that can handle that case.

Answer 15

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.