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.

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?

share|improve this question
14  
It's been said (and I believe it) that the programming language you work in has an influence on the way you think about a problem. This would imply that very different programming languages might be suited to different classes of problems. –  Joris Timmermans Apr 25 '13 at 8:37
1  
A lot of this entirely depends on the scale you are working on beyond LOC. Some languages just don't either support the speed or concurrency needs. Algorithms are important but sometimes if language x is y times slower than language z you simply can't use x regardless of verbosity. –  Rig Apr 25 '13 at 13:46
    
As a note the only thing that I've learned in school is that everyone has a bug per lines of code that remains constant independent of code used. So, if a language that allows you to do it in fewer lines of code results in fewer bugs therefore, you can get it to market faster and the less of a chance a bug will show up when a user is using it. So, in my opinion I would pick the best language for the job which everyone else in the company knows that is required to work on that project. –  Travis Pessetto Apr 25 '13 at 16:01
3  
@Travis: "defect per SLOC rate remains constant regardless of language" just isn't true though. See John's answer. –  Ben Voigt Apr 25 '13 at 18:06
    
Now you have me thinking about entering the next contest using F# as the language! –  code4life May 3 '13 at 20:19

8 Answers 8

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.

share|improve this answer
1  
+ 1 for "million other factors to be considered" –  jmo21 Apr 25 '13 at 10:35
1  
I will add to this that if it's a functional problem you're trying to solve, then for heavens sake, please use a functional language! So I'd argue that you should really stick one language per major programming paradigm. –  Martijn Verburg Apr 25 '13 at 10:55
6  
+1 for the last sentence. –  Shivan Dragon Apr 26 '13 at 13:23
2  
+1 Lines of code is a terrible metric by itself. We need to measure maintainability, not lines of code. 200 lines of type-safe code can potentially be a lot more maintainable than 50 lines of Python. –  Phil Apr 26 '13 at 16:46
1  
@Phil: And 200 lines of Python can potentially be a lot more maintainable than 50 lines of type-safe code. I've never seen that much clarity advantage in type-safe languages, assuming well-written code. –  David Thornley Apr 26 '13 at 17:49

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.

share|improve this answer
    
+1, I remember that question - good simple example –  Izkata Apr 25 '13 at 15:54

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.

share|improve this answer
    
Obviously, java was released after that experiment you're linking to. –  toasted_flakes May 13 '13 at 12:46

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.

share|improve this answer
    
Falsehood: Downloading several solutions from some code contest sites is a definitive scientific study sufficient to conclude that you definitely know for a fact what the top positions looks like. –  Lie Ryan Apr 25 '13 at 10:15
    
@LieRyan True, but taking part in a few dozen programming competitions (as I have) on (arguably) the most popular such site (TopCoder) and always seeing majority of top positions as C / C++ / Java is rather significant. Also, I said "tend to" not "are always". –  Dukeling Apr 25 '13 at 10:19
    
disagree that "Straight number of lines isn't such a big deal." code is the enemy –  jk. Apr 25 '13 at 10:33
6  
@jk. Should I have highlighted "such"? It matters, but it isn't the alpha and omega. You prefer a few less lines to readability? I sure don't. I'll take a few simple if-statements to a very confusing, unreadable, bit-shifting, multiplying, dividing, adding, subtracting, XORing, ANDing, multi-conditional expression any day. Possibly not what you were talking about, but that's what reducing line count comes down to sometimes. And I was more talking about implementing something complex in few lines, or something simple in many lines; the latter often takes less time. –  Dukeling Apr 25 '13 at 10:53

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?

enter image description here

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.

share|improve this answer
    
What you're writing only scrapes the surface. You are assuming a notion of 'better' that not everyone shares. Quality is always a matter of suitability to one's goals. Programming in C++ isn't always a good fit for every goal. –  reinierpost Apr 25 '13 at 11:59
1  
@reinierpost: that's why I wrote about significantly higher effort. In the cases you mention C++ isn't good fit, but not because it cannot be done. It's not good fit, because it'll take too much developer resources. –  vartec Apr 25 '13 at 12:04
    
What is more, it just isn't better in that case. –  reinierpost Apr 25 '13 at 13:31
2  
and in fact this is what happens in a lot of industries, games for example have a lot of Lua code that glues C++ code together for both performance and productivity. –  gbjbaanb Apr 25 '13 at 21:16

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.

share|improve this answer
1  
Preparation is important when possible. With Google Code Jam I have a small library that reads input and displays output as they want it, and I include that code in my submission. –  Mark Hurd May 1 '13 at 4:29
    
Second time I did something similar but as a project template. It creates a source file with an input class below Main and few things inside Main method (instance of my input class and the output stream and case loop). –  Emperor Orionii May 2 '13 at 7:26

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.

share|improve this answer
3  
(a) I know for a fact that C / C++ / Java tend to be the top positions in programming competitions. (b) C / C++ is considered of the "most powerful language"s by many (definitely above Perl / Ruby / Python). (c) Because of operator overloading, C++ code can look almost identical to your second example. (d) Such extensive checking (in Java, is it?) is only required if: (1) You have no idea what you're doing. (2) The nature of the data is such that this is required (doesn't happen in coding competitions). (3) You're writing code to be used by other people (not applicable). –  Dukeling Apr 25 '13 at 9:18
    
@Dukeling: According to this study (page.mi.fu-berlin.de/prechelt/Biblio/jccpprtTR.pdf) scripting languages allow faster development and smaller source code. According to another study (flownet.com/gat/papers/lisp-java.pdf), Lisp offers even more productivity than scripting languages. According to the second study cited above, Lisp code turns out to be almost as fast as C++ code while it takes less time to write. –  Giorgio Apr 25 '13 at 11:09
    
"between a 200,000 line program and an 40,000 line program": I think you have to distinguish. Differences due to programming language verbosity (syntax) do not add complexity to the code and therefore can have little impact on the required maintenance effort. On the other hand, you can have a different line count because of different language features. E.g. in Python you do not have to manage memory while in C you have to implement all your memory management yourself. Then I agree with you that in the C code you have more functionality and you definitely need extra maintenance time. –  Giorgio Apr 25 '13 at 11:26
    
@Giorgio I'm not arguing about development time or size of source code, purely what actually happens in programming competitions, based on significant experience. –  Dukeling Apr 25 '13 at 11:28
1  
I was citing two scientific papers (which IMO are worth taking a look at), I was not speaking about what people on web pages think about it. The fact that an opinion is wide spread does not automatically imply that it is valid. :-) At least, one has to verify it in some rigorous way. –  Giorgio Apr 25 '13 at 11:51

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.

share|improve this answer

protected by maple_shaft Apr 25 '13 at 12:56

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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