Hot File

Optimize your Code using Appropriate Algorithm using C and C++

View: 2144    Dowload: 0   Comment: 0   Post by: hanhga  
Author: none   Category: C / C++ / MFC   Fields: Other

9 point/3 review File has been tested

For any code you write, you should always take some time to think through and pick the right algorithm to use for your specific scenario.

Introduction

For any code you write, you should always take some time to think through and pick the right algorithm to use for your specific scenario.

The problem we are going to analyze for this example is to find a maximum value of the function in a two dimensional segment.

We’ll consider only whole numbers

First we’ll write the program without consider performance. Then, we’ll discuss few ways to boost the performance of this program.

Our Scenario: We have interval for x [-100…100] and interval for y [-100…100]. Now in these two intervals we are looking for a maximum of the function (x*x + y*y)/(y*y + b).

This is a function of two variables: x and y. There is one more constant which could be different and user will enter it. This constant b is always greater than 0 and also lesser than 1000.

In our program ,we will not use function pow() that is implemented in math.h library. It would be interesting exercise to figure out which approach would create faster code.

Example code:

#include <iostream>

#define LEFT_MARGINE_FOR_X -100.0
#define RIGHT_MARGINE_FOR_X 100.0
#define LEFT_MARGINE_FOR_Y -100.0
#define RIGHT_MARGINE_FOR_Y 100.0

using namespace std;

int
main(void)
{
//Get the constant value
cout<<"Enter the constant value b>0"<<endl;
cout<<"b->"; double dB; cin>>dB;

if(dB<=0)   return EXIT_FAILURE;
if(dB>1000) return EXIT_FAILURE;

//This is the potential maximum value of the function
//and all other values could be bigger or smaller
double dMaximumValue = (LEFT_MARGINE_FOR_X*LEFT_MARGINE_FOR_X+LEFT_MARGINE_FOR_Y*LEFT_MARGINE_FOR_Y)/ (LEFT_MARGINE_FOR_Y*LEFT_MARGINE_FOR_Y+dB);

double dMaximumX = LEFT_MARGINE_FOR_X;
double dMaximumY = LEFT_MARGINE_FOR_Y;

for(double dX=LEFT_MARGINE_FOR_X; dX<=RIGHT_MARGINE_FOR_X; dX+=1.0)
  for(double dY=LEFT_MARGINE_FOR_Y; dY<=RIGHT_MARGINE_FOR_Y; dY+=1.0)
    if( dMaximumValue<((dX*dX+dY*dY)/(dY*dY+dB)))
    {
      dMaximumValue=((dX*dX+dY*dY)/(dY*dY+dB));
      dMaximumX=dX;
      dMaximumY=dY;
    }

cout<<"Maximum value of the function is="<< dMaximumValue<<endl;
cout<<endl<<endl;
cout<<"Value for x="<<dMaximumX<<endl
    <<"Value for y="<<dMaximumY<<endl;

 return EXIT_SUCCESS;
}

Now, if we analyze the code more carefully, we notice that the part for dX*dX is calculated more times than it should, in this case it is calculated 200 times and this is a was of CPU time. What we could do?

One of the trick is to create one variable dX_Squer = dX*dX, and calculate after first for repetition, then we could use that in all calculations afterwards. You just need to add one more brackets.

There are few more optimizations you can do in the above code, just try to spot them.

The next point we could consider is how general our algorithm is, versus how optimal is it from speed point of view.

In that case we could apply few algorithms depending on the size of input set. What do we mean by that?

For example, in one our earlier c++ articles, we discussed about binary numbersthat have only two ones in many zeros.

We could use MVA algorithm that could outperform the original algorithm from speed point of view on smaller numbers, the ones that are fit for unsigned long long int, but if you use my algorithm combined with vectors it could be used in some problems where you try to pick two objects that are in set.

So, in order to create the best possible solution you could merge two algorithms and apply one according to the size of the problem. So, if the number used is smaller than unsigned long long int, you could use first algorithm and if number will not fit already mentioned type of data you could use vectors or some other data structures.

Similar to this would be addition of numbers, where it is simple to consider case of long long int, but in case we need to add to big numbers that are in size way bigger than unsigned long long int you could use vectors to store them and apply operation of addition with your algorithm. If you prefer classes you could use them to, but if you don’t need OOP approach you could just use double linked list or arrays or some other more appropriate data structure.

Optimize your Code using Appropriate Algorithm using C and C++

Optimize your Code using Appropriate Algorithm using C and C++ Posted on 18-12-2015  For any code you write, you should always take some time to think through and pick the right algorithm to use for your specific scenario. 3/10 2144

Comment:

To comment you must be logged in members.

Files with category

  • How to Swap Two Numbers using Call by Reference in C

    View: 370    Download: 0   Comment: 0   Author: none  

    How to Swap Two Numbers using Call by Reference in C

    Category: C / C++ / MFC
    Fields: Other

    0/0 review
    How to swap two numbers using call by reference in C , C++. In the interviews interviewer generally asked the difference between call by reference and call by value

  • How to Print Fibonacci Series using Recursion in C, C++

    View: 376    Download: 0   Comment: 0   Author: none  

    How to Print Fibonacci Series using Recursion in C, C++

    Category: C / C++ / MFC
    Fields: Other

    4.5/1 review
    Write a program to print Fibonacci Series using recursion. Fibonacci series is a very important program in terms of interviews. To make this program little tough interviewer ask to write a fibonacci series code using recursion.

  • How to Implicitly Typed Arrays In C#

    View: 410    Download: 0   Comment: 0   Author: none  

    How to Implicitly Typed Arrays In C#

    Category: C / C++ / MFC
    Fields: Other

    0/1 review
    When we initialize these type of arrays with any data type, the compiler convert these arrays into that data type at compile time.

  • How to C# Static vs Instance Methods As Event Handlers

    View: 286    Download: 0   Comment: 0   Author: none  

    How to C# Static vs Instance Methods As Event Handlers

    Category: C / C++ / MFC
    Fields: Other

    0/0 review
    Both static and instance methods can be used as event handlers in C#

  • Build Pass By Reference To Method In C#

    View: 439    Download: 0   Comment: 0   Author: none  

    Build Pass By Reference To Method In C#

    Category: C / C++ / MFC
    Fields: Other

    0/3 review
    Like value types such as int, double, char etc. We can also pass a reference variable to the method in C# as its parameter which allows us to pass an object to the method and it is called pass by reference to method in C#.

  • How to C# Continue Statement

    View: 273    Download: 0   Comment: 0   Author: none  

    How to C# Continue Statement

    Category: C / C++ / MFC
    Fields: Other

    0/2 review
    continue statement skips or exits the current execution of a loop by given condition and keep execution continue for its next iteration unlike break statement it does not exit or terminate from loops, it terminates only its current execution

  • How to Single Dimensional Arrays In C#

    View: 212    Download: 0   Comment: 0   Author: none  

    How to Single Dimensional Arrays In C#

    Category: C / C++ / MFC
    Fields: Other

    0/1 review
    Single Dimensional Arrays in C# store each individual element at their single dimension, position or a specific location, that location is called an array index. Each index describes the position of each element within an array. Each element in an...

  • Build C# Multilevel Inheritance

    View: 236    Download: 0   Comment: 0   Author: none  

    Build C# Multilevel Inheritance

    Category: C / C++ / MFC
    Fields: Other

    2.5/2 review
    C# supports multilevel inheritance, suppose we have four classes A, B, C and D. Class A can inherit to B, B to C and C can inherit to D and so on now class D has all public members of class A, B and C include its own.

 
Newsletter Email

File suggestion for you

File top downloads

logo codetitle
Codetitle.com - library source code to share, download the file to the community
Copyright © 2015. All rights reserved. codetitle.com Develope by Vinagon .Ltd