Как можно переделать прогу?
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Как можно переделать прогу? - 2010-06-02 13:56:17.133333
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
вот исходник
#include <iostream> //Реализует ввод и вывод
#include <fstream>
#include <vector> //Определяется динамический массив
#include <algorithm>
#include <windows.h> //GetTickCount
#include "tree.h"
#include "word.h"
using namespace std; //Использование имен из пространства std по-умолчанию
bool parse(string& str)
{
if (str.length() < 4) return false;
const char symbols[] = {44, 46, 33, 63, 34, 60, 62, 40, 41, 59, 39, 58, 61, 92, 47};
for (int j=0, len = str.length(); j<len; j++) //Функция len используется для проверки пустой строковой переменной
{
for (int i=0; i<sizeof(symbols); i++)
{
if (str[j] == symbols[i])
{
i = 0;
str.erase(j,1);
if ( j > 0 ) j--;
len--;
}
}
}
if (str.length() < 4) return false;
}
int compare(const void *obj1, const void *obj2)
{
CompareByCount cmp; // используется на втором этапе программы для сортировки вектора с сортировкой по уменьшению частоты появления этого слова
return cmp.more((Word*)obj1, (Word*)obj2);
}
int main(int argc, char *argv[])
{
DWORD startTime = GetTickCount();
BinarySearchTree<Word*> tree;
CompareByStr cmp; //используется на первом этапе программы при обработки файла и для подсчета слов, сортировка выполняется по словам
tree.setComparer(&cmp);
vector<Word*> v;
ifstream file("1.txt"); //Открытие файла с текстом
if (!file.is_open())
{
cout << "It is impossible to open a file 1.txt" << endl;
system("pause");
return 1;
}
string str; //представление строк
Word w, *pWord;
do {
file >> str;
if (!parse(str)) continue;
w.set(str);
// Если нашли слово в дереве, то увеличиваем счетчик на единицу
if((pWord = tree.search(&w)) != NULL) pWord->inc();
else
{
// иначе добавляем новое слово в дерево
pWord = new Word(str);
tree.insert(pWord);
// добаляем слово в вектор
v.push_back(pWord);
}
} while (!file.eof());
file.close();
// Сортируем вектор по полю count
sort(v.begin(), v.end(), compare); //Начало и возврат итератора и сравнение
ofstream out("2.txt"); //Записываем в файл вывод слов
if (!out.is_open())
{
cout << "It is impossible to open a file 2.txt" << endl;
system("pause");
return 1;
}
for (vector<Word*>::iterator i = v.begin(), end = v.end(); i != end; i++)
{
out << **i;
}
out.close();
cout <<"The program has successfully deduced words in a file 2.txt...\nTime: " << (GetTickCount() - startTime) /1000.0 <<" second(s)\n" << endl;
system("pause");
return 0;
}
Помогите плиз, надо чтобы сортировка происходила намного быстрее чем сейчас! компилировать через release… Заранее спасиб!
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 14:18:08.546666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Хороший пример того, как не нужно писать комментарии к коду.
З.Ы. что за сортировка? Какая изначальная задача?
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 16:13:44.726666
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
Нужно осуществить сортировку с наименьшим временем текста романа ,,война и мир" он открывает файл 1.тхт, записывать отсортированные слова(больше 4 букв) в файл 2.тхт….
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 16:20:21.100000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Общее:
http://ru.wikipedia.org/wiki/Алгоритм_сортировки
http://algolist.manual.ru/sort/index.php
А вообще врядли получится сильно быстрее, чем std::sort. Разве что как-то соптимизируешь компаратор.
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 17:22:40.643333
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
хммм… ну мне как бы просто говорили, что можно через многопоточность эту прогу переделать, но вот я хоть и читал и тд, все равно не могу сделать = (((
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 17:41:15.490000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Может это поможет: http://forum.codeby.net/lofiversion/index.php/t12450.html
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 17:43:17.320000
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
блин = ((( это конечно хорошо, но блин, все равно не вкатывает мне в мозг многопоточность = (((((
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 18:18:30.376666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ну не делай ;)
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 18:20:58.450000
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
= (((( да с удовольствием = (((( но нужно эту прогу последнюю сдать = ((( она полностью работает! но задача, написать программу которая сортирует не больше 1,5 сек… а у меня сортирует за 2 сек
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 19:08:45.033333
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
В написанном не разбирался, просто гугл…
P.S. возми комп пошустрее ;)
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 19:10:53.576666
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
quote:
ORIGINAL: _SaZ_
В написанном не разбирался, просто гугл…
P.S. возми комп пошустрее ;)
=)))) если б все так просто было б =)))) там препод принимает все проги на своем ноуте!!!!
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 19:14:19.713333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Sidjey, а расскажи-ка мне, что у тебя там за BinarySearchTree, а? Это ведь двоичное дерево поиска, не так ли? Ну а если я прав, то нахрена тебе тогда массив и сортировка этого массива?
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 22:24:43.720000
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
quote:
ORIGINAL: rgo
Sidjey, а расскажи-ка мне, что у тебя там за BinarySearchTree, а? Это ведь двоичное дерево поиска, не так ли? Ну а если я прав, то нахрена тебе тогда массив и сортировка этого массива?
да это так, ну записываем в массив или в дерево слова, а потом вроде как сортируем…
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-02 22:43:25.373333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Ты знаешь как работает двоичное дерево поиска? Оно, по-сути, отсортировывает всё, что ты туда запихиваешь. И если тебе надо отсортировать кучу слов и ты эти слова запихал в дерево, тебе лишь надо извлечь эти слова из дерева. Надо просто обойти все узлы дерева, в нужном порядке (в прямом или в обратном), и вывести содержимое этих узлов. Почитай про сортировку вставкой в двоичное дерево. Ты её уже сделал, тебе остался последний шаг: вывод результата.
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-03 14:34:04.903333
|
|
|
m_Sam
Сообщений: 15
Оценки: 0
Присоединился: 2010-05-13 12:11:24.050000
|
quote:
ORIGINAL: Sidjey
Нужно осуществить сортировку с наименьшим временем текста романа ,,война и мир" он открывает файл 1.тхт, записывать отсортированные слова(больше 4 букв) в файл 2.тхт….
Возможно указывая в задании роман ,,война и мир" имелось ввиду, что файл очень большой (неизвестно на самом деле когда появилась такая задача=) ) и его надо сортировать не сильно расходуя оперативную память ?
А если делать так как предлагаешь ты, то почему просто не создать vector<string> , наполнить его словами удовлетворяющими критерий и применить метод ::sort( cmpFnc ) , тобиш QuickSort ?
Единственное что тут не так, так это то что сам вектор будет огромен )
Если же на память поплевать, то можно сделать распределяющую сортировку(RadixSort), она должна быть в этом варианте даже быстрей быстрой (QuickSort )
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-03 14:51:43.256666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
list вместо вектора ;)
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-04 06:10:37.010000
|
|
|
Sidjey
Сообщений: 25
Оценки: 0
Присоединился: 2010-05-20 19:05:36.610000
|
Огромное всем спасибо!!! =) у меня все таки получилось сделать прогу, но делал я теперь через хэш таблицы =)
|
|
|
|
|
RE: Как можно переделать прогу? - 2010-06-04 12:15:35.376666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ну выкладывай, хвастайся.
|
|
|
|
|
|
