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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
#1

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

19.06.2013, 22:24. Просмотров 1135. Ответов 14
Метки нет (Все метки)

Есть задача :"Во входном файле (вы можете читать данные из файла 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() использовать другую функцию, которая быстре считывает данные из файла??
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2013, 22:24     Подскажите пожалуйста как ускорить работу программы!
Посмотрите здесь:
C++ Динамический массив, много циклов и простые числа. Как ускорить работу программы ?
C++ Ускорить работу программы
Задача про рюкзак - ускорить работу программы C++
Как ускорить работу? C++
Как ускорить работу с файлами? C++
C++ Можно ли как нибудь ускорить работу цикла for?
C++ Как ускорить работу (поиск вхождений подстроки)?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VTsaregorodtsev
338 / 318 / 45
Регистрация: 19.02.2010
Сообщений: 1,355
20.06.2013, 00:12     Подскажите пожалуйста как ускорить работу программы! #2
Нет, нужно использовать алгоритм с вычислительными затратами не O(N^2)
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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
1429 / 766 / 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++
4225 / 2199 / 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
алкокодер
154 / 150 / 11
Регистрация: 27.12.2012
Сообщений: 548
20.06.2013, 10:41     Подскажите пожалуйста как ускорить работу программы! #6
Thinker, по моему так количество строк посчитается.
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
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
20.06.2013, 18:17     Подскажите пожалуйста как ускорить работу программы! #8
Цитата Сообщение от Nikko12 Посмотреть сообщение
Olivеr, Ваш код при компиляции выдает у меня 11 ошибок)))))
Найдите компилятор с поддержкой С++11. Например GCC
MrGluck
Модератор
Эксперт CЭксперт С++
7192 / 4358 / 634
Регистрация: 29.11.2010
Сообщений: 11,867
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
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:19  [ТС]     Подскажите пожалуйста как ускорить работу программы! #10
Thinker, Так мне нужно подсчитать кол-во различных слов
MrGluck
Модератор
Эксперт CЭксперт С++
7192 / 4358 / 634
Регистрация: 29.11.2010
Сообщений: 11,867
20.06.2013, 18:20     Подскажите пожалуйста как ускорить работу программы! #11
Кстати, для С++98 можно просто unordered_set заменить на set. Время конечно увеличиться, т.к. добавиться ненужная сортировка, но ненамного.
Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:20  [ТС]     Подскажите пожалуйста как ускорить работу программы! #12
Olivеr, Копилятор сервера не поддерживает С++11, так что не судьба((((
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
20.06.2013, 18:23     Подскажите пожалуйста как ускорить работу программы! #13
Цитата Сообщение от MrGluck Посмотреть сообщение
Olivеr, мапу то зачем, количество считать же не требуется.
А я, кажись, посчитал количество не повторяющихся слов...
Никогда не умел читать задания)

Добавлено через 48 секунд
Цитата Сообщение от Nikko12 Посмотреть сообщение
Olivеr, Копилятор сервера не поддерживает С++11, так что не судьба((((
Мой код и так не то делает))
Посмотрите 9-е сообщение
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++ Пожалуйста подскажите как правильно!
Подскажите как делать,пожалуйста C++
C++ Как прекратить работу программы?

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru