27 Jan 2013 @ 9:36 AM 

 

This is part of a occasionally updated series on various programming languages. It should not be interpreted as a benchmark, but rather as a casual look at various programming languages and how they might be used by somebody for a practical purpose.
Currently, there are Articles written regarding Python,C#, Java and VB6 (merged for some reason),Scala,F# & Ruby,Perl, Delphi, PHP,C++,Haskell,D, VB.NET, and even QuickBASIC

Though I didn’t plan on it, somehow I got around to actually implementing the C++ variant of the anagrams program I have been re-implementing in various languages to try to compare their linquistic and performance attributes.

The algorithm is relatively simple. it seeks to take an input file, a list of words, and determine which words are anagrams of one another. This is done by sorting each word (by it’s letters) and using that sorted word as an index into Hashmap or Hashtable or equivalent structure, adding the original word to a list stored in that structure. When the program is complete, each entry in the hashmap that has more than one item contains words that are anagrams of one another.

The C++ program I created that did this is this:

The execution time of this little bugger? around half a second, on average. This puts it on par with F#; but given it is C++, you would expect it to have the blazing speed that people often attribute C++ with; Too often you see people saying “Language X is too slow; they should rewrite this in C++”. Now, is this implementation of the algorithm as I’ve done it in C++ the fastest possible one? No, certainly not. But I think the code maintenance consideration is a big one. It makes sense to strive for the fastest possible program, but when you are only getting tiny gains from a complete rewrite and have to start really digging into the implementation to make things faster, I think you’ve passed the point where it can be particularly useful.

In this specific case, the RAII that I use appears to have a rather large effect on performance. the inner conditional if, for example, constructs a vector, and then tears it down when it goes out of scope. the cost of the delete each iteration ends up with a total time of around 18% of the entire program run. An optimization here might be to use a dynamically allocated vector. Another option might be to read the documentation: the entire if block is actually redundant, since the HashMap will actually construct the vector itself as part of it’s templature. As a result, the new code is:

The new execution time averages around 0.4 seconds- so we saved about 18% of the execution time, as one would expect. And the resulting code is much shorter, which cannot be overstated.

But still- this difference does not really convince me of C++ being the “fastest” language. Surely you can write faster code in C++ if you know exactly what you are doing, but that isn’t usually needed. In this case, we are dealing with over 200 thousand words, and truthfully very few of the programs I’ve presented on this issue really present scalability problems; even Ruby’s ten seconds could be mitigated if necessary using any number of caching techniques. Of course the downside here is that such improvements require more code, which means more interpretation, which means it could very well end up right back where it started anyway.

Have something to say about this post? Comment!

Posted By: BC_Programming
Last Edit: 14 Jun 2017 @ 07:20 AM

EmailPermalink
Tags
Categories: Programming


 

Responses to this post » (None)

 
Post a Comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">


 Last 50 Posts
 Back
Change Theme...
  • Users » 45017
  • Posts/Pages » 369
  • Comments » 105
Change Theme...
  • VoidVoid « Default
  • LifeLife
  • EarthEarth
  • WindWind
  • WaterWater
  • FireFire
  • LightLight

PP



    No Child Pages.

Windows optimization tips



    No Child Pages.

Software Picks



    No Child Pages.