Is the algorithm more important than the programming language?

Question

During the current (2013) Google Code Jam contest, there was a problem that took C++ and Java people 200+ lines of code as compared to Python people that solved the same problem only using 40 lines of code.

Python is not directly comparable with C++ and Java but the difference in verbosity I thought might perhaps have an influence on the efficiency of the algorithm.

How important is knowing the right algorithm compared to the choice of language? Could an excellently implemented Python program be implemented in C++ or Java in a better way (using the same algorithm) and does this have any relation to the natural verbosity of certain programming languages?

Answer 1

Obviously, if you consider this question in the context of something like Google Code Jam, then algorithmic thinking is clearly more important when having to solve algorithmic problems.

In everyday life, however, about a million other factors have to be considered as well, which makes the question much less black vs white.

Just a counter-example: If you need 200 more lines in Java, but everyone in your company knows Java, this isn't a big deal. If you could write it in 5 lines of Python or any other language, but you would be the only one in the company to know that language - it is a big deal. Such big a deal in fact, that you will not even be allowed to do so and instead have to write it in Java.

From a craftman's perspective, we always try to approach with the right tool for the job, but the word right in there is so tricky that one can easily get it wrong.

On the contrary, I found algorithmic thinking in companies to be almost absent. Only few select people possess it, whereas the average joe often already has troubles estimating runtime complexities of loops, searches, etc.

In terms of algorithmic competitions, however, my personal experience from competing in them for several years, clearly tells me that you should stick to one language. Speed is a major factor and you simply cannot afford to waste time on your tools, when you should dedicate it to solving the problems within the time limit. Also consider that writing 200 lines of Java code without thinking is still much faster than hand-crafting 50 lines of complicated python code requiring a lot of thinking, yet both solving more or less the same problem.

Oh and finally, make sure you understand the major differences between algorithmic competition code and company production code. I have seen fantastic algorithmic coders, that wrote horrible code I would not ever accept in a product.

Answer 2

I would argue that, even outside competitions, algorithmic thinking is more important than knowing every trick for a specific language.

Of course, you want to know the language you work with as well as possible, but languages come and go, while the ability to think abstractly in terms of algorithms is a highly transferable skill.

Case in point: if I recall correctly, there was a post here on Programmers a while ago in which someone complained about failing FizzBuzz in an interview and blamed his lack of knowledge about Java's modulo operator for it. This conclusion is wrong -- the lack of knowledge about how modulo works made him unable to think algorithmically about the problem and solve it, even in the absence of a dedicated modulo operator. Going further: Java has a Tree class -- what if, in future, you have to work with a language that does not implement this class? Again, the ability to think about the problem trumps language-specific details.

I admit that the examples are simplistic, but they help to bring the point across.

Answer 3

Language matters.

DARPA and the US Navy did a shootout experiment almost 20 years ago. The dark horse runaway winner was Haskell. Ada and C++ were both represented; Java was not.

Around the same time, Pratt & Whitney did a data mining study on jet engine controller projects, looking at timecard and bug tracker data. They discovered that Ada gave double the programmer productivity and 1/4 the defect density of any other language they were using.

Atari used to use FORTH to develop videogames, and the fact that they were using FORTH was considered extremely proprietary.

Paul Graham's comments on using LISP are well-known. Erann Gat's comments on LISP at JPL are equally cogent, although not as well-known.

The Boeing 777 avionics software is pretty much all Ada. Their experience was very good, even though one major subcontractor had to start over in mid-stream.

Language matters.

Answer 4

Some points:

• The top positions tend to be C++ / C / Java, regardless of how many lines of code the difference is between that and some other language. This may be more about that the top coders tend to pick these languages over some others, probably because of their raw speed.
  Unfortunately you can't easily see the programming language on Google Code Jam, but I downloaded a few of the top ones and, as far as I remember, these are mostly C / C++. TopCoder (a popular online programming contest hosting site) mostly has similar results.

• Because they are pretty low level, I'm pretty sure you're not going to easily beat C / C++ in terms of raw running time (and Java's doesn't trail too far behind). From my experience, dynamically typed languages tend to be significantly slower than statically typed languages. The optimal solution may not even be fast enough in some languages, but this shouldn't be a general rule.

• The right algorithm is vital. If you knew how to solve all the problems (in high detail) from the start, and you're a good, fast coder, you'll most likely win, regardless of which language you code in (assuming the optimal solution in that language is fast enough).

• Straight number of lines isn't such a big deal. Once you get enough programming experience, you'll know that you can spend 10 minutes programming 10 lines or 200 lines, it all depends how complex the lines are. Also, if you've coded up similar code hundreds of times, you'll be able to do so pretty quickly. Not too mention all the macro's that top C / C++ coders often use to optimise their coding time.

• Frank makes a good point - (outside of programming competitions) you can't go about coding in Python for your company if their entire code base is in C or whatever, you need to conform to their language.

• It's reasonably easy to switch between languages, it's not easy to build up years of algorithmic thinking knowledge. I'm willing to bet almost any excellent programmer can switch to another (vaguely similar) language in, let's say, a week. Maybe he/she won't be good enough to win programming competitions in that language (give it another 2 weeks), but will have the basics down.

Answer 5

Can same logic be implemented better in C++? Of course it can, if by better you mean faster and more memory efficient. Problem is that amount of effort required to do so is significantly higher. Furthermore, theoretically you could still go lower level and implement it in pure C or even ASM, which would take even longer, but you could have even more optimized code.

Of course, in case of competitions like Code Jam or TopCoder it isn't a biggie, as it's just 40 lines vs 200 lines. On the other hand in this type of competition what matters the most is the time/space complexity of the algorithm. While in real life application, YMMV, in these types of competitions O(n) algorithm written in slowest of languages will always beat O(n²) written in fastest of languages. Especially that there will be multiple test that are the worst case scenario.

But apart the competitions, if we're talking real life big projects, then it's no longer 40 lines vs 200 lines. In big projects it huge code base starts to be a problem. At which point you get to:

C++ vs Python?

Pure Python is slow. That's why standard Python interpreter (CPython) is written in C. Practically all with built-in functions written as highly optimized C. Python also can be easily used in conjunction with C libraries (via ctypes or as native cpython modules) and with C++ libraries via Boost::Python. This way you can write your high level logic in Python, a language that is flexible, allows quick prototyping and adaptation (meaning that you can spend more time tweaking and improving your algorithm). OTOH, you can write your lower level library functions in C or C++ module. Great example of such a approach is SciPy, which is Python library, yet under the hood it uses highly optimized numeric libraries such as ATLAS, LAPACK, Intels MKL or AMD's ACML.

Answer 6

In my opinion what people colloquially consider a "programming languages" are actually three separate things:

1. Language type and syntax
2. Language IDE
3. Available libraries for a language

For instance when somebody brings up C# in a discussion you may think he/she is talking about language syntax (1) but it's 95% certain that the discussion will involve .Net framework (3). If you are not designing a new language, it's hard and usually pointless to isolate (1) and ignore (2) and (3). That's because IDE and standard library are "comfort factors", things that directly affect the experience of using a certain tool.

Last few years I too participated in Google Code Jam. First time I opted for C++ because it has nice support for reading the input. For example reading three integers from a standard input in C++ looks like this:

int n, h, w;
cin >> n >> h >> w;

While in C# the same would look like this:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

That's a lot more mental overhead for a simple functionality. Things get even more complicated in C# with multiline input. Maybe I simply haven't figured out a better way back then. Anyway, I failed to pass the first round because I had a bug that I couldn't correct before the end of the round. Ironically the input reading method obfuscated the bug. Problem was simple, input contained a number that was too big for 32 bit integer. In C# int.Parse(string) would throw an exception but in C++ the file input stream would set a certain error flag and fail silently making unsuspecting developer unaware of a problem.

Both examples demonstrate how the library was used rather then language syntax. First one demonstrates the verbosity and the other demonstrates the reliability. Many libraries are ported to multiple languages and some languages can use libraries that are not specifically built for them (see @vartec's answer about Python with C libraries).

To wrap this up, knowing the right algorithm helps. In coding competitions it's crucial, especially when resources such as execution time and memory are purposely limited. In application development it's welcome but generally not crucial. Maintainability is more important there. It is can be achieved by applying correct design patterns, having good architecture, readable code and relevant documentation and all of those methods heavily depend on in-house and 3rd party libraries. So, I find it more important to know what kind of wheels are already invented and how do they fit then how to make my own.

Answer 7

If you want to compete in timed programming competitions, you should learn the most expressive language allowed in the competition. Perl would probably be best, followed by Ruby or Python. You will still need good facility with algorithms, but at least you won't get bogged down writing something like

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

instead of

b[k] += a[k]

Don't worry about learning several libraries. They are all very similar and the documentation is online. Becoming fluent in more expressive languages will make you a better (but possibly frustrated) programmer in less expressive languages. The opposite is not true.

N.B.

The difference between 200 lines of code and 40 lines of code is huge, and it's even bigger when it's the difference between a 200,000 line program and an 40,000 line program. Then it's the difference between a team of five plus a manager, and a team of one or two.

Answer 8

Any algorithm can be implemented in any programming language. After all, its not the syntax that matters. But using a high level language like Python do have its own advantages. Less work and less amount of coding. So to implement an algorithm in Python, you shall need fewer lines than what is required in a low level language like C.

Python have most of the data structures built into its library. But in C, we need to start from scratch and use a structure to built it all up. Certainly there are differences between the high level and low level language, but the language shouldn't stop you from implementing any algorithm.

Answer 9

While extrapolating the "40 LoC vs 200 LoC" example, saying "well, only a fifth of the total LoC is obviously faster to write so it must be better" may seem tempting, I really think there is little truth to be found there.

Optimizing for fewest LoC is almost never a good idea in my opinion. Yes, every LoC written is a potential for bugs, and you never have to debug what you never wrote etcetc. The point is, optimize for readability and decoupledness. It does not matter if you solve a problem using a 20 lines big regex, as opposed to writing a module of 1k LoC. The regex will be an opaque wall, extremely prone to bugs, hard to understand, nightmarish to alter without changing it's behavior in unoredicatble ways etc.

Getting rid of boilerplate and verbosity that doesn't add any value is all well and good, but on the other hand, using something like Java or C#, having knowledge about design patterns and tools like resharper allow you SO much flexibility in refactoring the code, cleaning it up over time, breaking things down, etc., that would simply be MUCH harder had you written it as a much smaller python script or ruby app.

A very telling comparison: I would rather have 100k LoC of test-covered decoupled C# code, filled with "overkill" stuff like strategy pattern, factories etc, rather than a 20k python app that just "gets stuff done". 5 times more code or not, the architecture wins every day.

I fully agree some kinds of work are easier and more convenient in some languages, but I believe more in choosing your language based on what tools you need and what the requirements are (and might be in the near future).