Performance of sorting procedures

1. Results

   Those results were generated with vs2012 Release configuration and full optimization: (\Ox):
   sort (tmp.begin(),tmp.end(),less<int>()): 399.258 milliseconds
   sort (tmp.begin(),tmp.end()): 402.652 milliseconds
   sort (tmp.begin(),tmp.end(), (lessFunction<int>)): 2.11581 seconds
   qsort (&tmp[0],tmp.size(),sizeof(int), compare): 2.43363 seconds
   

2. Code

   #include <windows.h>
   
   #include <vector>
   #include <cstdlib>
   #include <iostream>
   #include <ostream>
   #include <sstream>
   #include <set>
   #include <string>
   #include <algorithm>
   #include <numeric>
   #include <future>
   #include <functional>
   
   using namespace std;
   size_t MAX_SIZE = (1 << 28) + 1;
   
   long long timer() {
       LARGE_INTEGER li;
       QueryPerformanceCounter(&li);
       return li.QuadPart;
   }
   long long frequency() {
       LARGE_INTEGER li;
       QueryPerformanceFrequency(&li);
       return li.QuadPart;
   }
   string format_time(const long long dt) {
       ostringstream oss;
       if ((dt) * 1000 < frequency()) {
           oss << (dt) * 1000000.0 / frequency() << " microseconds";
       } else if (dt < frequency()) {
           oss << (dt) * 1000.0 / frequency() << " milliseconds";
       } else {
           oss << (dt) * 1.0 / frequency() << " seconds";
       }
       return oss.str();
   }
   
   void fillRandomVector (vector <int> *v)
   {
       srand (0);
       for (auto i:*v)
           i = rand();
   }
   
   template <typename T>
   bool lessFunction(const T &d1, const T &d2)
   {
       return d1 < d2;
   }
   
   int compare (const void * a, const void * b)
   {
       return ( *(int*)a - *(int*)b );
   }
   
   int main()
   {
       typedef pair<long long, string> tTiemrResult;
       vector <tTiemrResult> tx;
   
       vector <int> tmp (MAX_SIZE);
   
       fillRandomVector (&tmp);
       tx.push_back(tTiemrResult(timer(),"start"));
       sort (tmp.begin(),tmp.end());
       tx.push_back(tTiemrResult(timer(),"sort (tmp.begin(),tmp.end())"));
   
       fillRandomVector (&tmp);
       tx.push_back(tTiemrResult(timer(),"start"));
       sort (tmp.begin(),tmp.end(),less<int>());
       tx.push_back(tTiemrResult(timer(),"sort (tmp.begin(),tmp.end(),less<int>())"));
   
       fillRandomVector (&tmp);
       tx.push_back(tTiemrResult(timer(),"start"));
       sort (tmp.begin(),tmp.end(), (lessFunction<int>));
       tx.push_back(tTiemrResult(timer(),"sort (tmp.begin(),tmp.end(), (lessFunction<int>))"));
   
       fillRandomVector (&tmp);
       tx.push_back(tTiemrResult(timer(),"start"));
       qsort (&tmp[0],tmp.size(),sizeof(int), compare);
       tx.push_back(tTiemrResult(timer(),"qsort (&tmp[0],tmp.size(),sizeof(int), compare)"));
   
       vector <tTiemrResult> tx2;
       for (size_t i=1; i < tx.size() ; i++)
           tx2.push_back(tTiemrResult(tx[i].first - tx[i-1].first, tx[i].second));
       sort (tx2.begin(), tx2.end());
       for (auto i:tx2)
           cout<<i.second<<": "<< format_time (i.first)<<endl;
       return 0;
   }
   

Performance of summing procedures.

1. Results
   Those results were generated with vs2012 Release configuration and full optimization:
   
   /c /Zi /nologo /W4 /WX- /Ox /Oy- /GL /D WIN32 /D NDEBUG /D _CONSOLE /D _UNICODE /D UNICODE /Gm- /EHsc /MD /GS /Gy /fp:precise /Zc:wchar_t /Zc:forScope /Fo"RELEASE\\" /Fd"RELEASE\VC110.PDB" /Gd /TP /analyze-
   
   
   asyncTabIndexedSum: 1.69146 seconds (2 cores)
   tabIndexedSum: 2.37756 seconds (optimized for SSE)
   vectorIndexedSum: 3.04009 seconds
   accumulateTabSum: 3.24292 seconds
   accumulateVectorSum: 3.31494 seconds
   vectorRangedSum: 3.35942 seconds
   tabPointeredSum: 3.45808 seconds
2. Code
   
   #include <tchar.h>
   #include <windows.h>
   #include <vector>
   #include <cstdlib>
   #include <iostream>
   #include <ostream>
   #include <sstream>
   #include <set>
   #include <string>
   #include <algorithm>
   #include <numeric>
   #include <future>
   using namespace std;
   size_t MAX_SIZE = (1 << 28) + 1;
   size_t MAX_REPEATS = 10;
   long long timer() {
       LARGE_INTEGER li;
       QueryPerformanceCounter(&li);
       return li.QuadPart;
   }
   long long frequency() {
       LARGE_INTEGER li;
       QueryPerformanceFrequency(&li);
       return li.QuadPart;
   }
   string format_time(const long long dt) {
       ostringstream oss;
       if ((dt) * 1000 < frequency()) {
           oss << (dt) * 1000000.0 / frequency() << " microseconds";
       } else if (dt < frequency()) {
           oss << (dt) * 1000.0 / frequency() << " milliseconds";
       } else {
           oss << (dt) * 1.0 / frequency() << " seconds";
       }
       return oss.str();
   }
   int tabIndexedSum (const int tab[], size_t tabSize)
   {
       int sum = 0;
       for (size_t i = 0; i<tabSize; ++i)
           sum += tab[i];
       return sum;
   }
   int tabPointeredSum (const int *tabBegin, const int *tabEnd)
   {
       int sum = 0;
       for (const int *i = tabBegin; i < tabEnd; ++i)
           sum += *i;
       return sum;
   }
   int vectorIndexedSum (const vector <int> &tab)
   {
       int sum = 0;
       for (size_t i=0;i<tab.size();++i)
           sum += tab[i];
       return sum;
   }
   int vectorRangedSum (const vector <int> &tab)
   {
       int sum = 0;
       for (auto i:tab)
           sum += i;
       return sum;
   }
   int accumulateVectorSum (const vector <int> &tab)
   {
       return accumulate (tab.begin(), tab.end(), 0);
   }
   int accumulateTabSum (const int tab[], size_t tabSize)
   {
       return accumulate (tab, tab + tabSize, 0);
   }
   int asyncTabIndexedSum (const int *tab, size_t tabSize)
   {
       size_t halfSize = tabSize / 2;
       auto s1 = async(launch::async, tabIndexedSum, tab, halfSize);
       auto s2 = async(launch::async, tabIndexedSum, tab +  halfSize, tabSize - halfSize);
       return s1.get() + s2.get();
   }
   int _tmain(int argc, _TCHAR argv[])
   {
       typedef pair<long long, string> tTiemrResult;
       vector <tTiemrResult> tx;
       vector <int> results;
       vector <int> tmp (MAX_SIZE);
       for (size_t i = 0; i < MAX_SIZE; ++i)
           tmp [i] = rand();
     
       tx.push_back(tTiemrResult(timer(),"start"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(tabPointeredSum (&tmp[0], &tmp[0] + MAX_SIZE));
       tx.push_back(tTiemrResult(timer(),"tabPointeredSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(tabIndexedSum (&tmp[0], MAX_SIZE));
       tx.push_back(tTiemrResult(timer(),"tabIndexedSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(accumulateTabSum (&tmp[0], MAX_SIZE));
       tx.push_back(tTiemrResult(timer(),"accumulateTabSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(asyncTabIndexedSum (&tmp[0], MAX_SIZE));
       tx.push_back(tTiemrResult(timer(),"asyncTabIndexedSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(vectorIndexedSum (tmp));
       tx.push_back(tTiemrResult(timer(),"vectorIndexedSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(vectorRangedSum (tmp));
       tx.push_back(tTiemrResult(timer(),"vectorRangedSum"));
       for (size_t i=0;i<MAX_REPEATS;++i)
           results.push_back(accumulateVectorSum (tmp));
       tx.push_back(tTiemrResult(timer(),"accumulateVectorSum"));
       cout << "resultSet: ";
       for (auto i:set <int> (results.begin(),results.end()))
            cout<< i<<", ";
       cout << endl;
       vector <tTiemrResult> tx2;
       for (size_t i=1; i < tx.size() ; i++)
           tx2.push_back(tTiemrResult(tx[i].first - tx[i-1].first, tx[i].second));
       sort (tx2.begin(), tx2.end());
       for (auto i:tx2)
           cout<<i.second<<": "<< format_time (i.first)<<endl;
       return 0;
   }
   

C++ in Action (Industrial Strength Programming) by Bartosz Milewski

http://www.relisoft.com/book/index.htm

1. Don’t use pointers where an index will do.

   a) Strlen using indexes

   int StrLen (char const str [] ) {
      for (int i = 0; str [i] != '\0'; ++i)
         continue;
      return i;
   }
   
   

   b) Strlen using pointers

   int StrLen (char const * pStr) {
      char const * p = pStr;
      while (*p++);
      return p - pStr - 1;
   }
    
   "If your compiler is unable to optimize the human readable, maintainable version of the algorithm, and you have to double as a human compiler-- buy a new compiler! Nobody can afford human compilers any more. So, have mercy on yourself and your fellow programmers who will have to look at your code."
   

2. Fighting Defensive Programming

   "Defensive programming" sounds good, doesn’t it? A program written by a defensive programmer should be safer and more robust, right? Wrong! Defensive programming is a dangerous form of engineering malpractice (in a show of self-abasement I’ll shortly expose examples of such practices in my own code). Defensive programming promotes writing code that is supposed to work even in the face of programmers’ errors, a.k.a. bugs. In practice, it gives the bugs the opportunity to cover their tracks. Anybody who spent a sleepless night chasing a bug that could have been caught early on, if it weren’t for defensive programming, will understand my indignation. In most cases defensive programming is a result of not understanding the exact contract between various parts of the program. A confused or lazy programmer, instead of trying to understand the logic of the program, might write something that should work no matter what. That code will obscure the program's logic even more, making further development even sloppier. The programmer will eventually lose control of the code.
   
   

   
   

How to Solve It (by George Pólya @wiki)

How to Solve It

From Wikipedia, the free encyclopedia

Jump to: navigation, search

How to Solve It (1945) is a small volume by mathematician George Pólya describing methods of problem solving.^[1]

Contents 1 Four principles 1.1 First principle: Understand the problem 1.2 Second principle: Devise a plan 1.3 Third principle: Carry out the plan 1.4 Fourth principle: Review/extend 2 Heuristics 3 Influence 4 See also 5 Notes 6 References 7 External links

Four principles

How to Solve It suggests the following steps when solving a mathematical problem:

1. First, you have to understand the problem.^[2]
2. After understanding, then make a plan.^[3]
3. Carry out the plan.^[4]
4. Look back on your work.^[5] How could it be better?

If this technique fails, Pólya advises:^[6] "If you can't solve a problem, then there is an easier problem you can solve: find it."^[7] Or: "If you cannot solve the proposed problem, try to solve first some related problem. Could you imagine a more accessible related problem?"

First principle: Understand the problem

"Understand the problem" is often neglected as being obvious and is not even mentioned in many mathematics classes. Yet students are often stymied in their efforts to solve it, simply because they don't understand it fully, or even in part. In order to remedy this oversight, Pólya taught teachers how to prompt each student with appropriate questions,^[8] depending on the situation, such as:

• What are you asked to find or show?^[9]
• Can you restate the problem in your own words?
• Can you think of a picture or a diagram that might help you understand the problem?
• Is there enough information to enable you to find a solution?
• Do you understand all the words used in stating the problem?
• Do you need to ask a question to get the answer?

The teacher is to select the question with the appropriate level of difficulty for each student to ascertain if each student understands at their own level, moving up or down the list to prompt each student, until each one can respond with something constructive.

Second principle: Devise a plan

Pólya^[10] mentions that there are many reasonable ways to solve problems.^[3] The skill at choosing an appropriate strategy is best learned by solving many problems. You will find choosing a strategy increasingly easy. A partial list of strategies is included:

• Guess and check^[11]
• Make an orderly list^[12]
• Eliminate possibilities^[13]
• Use symmetry^[14]
• Consider special cases^[15]
• Use direct reasoning
• Solve an equation^[16]

Also suggested:

• Look for a pattern^[17]
• Draw a picture^[18]
• Solve a simpler problem^[19]
• Use a model^[20]
• Work backward^[21]
• Use a formula^[22]
• Be creative^[23]
• Use your head/noggin^[24]

Third principle: Carry out the plan

This step is usually easier than devising the plan.^[25] In general, all you need is care and patience, given that you have the necessary skills. Persist with the plan that you have chosen. If it continues not to work discard it and choose another. Don't be misled; this is how mathematics is done, even by professionals.

Fourth principle: Review/extend

Pólya^[26] mentions that much can be gained by taking the time to reflect and look back at what you have done, what worked and what didn't.^[27] Doing this will enable you to predict what strategy to use to solve future problems, if these relate to the original problem.

Heuristics

The book contains a dictionary-style set of heuristics, many of which have to do with generating a more accessible problem. For example:

Heuristic	Informal Description	Formal analogue
Analogy	Can you find a problem analogous to your problem and solve that?	Map
Generalization	Can you find a problem more general than your problem?	Generalization
Induction	Can you solve your problem by deriving a generalization from some examples?	Induction
Variation of the Problem	Can you vary or change your problem to create a new problem (or set of problems) whose solution(s) will help you solve your original problem?	Search
Auxiliary Problem	Can you find a subproblem or side problem whose solution will help you solve your problem?	Subgoal
Here is a problem related to yours and solved before	Can you find a problem related to yours that has already been solved and use that to solve your problem?	Pattern recognition Pattern matching Reduction
Specialization	Can you find a problem more specialized?	Specialization
Decomposing and Recombining	Can you decompose the problem and "recombine its elements in some new manner"?	Divide and conquer
Working backward	Can you start with the goal and work backwards to something you already know?	Backward chaining
Draw a Figure	Can you draw a picture of the problem?	Diagrammatic Reasoning [28]
Auxiliary Elements	Can you add some new element to your problem to get closer to a solution?	Extension[disambiguation needed]

The technique "have I used everything" is perhaps most applicable to formal educational examinations (e.g., n men digging m ditches) problems.
The book has achieved "classic" status because of its considerable influence (see the next section).
Other books on problem solving are often related to more creative and less concrete techniques. See lateral thinking, mind mapping, brainstorming, and creative problem solving.

Influence

• It has been translated into several languages and has sold over a million copies, and has been continuously in print since its first publication.
• Marvin Minsky said in his influential paper Steps Toward Artificial Intelligence that "everyone should know the work of George Pólya on how to solve problems." ^[29]
• Pólya's book has had a large influence on mathematics textbooks as evidenced by the bibliographies for mathematics education.^[30]
• Russian physicist Zhores I. Alfyorov, (Nobel laureate in 2000) praised it, saying he was very pleased with Pólya's famous book.
• Russian inventor Genrich Altshuller developed an elaborate set of methods for problem solving known as TRIZ, which in many aspects reproduces or parallels Pólya's work.

Poor Man’s Visual Studio Cppcheck Integration (By Aleksey Vitebskiy, 9 Oct 2012)

http://www.codeproject.com/Tips/472065/Poor-Man-s-Visual-Studio-Cppcheck-Integration

Introduction

Cppcheck is a good tool to have in your arsenal. Anything that helps me avoid stupid mistakes is very welcome. The problem is that if you use Visual Studio, you either have to use the separate Cppcheck GUI or pay an arm and a leg for something like Visual Lint. If you want a more convenient way to run Cppcheck on your code, but don't want to shell out $200 for the privilege, there's a fairly easy way to do a simple integration.
This article is a re-post from http://avitebskiy.blogspot.com/2012/10/poor-mans-visual-studio-cppcheck.html.

Getting Started

First things first, download the latest version Cppcheck from http://cppcheck.sourceforge.net/ and install it. This will give you both the command line version and the GUI version of Cppcheck.

Create a Visual Studio External Tool

In Visual Studio, open menu Tools→External Tools...

• Click the Add button
• Set the Title, for example Cppcheck
• Set Command to C:\Program Files (x86)\Cppcheck\cppcheck.exe
• Set Arguments to --quiet --verbose --template=vs $(ItemPath)
• Set Initial Directory to $(ItemDir)
• Make sure Use Output window checkbox is enabled
• Click on the Move Up button repeatedly until your entry is at the top of the list, this will make it easier to identify you new command as you can count on it being called Tools.ExternalCommand1
• Click OK.

Voila!  You now have a Cppcheck entry in your Tools menu:
 

Use the Tool

You can now use select the Cppcheck menu entry any time you want to run Cppcheck on a file.  The cool thing about the --template=vs switch is that you can click on a Cppcheck error and Visual Studio will automatically take you to that line of code:

Automate Cppcheck to Run on File Save

Now that we have created a command to run Cppcheck, we can have it run automatically after a file save:

• Go to menu Tools→Macros→Macros IDE, this will bring up a the Macros IDE
• On the left hand side there should be a Project Explorer panel
• In the Project Explorer panel, double click on EnvironmentEvents module
• Insert the following code in the module:

Collapse | Copy Code

Private Sub DocumentEvents_DocumentSaved(ByVal Document As EnvDTE.Document) Handles DocumentEvents.DocumentSaved
    If Document.Language = "C/C++" Then
        DTE.ExecuteCommand("Tools.ExternalCommand1")
        Document.Activate()
    End If
End Sub

• Now save the module, close the Macros IDE, and you're good to go

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Aleksey Vitebskiy Software Developer TerraGo Technologies United States Member Follow on Twitter Google

No Biography provided