Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

19.06.2013, 22:24. Просмотров 1396. Ответов 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() использовать другую функцию, которая быстре считывает данные из файла??
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2013, 22:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подскажите пожалуйста как ускорить работу программы! (C++):

Динамический массив, много циклов и простые числа. Как ускорить работу программы ? - C++
Всем привет. Задание следующее: Кто нибудь вводит с клавиатуры число n и k, должен создастся массив из чисел от 1 до n, далее каждый...

Ускорить работу программы - C++
Лексикографический порядок чисел (Время: 1 сек. Память: 16 Мб Сложность: 31%) Натуральные числа от 1 до N упорядочены...

Задача про рюкзак - ускорить работу программы - C++
Вообщем есть алгоритм, который работает правильно за O(N*W), поэтому при больших значениях будет очень долго считать, нужно изменить так,...

Как ускорить работу? - C++
Прога ещё не доработана, сейчас интересует именно графический режим, когда нажимается клавиша 1-4 один из 4-х квадратов должен...

Как ускорить работу с файлами? - C++
Предполагается, что программа будет работать с файлами размера 300-500МБ. Эти обычные функции работают слишком медленно. Может быть стоит...

Как ускорить работу (поиск вхождений подстроки)? - C++
//подсчет kf int NumberKF(string &amp;P, vector&lt;string&gt; &amp; F, const int f){ int kf =0; for(size_t i = 0; i &lt; f; ++i){ //обход по...

14
VTsaregorodtsev
377 / 360 / 53
Регистрация: 19.02.2010
Сообщений: 1,520
20.06.2013, 00:12 #2
Нет, нужно использовать алгоритм с вычислительными затратами не O(N^2)
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
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() использовать другую функцию, которая быстре считывает данные из файла??
Это ничего не даст. Проблема в вашем алгоритме.
0
DiffEreD
1432 / 769 / 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;
}
0
Thinker
Эксперт С++
4229 / 2203 / 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;
и все!!!
0
UnsKneD
алкокодер
155 / 151 / 12
Регистрация: 27.12.2012
Сообщений: 550
20.06.2013, 10:41 #6
Thinker, по моему так количество строк посчитается.
0
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 иначе добавляем в конец вектора ище одно слово и сразу считаем сумму. По завершению конца файла сразу будет известно кол-во слов.
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
20.06.2013, 18:17 #8
Цитата Сообщение от Nikko12 Посмотреть сообщение
Olivеr, Ваш код при компиляции выдает у меня 11 ошибок)))))
Найдите компилятор с поддержкой С++11. Например GCC
0
MrGluck
Модератор
Эксперт CЭксперт С++
7510 / 4642 / 700
Регистрация: 29.11.2010
Сообщений: 12,678
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, мапу то зачем, количество считать же не требуется.
1
Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:19  [ТС] #10
Thinker, Так мне нужно подсчитать кол-во различных слов
0
MrGluck
Модератор
Эксперт CЭксперт С++
7510 / 4642 / 700
Регистрация: 29.11.2010
Сообщений: 12,678
20.06.2013, 18:20 #11
Кстати, для С++98 можно просто unordered_set заменить на set. Время конечно увеличиться, т.к. добавиться ненужная сортировка, но ненамного.
0
Nikko12
1 / 1 / 0
Регистрация: 07.06.2013
Сообщений: 162
20.06.2013, 18:20  [ТС] #12
Olivеr, Копилятор сервера не поддерживает С++11, так что не судьба((((
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
20.06.2013, 18:23 #13
Цитата Сообщение от MrGluck Посмотреть сообщение
Olivеr, мапу то зачем, количество считать же не требуется.
А я, кажись, посчитал количество не повторяющихся слов...
Никогда не умел читать задания)

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

Добавлено через 43 секунды
Olivеr, Все равно спасибо, что просто ответили
0
MrGluck
Модератор
Эксперт CЭксперт С++
7510 / 4642 / 700
Регистрация: 29.11.2010
Сообщений: 12,678
20.06.2013, 18:28 #15
Olivеr, нет, определил все верно, но нам ведь фактически нужны лишь те элементы мапа, что имеют второе число, равное единице, т.е. встречающиеся не более 1 раза. А с уникальностью вполне и set может справиться. Вот если бы требовалось любое количество, отличное от 1, то тогда map.
0
20.06.2013, 18:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.06.2013, 18:28
Привет! Вот еще темы с ответами:

Можно ли как нибудь ускорить работу цикла for? - C++
Подскажите пожалуйста - можно ли как нибудь ускорить работу цикла for? Заранее сильно благодарен!

Ускорить выполнение программы как минимум в два раза - C++
Привет, товарищи! Публикую данную тему в целях спортивного интереса. Сразу оговорюсь, те кто &quot;в теме&quot; - отвечайте просто &quot;я знаю&quot; (я...

Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода) - C++
есть код, нужно cout и cin перевести на printf и scanf дополнительных библиотек не подключать! проблема в том что при вводе 14 работает...

Подскажите как делать,пожалуйста - C++
Вот задачка,сколько сижу думаю над ней,не понимаю=( 1)Соседями элементами Аij в матрице назовем элементы Аkl(внизу) c...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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