How can I reduce the computational time taken by my code ?

Question

0.00/5 (No votes)

See more:

i developed this code that finds the word count(frequency of each word) in the program depending on the character's ASCII code and my program takes 136 mili seconds to compute the whole program.i am trying to reduce this time.how can i do that since i am new in the programming ?

What I have tried:

#include<iostream>
#include<windows.h>
#include<wchar.h>
#include<conio.h>
#include<string>
#include <ctime>

using namespace std;

int main()
{
	SYSTEMTIME time;
	GetLocalTime(&time);
	wprintf(L"START OF TIME : %02d:%02d:%02d\n", time.wHour, time.wMinute, time.wMilliseconds);
	
	int TOTAL = 0;
	char a[2000];
	cout << "enter the string = ";
	cin.getline(a, 2000);
	int Totalwords = 0;
	int no = 0;

	for (int i = 0; a[i] != '\0'; i++)
	{

		if ((int(a[i]) >= 65 && int(a[i]) <= 90) || (int(a[i]) >= 97 && int(a[i]) <= 122))
		{

		}
		else
		{
			Totalwords++;
		}
		no = i;
	}

	TOTAL = Totalwords;
	cout << "number of words = " << TOTAL << endl;
	string *words = new string[TOTAL];


	for (int i = 0, j = 0; j < TOTAL, i <= no;)
	{
		if ((int(a[i]) >= 65 && int(a[i]) <= 90) || (int(a[i]) >= 97 && int(a[i]) <= 122))
		{
			words[j] = words[j] + a[i];
			i++;
		}
		else
		{
			j++;
			i++;
		}
	}

	int count = 0;
	for (int i = 0; i< TOTAL; i++)
	{
		bool flag = true;
		for (int j = i - 1; j >= 0; j--)
		{

			if (words[i] == words[j])
			{
				flag = false;
				break;
			}
		}

		if (flag)
		{
			count = 1;
			for (int k = i + 1; k<TOTAL; k++)
			{
				if (words[i] == words[k])
					count++;
			}
			cout << words[i] << " ___ " << count << '\n';
		}
	}

	SYSTEMTIME time1;
	GetLocalTime(&time1);
	wprintf(L"END EXECUTION TIME : %02d:%02d:%02d\n", time.wHour, time.wMinute, time.wMilliseconds);
	cout << "Time Difference = " << &time-&time1 << endl;
	_getch();

}

Posted 17-Apr-18 5:04am

Member 13784265

Updated 17-Apr-18 10:35am

jeron1

v2

Add a Solution

Comments

jeron1 17-Apr-18 11:15am

How do you know it's 136mS? Your start time is calculated prior to calling cin.

Member 13784265 17-Apr-18 11:17am

at the end of the program i cout the time again to check the difference between start time and end time

jeron1 17-Apr-18 11:20am

So your ability to enter data at cin() is mighty consistent timewise (and exceptionally fast)?

Member 13784265 17-Apr-18 11:24am

i didn't get your question,sorry.

jeron1 17-Apr-18 11:29am

Try getting your start time just before entering the first for loop.

Pascal-78 17-Apr-18 11:52am

The time difference is a pointer difference! It will not give the right time.
Your code displays the start time twice!, and it displays the milliseconds without the seconds.
For time arithmetics, you should convert your SYSTEMTIME to FILETIME then to ULARGE_INTEGER and do arithmetics using the last type.
You should start by getting a good time measurement first

Member 13784265 17-Apr-18 12:07pm

is there anything i could do with my code that will reduce its time that it takes to run the whole program?

Rick York 17-Apr-18 16:22pm

One handy class you use for timing can be found on this page : Using WM_COPYDATA. That is an old article I submitted to the predecessor of this site but it contains a class called CElapsed that is very useful for high resolution timing. It lives in a header file so it is very easy to include and use. You should start the timer after all input is received and you have displayed and time only the computational logic, not any I/O.

3 solutions

Solution 2

Your main problem is "nesting". Your loops are nested and so run to often.

Because ot this line

C++

TOTAL = Totalwords;

would I try to bring the loops into this braces

C++

else
{
    Totalwords++;
    //here may go the rest of your loops
}

Rethink the strategy of this comparison

C++

if (words[i] == words[k])

It will be slow because of the mass of comparison. You made it twice. That twice bad.

Make some test data with some words and use the debugger.

Posted 17-Apr-18 6:13am

KarstenK

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Rick York · Accepted Answer · 2018-04-17T10:36:00

I would code this with loops similar to how a bubble sort is implemented. Here is an example, including the elapsed timer I mentioned in my comment above :

C++

CElapsed timer;
timer.Begin();
int i, j;
int count = 0;
int last = Totalwords - 1;
for( i = 0; i < last; ++i )
{
    for( j = i + 1; j < TotalWords; ++j )
    {
        if( words[i] == words[j] )
            ++count;
    }
}
double elapsed = timer.End();
cout << "elapsed time was " << elapsed << " seconds" << endl;

This is the brute force method of comparison. A better option would be to use a map, as mentioned previously. If you prefer the brute force method you would be better off saving the strings in a vector so you don't have to care about how many you have and it will clean up after itself automatically.

I also noticed you have a repeated code sequence that accepts a line of input and processes it. You should consider making that a function. You can use isalpha() to determine if the character is alphabetic, or _istalpha for the tchar version.

Patrice T · Accepted Answer · 2018-04-17T05:44:00

Quote:
i didn't get your question,sorry.

Timing is meaningless if you include user input in the timing.
Move the beginning of timing after any user input, and avoid output during timing.

Quote:
How can I reduce the computational time taken by my code ?

Your code is simple minded, but it is at expense of running time.
Instead of using the array words which have an access time linear with number of words, use should use a map.
map - C++ Reference[^]
std::map : The C++ dictionary class – Modern C++[^]

Suppose you have a list of 1000 words
In an array, to know if a word exist, you check the 1000 words.
In a map container, the words are sorted alphabetically and the container uses a tree search or dichotomy, this means that you know if a word exist in list with only 10 search.
Because 2^10= 1024 > 1000

Your algorithm is: (say there is 1000 words)

C++

for each input word // 1000 times
  build list of words
for each word in list // 1000 times
  for each previous words // 500000 times
    Check if word already counted // (in previous words)
  if not counted
    for each remaining words // 500000 times in worst case
      count this word // (in remaining words)
    and print word and count

Algorithm with map container:

C++

for each input word // 1000 times
  copy word in temp variable
  check if word exist
  if not exist
    insert new word in map // 1000 times in worst case
  add 1 to count of that word // 1000 times
for each word in map // 1000 times in worst case
  print word and count

How can I reduce the computational time taken by my code ?

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0