Thread: prime numbers and time consuming

Originally Posted by AntP

Again, this isn't what I'm saying at all. At least, it wasn't, before people blew my point way out of proportion and twisted what I was trying to say into "C iz slow ruby is bettar lolll."

My point was simply that it's not a tautology that C will be quicker for a given task. Take your string matching example, for instance. There's no reason why C couldn't outperform Python for string matching/manipulation tasks but, given the sheer amount of work and research that it would take to implement algorithms of equivalent intelligence in C (to those that are already standard in Python), it's not wrong to assert that - in practical terms - Python will outperform C on this front.

Of course it would be possible to do marginally better with C, but the blanket statement that "C will always outperform an interpreted language" is extremely misleading as someone who didn't know better could infer from it that "writing my own function in C would be quicker than using this built in one in Python." You have to bear in mind that many people (and many programmers) aren't familiar with the notion of asymptotic time complexity and thus would see nothing wrong with making this inference.

C will always outperform an interpreted language BECAUSE it is not interpreted. You can implement the same algorithm that your fancy interpreted language has in C with no issues whatsoever. You are comparing apples and oranges here. You are saying: "An interpreted language will outperform C on different algorithms"... well doh. You can't compare performance on two different algorithms and then claim that the language that the superior algorithm is implemented in performs better. Take a standard algorithm, say mergesort, test it using your interpreted language library version, and then write THE EXACT SAME ALGORITHM in C. Then tell us which one performs better.

The fact that you work more to write it in C has nothing to do with performance. Performance is related exclusively to the attributes of your program not to your development time. Stop mixing the two up!

Originally Posted by claudiu

C will always outperform an interpreted language BECAUSE it is not interpreted. You can implement the same algorithm that your fancy interpreted language has in C with no issues whatsoever. You are comparing apples and oranges here. You are saying: "An interpreted language will outperform C on different algorithms"... well doh. You can't compare performance on two different algorithms and then claim that the language that the superior algorithm is implemented in performs better. Take a standard algorithm, say mergesort, test it using your interpreted language library version, and then write THE EXACT SAME ALGORITHM in C. Then tell us which one performs better.

The fact that you work more to write it in C has nothing to do with performance. Performance is related exclusively to the attributes of your program not to your development time. Stop mixing the two up!

Again, you have completely sidestepped my point. I am not mixing anything up. You are either confused or you are intentionally using strawman arguments.

You are arguing with points I never made. And you are being rather crass about it. I repeat:

The blanket statement that "C will always outperform an interpreted language" is extremely misleading as someone who didn't know better could infer from it that "writing my own function in C would be quicker than using this built in one in Python." You have to bear in mind that many people (and many programmers) aren't familiar with the notion of asymptotic time complexity and thus would see nothing wrong with making this inference.

My entire point was that the algorithms in a higher-level interpreted language are probably better (assuming they are appropriate) than the ones you could write yourself, which will be reflected in performance. That's it. You have continued to put words in my mouth since then.

I'm going to stop responding to you now because I find you quite unpleasant.

Originally Posted by AntP

Again, you have completely sidestepped my point. I am not mixing anything up. You are either confused or you are intentionally using strawman arguments.

You are arguing with points I never made. And you are being rather crass about it. I repeat:



My entire point was that the algorithms in a higher-level interpreted language are probably better (assuming they are appropriate) than the ones you could write yourself, which will be reflected in performance. That's it. You have continued to put words in my mouth since then.

I'm going to stop responding to you now because I find you quite unpleasant.

I understood your point perfectly and all I am saying is that you are dead wrong. There is nothing to debate here, because your conclusion is not based on any verifiable claims. In fact most evidence out there points to the exact opposite: that interpreted languages are slower. In terms of what I can and cannot write, I too, like many others here have formal education in computer science so I am pretty comfortable developing my own algorithms. In this sense, I don't think the algorithms provided by some library in some interpreted language are as magical as you claim them to be and can be easily understood and implemented in another.

I will stand corrected if you try to run a test like Adak suggested in which you clearly demonstrate that for a given algorithm an interpreted language will outperform one written by one of the people here in C. You will be in for quite a surprise when you realize that many people here have the skill, ability and experience to implement more efficient algorithms than the ones you can come up with from standard libraries.

I am sorry if I have been "crass" but providing misleading information on a C forum about C will earn you some prompt replies.

Sigh, do we have to go through this kind of arguments? Let's examine the statements:

Originally Posted by Gustaff

Im using APL as my programming language. I would like to see if C is faster.
(APL is an interpreter)

Originally Posted by Adak

C is one of the faster (perhaps the fastest depending on the program and compiler), language. It *is* going to be considerably faster than an interpreted language - any interpreted language.

Originally Posted by AntP

Depends. In the majority of problems (this one included), computational complexity will have a much greater effect on running time than things like caching and other such compiler optimizations.

Frankly, I think that both Adak and AntP are right. It is nonsense to talk about a programming language being faster than another, so it must surely be implied that both Gustaff and Adak are talking about comparing the performance of some optimal solution in APL with a corresponding optimal solution in C. AntP's point is that the solutions may not be optimal, and that certainly makes sense as Gustaff does not appear to be familiar with both C and the algorithms concerning this problem.

Originally Posted by AntP

Higher-level, interpreted languages tend to use very well-optimized algorithms in their standard libraries, for procedures that C may not have at all, thereby requiring the programmer to come up with the algorithm. Designing a good algorithm is often extremely unintuitive and, no matter how good a programmer you are, the complexity of the algorithm in the standard libraries is almost guaranteed at least to match yours; most likely, it will be several orders better.

The above also makes sense. However, it is a myopic view in that it ignores the fact that domain experts do write C libraries (which may even be used to implement the library functionality for these other programming languages), and C programmers are not restricted to the C standard library. Consequently, this conclusion does not follow the argument:

Originally Posted by AntP

So, in practice, it is often the case that the interpreted language will outperform the lower-level compiled language.

Furthermore, this point may be moot to begin with, if APL does not have primality testing functionality in its standard/built-in library.

Originally Posted by laserlight

...

Thanks for summarising. It was, indeed, my original intention merely to note, for the sake of the OP, that it is not simply the programming language that determines efficiency - but also the manner in which the problem is solved - and that (regardless of the language) library functions will likely do a very good job of performing a task, where your own solution may not. So, in a sense, I guess "merge sort in Ruby outperforms bubble sort in C" isn't too bad an example. Given the context of the thread, I feel that this was an entirely reasonable thing to note.

It was never my intention to suggest that interpreted languages were inherently faster than compiled ones, nor that it is impossible to match or better a standard library function (hence the use of the word 'depends' in my first post), though it seems such inferences were made. I think after this the meaning of my original post was lost. Perhaps I didn't do a very good job of clarifying, but I tend to get a little wound up when people begin their responses to my well-intentioned posts with "Uhh, no!"

Except we were talking about APL rather than any generic interpreted language. If you know something about APL then you understand that it's unique in that it has an extremely high built-in-algorithm to interpreter overhead quotient. In fact, a good APL programmer will code in a way that favors certain array and vector products that may not be considered in other languages because APL provides a plethora of built-in primitives that deal with multi dimensional arrays natively.

For example, APL has a built-in sort (ranking) operator. So some of the arguments above that claim interpreters are necessarily slower are not 100% true. In APL, the number of tokens or symbols needed to be "interpreted" for a sort function is exactly one. That's it. One character. How slow do you think that makes it? The actual sorting is done via algorithm that was implemented by experts. Probably coded in assembler.

Another point: APL has matrix inverse, matrix divide, vector inner and outer products, determinants, least-squares-fit, any number of transposes, rotates, permutations of matrix dimensions (planes, rows, columns), selection, slicing, dicing, etc. None of these things need to be coded by the programmer. Many algorithms that would normally be left to possibly inexperienced programmers are already available. Again, a few single primitive symbols and the internal, highly efficient algorithms are invoked.

The interpreter is something like: read a character, do a million operations, read another character, do another million. Program is done.
What? It was interpreted? Oh golly gee. It was inconsequential.

So in the defense of APL as an interpreter, and only APL, it has been clocked against code written in FORTRAN and won favorably except where the FORTRAN libraries were better optimized than APL libraries. The point that APL is interpreted can not be held against it as much as it can for other interpreters. APL is different.

</soapbox>