Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > optimizing code: sort algorithm, random numbers etc. Best resources for optimization?

Reply
Thread Tools

optimizing code: sort algorithm, random numbers etc. Best resources for optimization?

 
 
PWalker
Guest
Posts: n/a
 
      12-15-2004
Hi, I have written code that I would like to optimize. I need to push it to
the limit interms of speed as the accuracy of results are proportional to
runtime.

First off, would anyone know any resources that explains how to optimize
code i.e. give some rules on c++ optimization? e.g. using memcpy to copy an
array (which i have done).

Also, what is the best sorting algorithm out there for sorting an array of
of size 100 or less? I have considered heapsort and insertsort. I am however
wanting to find the fastest.

Also I'm looking for a good fast random number generator. I am currently
using Boost:

boost::minstd_rand
boost::uniform_real<>
boost::uniform_int<>
boost::variate_generator<boost::minstd_rand, boost::uniform_real<> >
boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >

Is the Mersenne-Twister RNG faster/better?

I am running VC++ 7 on an AMD Mobile XP 2600+ if that helps.

Thanks!
Cheers,
Peter


 
Reply With Quote
 
 
 
 
Puppet_Sock
Guest
Posts: n/a
 
      12-15-2004
PWalker wrote:
[bunch of questions not directly related to C++ language]

Most of your questions will be best addressed with a web search.
Say you start at www.google.com, and possibly with groups.google.com.
Socks

 
Reply With Quote
 
 
 
 
Ivan Vecerina
Guest
Posts: n/a
 
      12-15-2004
"PWalker" <(E-Mail Removed)> wrote in message
news:41c059dd$(E-Mail Removed)...
> Hi, I have written code that I would like to optimize. I need to push it
> to the limit interms of speed as the accuracy of results are proportional
> to runtime.
>
> First off, would anyone know any resources that explains how to optimize
> code i.e. give some rules on c++ optimization? e.g. using memcpy to copy
> an array (which i have done).

This may not always be a good idea. Beware of undefined behavior...

> Also, what is the best sorting algorithm out there for sorting an array of
> of size 100 or less? I have considered heapsort and insertsort. I am
> however wanting to find the fastest.


Try std::sort. In popular C++ library implementations, it is based on
the IntroSort algorithm, which itself is an improvement over the famed
QuickSort. But the best approach will depend on the contents of the
array (e.g. sometimes a linked list based MergeSort, with guaranteed
NlgN complexity and reduced number of object copies may do better).

> Also I'm looking for a good fast random number generator. I am currently
> using Boost:
>
> boost::minstd_rand
> boost::uniform_real<>
> boost::uniform_int<>
> boost::variate_generator<boost::minstd_rand, boost::uniform_real<> >
> boost::variate_generator<boost::minstd_rand, boost::uniform_int<> >
>
> Is the Mersenne-Twister RNG faster/better?


How do you define "better" ?
To what extent is RNG speed relevant to your problem ?


The most critical rule when optimizing code is to *measure first*.
From your post, it does not sound like you have done much
profiling so far.
Do you know what percentage of the execution time is spent on
sorting or on other functions?
If not, it is likely that you are wasting your time.

Next, you need to look at algorithms complexity, and avoid
doing any computations when possible (e.g. caching, etc...).

Tertio, remember that memory access is the bottleneck of many
computer programs today. Try to make your memory accesses
contiguous and cache friendly (e.g. use in-lined data members
instead of pointers to separate objects; use arrays and std::vector
instead of other object collections when possible).


For C++ itself, all you need is to be aware of the cost of
some features (e.g. exceptions if relevant, virtual calls,
construction/destruction of objects, etc).

Also, remember to 'tune' the compiler options for generating fast
code. You may even consider switching compilers (some generate
noticeably faster code than others).


There are many targeted optimization techniques and approaches,
but you have given too little information about the kind of
problem that you are working on...


But again: measure first to know what part of your system
should be the target of your optimization efforts.


Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com


 
Reply With Quote
 
richardv2
Guest
Posts: n/a
 
      12-15-2004
The answer to almost every "Which sort is fastest?" question is "It
depends."

The slightly smart bubble sort will kick butt on a list that was sorted
recently and has just had a few additions at the end.

When I needed these answers for work problems years ago, I could only
program each as best I could, then try them with normal distribution
(what I usually gave to the sort), then some completely random, then
some *almost* sorted samples.

Back then, I chose the second best (Shell) over the fastest (QuickSort)
because I actually understood Shell. (Could write the code as fast as I
could type.) but I could not remember Quick well enough to write or
troubleshoot in my head. And the time difference was minimal.

Yesterday I sorted 10,000 floats in 0.6 seconds with a not so great
algorithm. When I last did this that would have taken quite a long
time!

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
FAQ 4.10 Why aren't my random numbers random? PerlFAQ Server Perl Misc 0 02-12-2011 11:00 PM
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
How do I get a random number between two random numbers? Alex Untitled Ruby 11 11-16-2009 09:45 AM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
Array sort function sorts on chars not numbers ... help ! how to sort numbers GIMME Javascript 5 07-26-2004 01:28 AM



Advertisments