Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
12 / 12 / 9
Регистрация: 12.04.2012
Сообщений: 259

Ускорить алгоритм

29.06.2014, 00:59. Показов 2494. Ответов 29
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть код который сохраняет строку из StringList в 2-ой StringList, если этой строки нет в 3-ий StringList ...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned __stdcall OST( void* Param )
{
std::auto_ptr<TStringList> SaveOst(new TStringList);
AnsiString ls=lst2->Text;
AnsiString a1="";
for (int i = 0; i < lst->Count; i++) {
count++;
 a1=lst->Strings[i];
   if(ls.Pos(a1)==0) SaveOst->Add(lst->Strings[i]);
 
}
 
SaveOst->SaveToFile("Ostatok.txt");
_endthreadex(0);
 return 0;
}
Работает не достаточно быстро, как можно эффективно изменить алгоритм для ускорения программы...
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.06.2014, 00:59
Ответы с готовыми решениями:

Ускорить алгоритм обработки текста
Здравствуйте. Есть программа для обработки ссылок на сайты - нахождение и сохранение доменов. Её работа заключается в следующем: есть...

Ускорить объединение двух стринггридов (алгоритм)
Привет всем. постараюсь объяснить суть вопроса. на сервере есть исполняемая программа типа база (список , координаты, и другие метки)...

Ускорить алгоритм удаления одного списка из другого
Здравствуйте. Есть два списка : один на 181093 строк другой на 80000. Нужно удалить один список из другого. Моя реализация: ...

29
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 06:54
Вот тебе наводка, надеюсь разберешься что и куда вставить, помогать не буду
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<String> v1;
std::vector<String> v2;
std::vector<String> v3;
 
// сортировка векторов
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
 
// находим разницу значений векторов и вставляем в 3-й вектор
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::inserter( v3, v3.begin()) );
 
// потом проходимся по 3-му вектору и записываем значения в нужный StringList
for ( UINT i = 0; i < v3.size(); i++ )
{
       SaveOst->Add( *it );
}
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 12:59
kzru_hunter,
1. std::set<> лучше использовать, тогда сортировать не надо.
2. Для вектора не std::inserter std::back_inserter()
3. В изначальной задачи проверка на частичное совпадение, а не полное.
4. UINT- > size_t
1
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 16:31
Avazart внутри std::set все равно происходят сортировки, точнее при добавлении элемента происходит поиска места, куда вставить элемент. по производительности будет одинаково. при использовании std::set нужно ещё итераторы объявлять.
конечно, чтобы функция OST моментально отрабатывала, нужно автору хранить где-то std::set, чтобы лишний раз не сортировать при вызове функции, ему решать.
правильнее конечно использовать std::back_inserter(), но и std::inserter подойдет, т.к. вектор v3 пустой.
Цитата Сообщение от Avazart Посмотреть сообщение
3. В изначальной задачи проверка на частичное совпадение, а не полное.
судя по коду, происходит полная проверка, поэтому и написал соответствующий код.
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 16:44
Цитата Сообщение от kzru_hunter Посмотреть сообщение
внутри std::set все равно происходят сортировки,
И
Цитата Сообщение от kzru_hunter Посмотреть сообщение
точнее при добавлении элемента происходит поиска места, куда вставить элемент.
Разные вещи.


Добавлено через 48 секунд
Цитата Сообщение от kzru_hunter Посмотреть сообщение
но и std::inserter подойдет
Не подойдет, ибо будет значительный проигрыш во времени.


Цитата Сообщение от kzru_hunter Посмотреть сообщение
судя по коду, происходит полная проверка, поэтому и написал соответствующий код.
C++
1
ls.Pos(a1)==0
Это частичное сравнение.
0
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 18:30
Цитата Сообщение от Avazart Посмотреть сообщение
Это частичное сравнение.
Полное, посмотри заново код и хватит спорить.
Цитата Сообщение от Avazart Посмотреть сообщение
Не подойдет, ибо будет значительный проигрыш во времени.
не будет, проверь на пустом векторе
Цитата Сообщение от Avazart Посмотреть сообщение
Разные вещи.
создать вектор, заполнить его элементами и отсортировать будет тоже самое, что и создать std::set и заполнить его значениями.
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 18:34
Цитата Сообщение от kzru_hunter Посмотреть сообщение
не будет, проверь на пустом векторе
Вставка в начало вектора всегда дороже чем вставка в конец, ибо что бы вставить в начало нужно сместить элементы (т.е скопировать).Тут нечего проверять.
0
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 18:40
Цитата Сообщение от Avazart Посмотреть сообщение
Вставка в начала вектора всегда дороже, вставки в конец, ибо что бы вставить в начало нужно сместить элементы (т.е скопировать)
ну так вектор то пустой, без разницы что использовать, и без тебя всё что ты пишешь знаю
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 18:40
Цитата Сообщение от kzru_hunter Посмотреть сообщение
Полное, посмотри заново код и хватит спорить.
Вот сам и посмотри, между
C++
1
if(ls.Pos(a1)==0) SaveOst->Add(lst->Strings[i]);
C++
1
if(ls!=a1) SaveOst->Add(lst->Strings[i]);
разница очевидна.
0
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 18:41
А вот это видел?
C++
1
AnsiString ls=lst2->Text;
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 18:42
Цитата Сообщение от kzru_hunter Посмотреть сообщение
ну так вектор то пустой, без разницы что использовать, и без тебя всё что ты пишешь знаю
ты заполняешь вектор по одному элементу и с каждым элементов затраты будут расти пропорционально количеству.
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 18:56
Пустота вектора, никак не влияет на вставку в начало вектора.

inserter вызывает insert() вектора а эта операция затратная в отличии от push_back()

http://www.cplusplus.com/refer... _iterator/
0
45 / 48 / 5
Регистрация: 24.06.2013
Сообщений: 677
29.06.2014, 19:05
Цитата Сообщение от leva Посмотреть сообщение
как можно эффективно изменить алгоритм для ускорения программы...
не понятно что представляет из себя метод "SaveToFile", то по названию чую, что что-то здесь не то)
Если эта функция производит запись на винт, то советую сохранять в буфер, а в файл писать раз из 10-100...но если этот метод уже предусмотрел тормознутость чтения-записи жёсткого диска, то порядок.
0
 Аватар для kzru_hunter
1124 / 795 / 101
Регистрация: 01.02.2011
Сообщений: 1,887
Записей в блоге: 1
29.06.2014, 19:32
Цитата Сообщение от Avazart Посмотреть сообщение
Пустота вектора, никак не влияет на вставку в начало вектора.
inserter вызывает insert() вектора а эта операция затратная в отличии от push_back()
Возьми и проверь - разница будет вставлена в начало вектора, т.е. тоже самое, что и в конец, т.к. вектор пустой!
0
29.06.2014, 22:04
 Комментарий модератора 
Avazart, kzru_hunter, прекращаем безобразия.
0
 Аватар для BRcr
4043 / 2333 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
29.06.2014, 23:30
Что вы как дети малые в самом деле! Ты начал, нет ты начал...

Полагаю, прения по inserter и back_inserter можно закрыть:
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
    using namespace std;
 
    size_t size( 1000000 );
    vector < int > v1( size ), v2( size ), v3( size ), v4( size );
    mcrs::t_time_counter tc;
    String inserter_time, backinserter_time;
 
    srand( time( 0 ) );
 
    for ( size_t i( 0 ), i_limit( size ); i < i_limit; ++i )
    {
        v1[ i ] = rand( ) % INT_MAX;
        v2[ i ] = rand( ) % INT_MAX;
    }
    sort( v1.begin( ), v1.end( ) );
    sort( v2.begin( ), v2.end( ) );
 
    tc.start( );
    set_difference( v1.begin( ), v1.end( ), v2.begin( ), v2.end( ), back_inserter( v3 ) );
    tc.stop( );
    backinserter_time = tc.get_time_string( );
 
    tc.start( );
    set_difference( v1.begin( ), v1.end( ), v2.begin( ), v2.end( ), inserter( v4, v4.begin( ) ) );
    tc.stop( );
    inserter_time = tc.get_time_string( );
 
    ShowMessage( "inserter_time =" + inserter_time + ", backinserter_time =" + backinserter_time );
Миниатюры
Ускорить алгоритм  
1
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
29.06.2014, 23:59
BRcr,Не интересно ставить такие опыты для людей предпочитающих тупить.
А для себя думаю будет интересно попробовать замеры с vector <std::wstring> и vector <UnicodeString>.
Для vector<UnicodeString> время должно меньше разнится чем для std::wstring.
0
12 / 12 / 9
Регистрация: 12.04.2012
Сообщений: 259
30.06.2014, 21:24  [ТС]
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
unsigned __stdcall OST( void* Param )
{
using namespace std;
auto_ptr<TStringList> SaveOst(new TStringList);
vector<String> v1;
vector<String> v2;
vector<String> v3;
 
 
for ( int i=0; i < lst->Count; i++ )
{
  v1.push_back(lst->Strings[i]);
}
for ( int q=0; q < lst2->Count; q++ )
{
  v2.push_back(lst2->Strings[q]);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), inserter( v3, v3.begin()) );
 vector<String>::iterator cur;
 
for ( cur=v3.begin(); cur < v3.end(); cur++ )
{
count1++;
       SaveOst->Add( *cur );
}
SaveOst->SaveToFile("Ostatok.txt");
_endthreadex(0);
 return 0;
}
Сделал так вроде работает и на много быстрее чем через StringList...
0
30.06.2014, 22:28

Не по теме:

К чему все говорилось (

0
12 / 12 / 9
Регистрация: 12.04.2012
Сообщений: 259
30.06.2014, 22:41  [ТС]
Код выше отрабатывает и так быстро мне хватит и этой скорости, просто в листах ну оооочень медленно все было сейчас меня устраивает и я понимаю что это не самый лучший вариант...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.06.2014, 22:41
Помогаю со студенческими работами здесь

Ускорить алгоритм составления списка файлов данной директории
Здравствуйте. Есть папка с файлами(462166 штук), как мне быстро получить их список, а следовательно и их количество? Вот, собственно,...

Ускорить программу
моя программа очень долго заносит данные из файла в мемо1 я так думаю это из-за того что считывание идет по циклу я знаю что можно щитати...

Ускорить вывод в RichEdit
Я генерирую миллион значений Все значения вывожу в поток: osftream p(&quot;text.txt&quot;); for(i=0; i &lt; 1000000; i++) { p &lt;&lt;...

Алгоритм шифрования DES (необходимо ускорить любым доступным способом)
Есть алгоритм шифрования дес, он работает но работает медленно ну или скажем так ... недостаточно быстро для того чтобы препод его принял....

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru