Работа с текстом в C++

[No_Comments]

Доброго всем времени суток!!!
Очень нужна помощь с программой.
Задание: распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождения в текст).
Программу писала для текста из 3х слов, в каждом по 3 буквы. Использовала структуры.
Меня 2 месяца не будет, прогу надо сдать в начале сентября!!!
Буду бесконечно благодарна.

#include <vcl.h>
#include <fstream.h>
#include <iostream.h>
#include <conio.h>
#include <string.h>
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
void main()
{const int n=16;
	char str[n];
	ifstream fg("I:\\text.txt"); // "Чтение файла"
	if(!fg)								// Если файла нет, то выходим
		exit(1);
	while(!fg.eof()){				// Чтение файла
		fg>>str;
	}
	cout << "Basic string: " << str << endl;
struct tx {
char wd[3];     //создаем массив
int k;        //счетчик
};
tx p[10];   //массив структур
int i=0;
int t=0;
int z=0;
for (z = 0; z < 10; z++)
p[z].k=0;
for ( z=0; z < 10; z++)
{ for (i = 0; i < n; i++)
	{if (str[i]!='_')
	p[z].wd[i]=str[i];
	//t++;
	}
}
for (z = 0; z < n; z++)
{
	for (i = 0; i < n; i++)
	cout<<p[z].wd[i];
	cout<<endl;
	//cout<<p[z].k;
}

/*z=0;
for (z = 0; z < 30; z++) {
{for (i=0; i<10; i++)
if (p[z].wd[i]==p[t].wd[i]);
else p[z].k++;
}
t++;
}
for (z = 0; z < 30; z++) {

}     */
	getch();
}

[l1pton17]

а в чем, собственно, проблема?)

[Nedward]

Вот программа, при файле содержащем

ccc
aaa
bbb
ccc
bbb
ccc

Дает вывод

Привет!
Читаем файл
Прочли слово "ccc"
Прочли слово "aaa"
Прочли слово "bbb"
Прочли слово "ccc"
Прочли слово "bbb"
Прочли слово "ccc"
Массив, сортированный по алфавиту:
Текст "aaa" встречается 1 раз
Текст "bbb" встречается 2 раз
Текст "ccc" встречается 3 раз
Массив, сортированный по количеству вхождений текста:
Текст "ccc" встречается 3 раз
Текст "bbb" встречается 2 раз
Текст "aaa" встречается 1 раз
Для продолжения нажмите любую клавишу . . .

Есть только 1 проблема: программа читает из файла в массив map, и для сортировки по частоте встречаемости я не придумал ничего лучше, чем создавать второй массив multimap
Производительность (как я думаю) будет ужасной, но оно вполне работает. С удовольствием послушаю, как её можно оптимизировать.

#include <iostream>
#include <locale>
#include <fstream>
#include <map>
#include <string>

using namespace std;

void main()
{
	setlocale(LC_ALL,"Russian");
	cout << "Привет!" << endl;
	ifstream f("d:\\abc\\input.txt"); //Сперва - файл из которого читаем слова
	map<string,unsigned int> words; //Теперь - хранилище для слов (и счетчик):
	string tmp; //временная переменная (в ней храним считанные из файла слова)
	cout << "Читаем файл" << endl;
	while(!f.eof())
	{
		f >> tmp;
		cout << "Прочли слово \"" << tmp << "\"" << endl;

		pair< map<string,unsigned int>::iterator, bool > p;
		p=words.insert(pair<string,unsigned int>(tmp,1)); //попытались вставить слово
		if (p.second) //если p - истина, то
		{
			//Элемент вставился (значит его не было :))
			words[tmp]=1;
		}
		else
		{
			//Элемент не вставился (значит он был, увеличиваем счетчик)
			words[tmp]=words[tmp]+1;
		}
	}
	multimap<unsigned int,string,std::greater<unsigned int> > words2;
	//После этого в массиве words у нас все строки, сортированные по алфавиту, докажем это:
	cout << "Массив, сортированный по алфавиту:" << endl;
	for(map<string,unsigned int>::iterator i=words.begin();i!=words.end();++i)
	{
		cout << "Текст \"" << (*i).first << "\" встречается " << (*i).second << " раз" << endl;
		//Палучился нэмног не русский акцэнт, да.
		//За одним копируем в другой map для сортировки
		//(если хочется быстродействия, то наверное лучше скопировать в какой-нибудь vector и сортировать в конце руками, но...)
		words2.insert(pair<unsigned int,string>((*i).second,(*i).first));
	}

	//Выводим массив, отсортированный по количеству вхождений:
	cout << "Массив, сортированный по количеству вхождений текста:" << endl;
	for(multimap<unsigned int,string,std::greater<unsigned int> >::iterator i=words2.begin();i!=words2.end();++i)
	{
		cout << "Текст \"" << (*i).second << "\" встречается " << (*i).first << " раз" << endl;
	}
}

[Rififi]

No_Comments

Очень нужна помощь с программой.
Задание: распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождения в текст).
Программу писала для текста из 3х слов, в каждом по 3 буквы. Использовала структуры.
Меня 2 месяца не будет, прогу надо сдать в начале сентября!!!

Хе-хе. стратегия, надо признать, весьма недурственная. Пока ты будешь прохлаждаться в отпуске, ботаны тебе решают задачки ((((:

Ну да ладно, ботаны сегодня добрые, вот т нечего делать набросалось...

#include <string>
#include <sstream>
#include <iostream>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

#include <boost/lambda/lambda.hpp>
namespace lm = boost::lambda;

struct WordCounter
{
	std::string word_;
	unsigned counter_;

	WordCounter(std::string s) : word_(s), counter_(0)
	{
	}
};

namespace client {
using namespace boost::multi_index;

typedef multi_index_container<
	WordCounter,
	indexed_by<
		ordered_non_unique<
			BOOST_MULTI_INDEX_MEMBER(WordCounter, unsigned, counter_),
			std::greater<unsigned>
		>,
		hashed_unique<
			BOOST_MULTI_INDEX_MEMBER(WordCounter, std::string, word_)
		>
	> > WordCounterIndex;
}

using client::WordCounterIndex;

int main()
{
	std::string s = "aaa bbb ccc aaa bbb  aaa";

	std::stringstream ss(s);
	std::string word;

	WordCounterIndex index;

	while (ss >> word)
	{
		WordCounterIndex::iterator it = index.insert(word).first;
		index.modify_key(it, ++lm::_1);
	}

	for (WordCounterIndex::const_iterator it = index.begin(); it != index.end(); ++it)
		std::cout << it->counter_ << " : " << it->word_ << std::endl;

	return 0;
}

Пример работы программы: http://liveworkspace.org/code/c274be...7beabce256767a

[Mandrivnyk]

#include <iostream>
#include <fstream>
#include <map>
#include <iterator>

using namespace std;

int main()
{
        map<string, int> results;
        multimap<int, string, greater<int> > sortresults;
        fstream text("text.txt");

        for (istream_iterator<string> It(text); It != istream_iterator<string>(); ++It)
            results[*It]++;
       
        for (map<string, int>::iterator It = results.begin(); It != results.end(); ++It)
            sortresults.insert(make_pair(It->second, It->first));

        for (multimap<int, string>::const_iterator It = sortresults.begin(); It != sortresults.end(); ++It)
                cout << It->second << "\t\t"<< It->first << endl;
}

[Nedward]

Сообщение от Mandrivnyk

#include <iostream>
#include <fstream>
#include <map>
#include <iterator>

using namespace std;

int main()
{
        map<string, int> results;
        multimap<int, string, greater<int> > sortresults;
        fstream text("text.txt");

        for (istream_iterator<string> It(text); It != istream_iterator<string>(); ++It)
            results[*It]++;
       
        for (map<string, int>::iterator It = results.begin(); It != results.end(); ++It)
            sortresults.insert(make_pair(It->second, It->first));

        for (multimap<int, string>::const_iterator It = sortresults.begin(); It != sortresults.end(); ++It)
                cout << It->second << "\t\t"<< It->first << endl;
}

Замечательный код!

Я и не подозревал, что

while(!f.eof())
	{
		f >> tmp;
		cout << "Прочли слово \"" << tmp << "\"" << endl;

		pair< map<string,unsigned int>::iterator, bool > p;
		p=words.insert(pair<string,unsigned int>(tmp,1)); //попытались вставить слово
		if (p.second) //если p - истина, то
		{
			//Элемент вставился (значит его не было :))
			words[tmp]=1;
		}
		else
		{
			//Элемент не вставился (значит он был, увеличиваем счетчик)
			words[tmp]=words[tmp]+1;
		}
	}

Можно упростить до

        for (istream_iterator<string> It(text); It != istream_iterator<string>(); ++It)
            results[*It]++;

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

[Rififi]

Nedward

с использованием современных техник C++ это можно упростить даже до:

typedef std::istream_iterator<std::string> I;

std::for_each(I(text), I(), ++ref(results)[arg1]);

[Nedward]

Не могу утверждать наверняка (не проводил тесты), но мне кажется что нашел более быстрое решение

#include <iostream>
#include <fstream>
#include <map>
#include <iterator>
#include <string>
#include <algorithm>
#include <locale>
#include <vector>

using namespace std;

bool sort_res(pair<string,int> a,pair<string,int> b) {return a.second>b.second;}

int main()
{
	setlocale(LC_ALL,"Russian");

	map < string, int> results;
	vector <pair<string,int> > v;
	fstream text("d:\\abc\\input.txt");

	for (istream_iterator<string> It(text); It != istream_iterator<string> (); ++It)
		results[*It]++;

	for (map<string, int>::iterator It = results.begin(); It != results.end(); ++It)
		v.push_back(make_pair(It->first,It->second));

	sort(v.begin(),v.end(),sort_res);

	for (vector <pair<string,int> >::iterator i=v.begin();i<v.end();++i)
		cout << "\"" << (*i).first << "\" встречается " << (*i).second << " раз" << endl;
}

[Mandrivnyk]

Сообщение от Nedward

Не могу утверждать наверняка (не проводил тесты), но мне кажется что нашел более быстрое решение

Провел тесты -)
Время примерно одинаковое. В диапазоне от 1838 до 1988 и от 1843 до 1994 микросекунд соответственно (для файла размером в 1000 строк).
Так что оба варианта вполне взаимозаменяемы -)

[Nedward]

Сообщение от Mandrivnyk

Провел тесты -)
Время примерно одинаковое. В диапазоне от 1838 до 1988 и от 1843 до 1994 микросекунд соответственно (для файла размером в 1000 строк).
Так что оба варианта вполне взаимозаменяемы -)

Честно говоря сперва не поверил и провел свои тесты
По результатам исследований выяснилось, что:
1) Я не имею представления, как проводить тесты достаточно быстрых алгоритмов (проверял функцией clock(), но до сих пор не знаю, что за значения она возвращает). Как Вы замеряли время в микросекундах?
2) Один из самых больших txt файлов на моем компьютере - роман барона Олшеври - ВАМПИРЫ.
3) Самое узкое место этих программ - вывод результатов
4) У барона большой словарный запас.
5) Новый алгоритм выигрывает, но он выигрывает копейки, результаты 10 измерений (если не учитывать время вывода на экран, конечно):

75,82,75,90,76,75,73,76,74,77

против

73,76,76,73,74,73,76,73,73,73

Итого 74 против 77,3
Это (если не ошибаюсь) 4,5% прирост скорости

Вообще странные результаты, я ожидал прироста скорости раза в 2 минимум. Ведь в первом варианте для каждого элемента ищется свое место, в то время как во втором сортируется уже готовый массив. Приму к сведению - использовать массив map для сортировки можно даже в критичных по скорости выполнения программах - на результат сильно не повлияет.
P.S. только сейчас пришло в голову - нужно было измерять время выполнения только измененного куска кода, а не всего алгоритма. Наверняка большую часть времени занимает чтение данных из файла. Позже, наверное, попробую - интересная тема получилась