Member 13784265 Ответов: 3

Как я могу сократить вычислительное время, затрачиваемое моим кодом ?

я разработал этот код, который находит количество слов(частоту каждого слова) в программе в зависимости от ASCII-кода символа, и моя программа занимает 136 милисекунд, чтобы вычислить всю программу.как я могу это сделать, если я новичок в программировании ?

Что я уже пробовал:

#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();

}

jeron1

Откуда ты знаешь, что это 136мс? Ваше время начала вычисляется до вызова cin.

Member 13784265

в конце программы я снова вычисляю время, чтобы проверить разницу между временем начала и временем окончания

jeron1

Таким образом, ваша способность вводить данные в cin() очень последовательна во времени (и исключительно быстра)?

Member 13784265

извини,я не расслышал твоего вопроса.

jeron1

Попробуйте получить время начала непосредственно перед входом в первый цикл for.

Pascal-78

Разница во времени-это разница в указателе! Это не даст нужного времени.
Ваш код отображает время начала дважды!, и он отображает миллисекунды без секунд.
Для арифметики времени вы должны преобразовать свое SYSTEMTIME в FILETIME, а затем в ULARGE_INTEGER и выполнить арифметику с использованием последнего типа.
Вы должны начать с получения хорошего измерения времени в первую очередь

Member 13784265

могу ли я что-нибудь сделать с моим кодом, чтобы сократить время, необходимое для запуска всей программы?

Rick York

Один удобный класс, который вы используете для синхронизации, можно найти на этой странице : Используя об ошибке wm_copydata Это старая статья, которую я отправил предшественнику этого сайта, но она содержит класс под названием CElapsed, который очень полезен для синхронизации с высоким разрешением . Он живет в заголовочном файле, поэтому его очень легко включить и использовать. Вы должны запустить таймер после того, как все входные данные получены и вы отобразили и время только вычислительной логики, а не каких-либо операций ввода-вывода.

3 Ответов

Рейтинг:
21

Rick York

Я бы закодировал это с помощью циклов, подобных тому, как реализуется пузырьковая сортировка. Вот пример, включая истекший таймер, о котором я упоминал в своем комментарии выше :

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;
Это метод грубой силы сравнения. Лучшим вариантом было бы использовать карту, как упоминалось ранее. Если вы предпочитаете метод грубой силы, вам будет лучше сохранить строки в векторе, чтобы вам не нужно было заботиться о том, сколько у вас есть, и он автоматически очистится после себя.

Я также заметил, что у вас есть повторяющаяся кодовая последовательность, которая принимает строку ввода и обрабатывает ее. Вы должны подумать о том, чтобы сделать это функцией. Вы можете использовать isalpha (), чтобы определить, является ли символ алфавитным, или _istalpha для версии tchar.

Member 13784265

спасибо :)

Рейтинг:
13

Patrice T

Цитата:
извини,я не расслышал твоего вопроса.

Хронометраж не имеет смысла, если вы включаете пользовательский ввод в хронометраж.
Переместите начало синхронизации после любого пользовательского ввода и избегайте вывода во время синхронизации.
Цитата:
Как я могу сократить вычислительное время, затрачиваемое моим кодом ?

Ваш код простодушен, но это происходит за счет времени выполнения.
Вместо того чтобы использовать массив words которые имеют время доступа линейное с количеством слов, use should use a map.
карта - Справочник по C++ [^]
std::map : класс словаря C++ – современный C++[^]

Предположим, у вас есть список из 1000 слов
В массиве, чтобы узнать, существует ли слово, вы проверяете 1000 слов.
В контейнере карты слова сортируются по алфавиту, и контейнер использует древовидный поиск или дихотомию, это означает, что вы знаете, существует ли слово в списке только с 10 поисками.
Потому что 2^10= 1024 > 1000

Ваш алгоритм таков: (скажем, есть 1000 слов)
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

Алгоритм с контейнером карты:
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

CPallini

мой 5.

Patrice T

Спасибо

Рейтинг:
1

KarstenK

Ваша главная проблема-это "гнездование". Ваши циклы вложены и поэтому выполняются часто.

Потому что от этой строки

TOTAL = Totalwords;

буду ли я пытаться привести петли в эти фигурные скобки
else
{
    Totalwords++;
    //here may go the rest of your loops
}
Пересмотреть стратегию этого сравнения
if (words[i] == words[k])
Он будет медленным из - за массы сравнения. Ты сделал это дважды- Это вдвойне плохо.

Сделайте некоторые тестовые данные с некоторыми словами и используйте отладчик.