Форум программистов, компьютерный форум CyberForum.ru

Подскажите пожалуйста как ускорить работу программы! - C++

Восстановить пароль Регистрация
 
Nikko12
 Аватар для Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
19.06.2013, 22:24     Подскажите пожалуйста как ускорить работу программы! #1
Есть задача :"Во входном файле (вы можете читать данные из файла input.txt) записан текст. Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки.

Определите, сколько различных слов содержится в этом тексте."
Моя программа не укладывается чуть-чуть по времени отведенное на ее выполнение, т.е. работает дольше 1 сек. Подскажите как ее можно ускорить.
P.S. Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
 int main()
 { 
    freopen("input.txt","r",stdin);
    int n=1,i,j,sum=0;
    vector <string> v1;
    char c,str[100];
    while(scanf("%s",str)!=EOF)//ввожу файлы пока не конец фала
    {
        v1.push_back(str);
    }
    for(i=0;i<v1.size();i++)
    {
        if(v1[i].length()!=0)//если длина фала больше нуль, значит найдено новое слово
        {
            
            sum++;
            for(j=v1.size()-1;j>=n;j--)// при нажодении такого же слова, стираю его
            {
                if(v1[j]==v1[i])
                {
                    v1[j].clear();
                }
                
            }
        }
        n++;
    }
    cout<<sum;
    return 0;
}
P.S. Заранее спасибо добрым людям за помощь.
P.S.S. Может нужно вместо функции scanf() использовать другую функцию, которая быстре считывает данные из файла??
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VTsaregorodtsev
293 / 273 / 35
Регистрация: 19.02.2010
Сообщений: 1,205
20.06.2013, 00:12     Подскажите пожалуйста как ускорить работу программы! #2
Нет, нужно использовать алгоритм с вычислительными затратами не O(N^2)
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 00:33     Подскажите пожалуйста как ускорить работу программы! #3
Используйте хеш-таблицу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <fstream>
#include <unordered_map>
 
using namespace std;
 
int main()
{
    ifstream file("input.txt");
    if (!file.good()) return -1;
    string word;
    unordered_map<string, int> words;
    while (file >> word)
        ++words[word];
    int count = 0;
    for (const auto &p: words)
        if (p.second == 1) ++count;
    cout << count;
    return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от Nikko12 Посмотреть сообщение
P.S.S. Может нужно вместо функции scanf() использовать другую функцию, которая быстре считывает данные из файла??
Это ничего не даст. Проблема в вашем алгоритме.
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.06.2013, 01:03     Подскажите пожалуйста как ускорить работу программы! #4
Ну, или сетом попробовать:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
#include <fstream>
#include <set>
#include <iterator>
#include <windows.h>
 
int main(int argc, char** argv)
{
   SetConsoleCP (1251); SetConsoleOutputCP (1251);
   
   std::ifstream ifs("D:/file.txt");
   if (ifs.is_open())
   {
      std::set<std::string> words((std::istream_iterator<std::string>(ifs)), std::istream_iterator<std::string>());
      std::cout<<"Различных слов: "<<words.size()<<'\n';
   }
   else
      std::cerr<<"Не удалось открыть файл.";
   
   std::cout<<'\n';
   return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.06.2013, 08:05     Подскажите пожалуйста как ускорить работу программы! #5
C++
1
2
3
4
5
6
FILE *f;
char s[1024];
int count = 0;
...// открываем файл
while(fscanf(f, "%s", s) == 1)
   ++count;
и все!!!
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
20.06.2013, 10:41     Подскажите пожалуйста как ускорить работу программы! #6
Thinker, по моему так количество строк посчитается.
Nikko12
 Аватар для Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:16  [ТС]     Подскажите пожалуйста как ускорить работу программы! #7
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Нет, нужно использовать алгоритм с вычислительными затратами не O(N^2)
Что значит алгоритм с вычислительными затратами не O(N^2), мне это не о чем не говорит.

Добавлено через 2 минуты
Olivеr, Ваш код при компиляции выдает у меня 11 ошибок))))) Если мой алгорит не эффективен, предложите другой.
P.S. Я думаю может стоит сравнивать строки при вводе, если есть строка то break иначе добавляем в конец вектора ище одно слово и сразу считаем сумму. По завершению конца файла сразу будет известно кол-во слов.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 18:17     Подскажите пожалуйста как ускорить работу программы! #8
Цитата Сообщение от Nikko12 Посмотреть сообщение
Olivеr, Ваш код при компиляции выдает у меня 11 ошибок)))))
Найдите компилятор с поддержкой С++11. Например GCC
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,399
20.06.2013, 18:18     Подскажите пожалуйста как ускорить работу программы! #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
#include <fstream>
#include <unordered_set>
#include <iterator>
 
int main()
{
    std::ifstream ifs("input.txt");
    if (!ifs) return 1;
    typedef std::istream_iterator<std::string> input_str;
    std::unordered_set<std::string> words((input_str(ifs)), input_str());
    std::cout <<words.size() << '\n';
}
Добавлено через 25 секунд
Olivеr, мапу то зачем, количество считать же не требуется.
Nikko12
 Аватар для Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:19  [ТС]     Подскажите пожалуйста как ускорить работу программы! #10
Thinker, Так мне нужно подсчитать кол-во различных слов
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,399
20.06.2013, 18:20     Подскажите пожалуйста как ускорить работу программы! #11
Кстати, для С++98 можно просто unordered_set заменить на set. Время конечно увеличиться, т.к. добавиться ненужная сортировка, но ненамного.
Nikko12
 Аватар для Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:20  [ТС]     Подскажите пожалуйста как ускорить работу программы! #12
Olivеr, Копилятор сервера не поддерживает С++11, так что не судьба((((
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
20.06.2013, 18:23     Подскажите пожалуйста как ускорить работу программы! #13
Цитата Сообщение от MrGluck Посмотреть сообщение
Olivеr, мапу то зачем, количество считать же не требуется.
А я, кажись, посчитал количество не повторяющихся слов...
Никогда не умел читать задания)

Добавлено через 48 секунд
Цитата Сообщение от Nikko12 Посмотреть сообщение
Olivеr, Копилятор сервера не поддерживает С++11, так что не судьба((((
Мой код и так не то делает))
Посмотрите 9-е сообщение
Nikko12
 Аватар для Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:26  [ТС]     Подскажите пожалуйста как ускорить работу программы! #14
MrGluck, Спасибо за помощь.

Добавлено через 43 секунды
Olivеr, Все равно спасибо, что просто ответили
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2013, 18:28     Подскажите пожалуйста как ускорить работу программы!
Еще ссылки по теме:

C++ Как прекратить работу программы?
Задача про рюкзак - ускорить работу программы C++
C++ Ускорить выполнение программы как минимум в два раза

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,399
20.06.2013, 18:28     Подскажите пожалуйста как ускорить работу программы! #15
Olivеr, нет, определил все верно, но нам ведь фактически нужны лишь те элементы мапа, что имеют второе число, равное единице, т.е. встречающиеся не более 1 раза. А с уникальностью вполне и set может справиться. Вот если бы требовалось любое количество, отличное от 1, то тогда map.
Yandex
Объявления
20.06.2013, 18:28     Подскажите пожалуйста как ускорить работу программы!
Ответ Создать тему
Опции темы

Текущее время: 01:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru