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

@leva · Регистрация: 12.04.2012

Студворк — интернет-сервис помощи студентам

Есть код который сохраняет строку из 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;
}

Работает не достаточно быстро, как можно эффективно изменить алгоритм для ускорения программы...

@BRcr · 01.07.2014, 01:39

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

и я понимаю что это не самый лучший вариант...

На несколько порядков не лучший, но хозяин - барин... Заменить пять буковок кода - это, конечно же, излишние заморочки. ))
Кстати, о сортировке изначально не было сказано ни слова.

@kzru_hunter · 02.07.2014, 17:00

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

vector < int > v1( size ), v2( size ), v3( size ), v4( size );

Заметил ошибку.

Нужно так:

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

vector < int > v1( size ), v2( size ), v3, v4;

У меня так std::inserter на 0.1-0.5 мс быстрее отрабатывает

@Retyrn0 · 03.07.2014, 01:34

Что серьёзно? Никого кроме меня не смущает

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

SaveOst->SaveToFile("Ostatok.txt");

?

@BRcr · 03.07.2014, 15:00

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

Заметил ошибку.

Все верно, моя ошибка.

Погонял на разных диапазонах - back_inserter у меня отрабатывает в среднем на 5 - 10 % быстрее.

Добавлено через 3 минуты
Retyrn0, сохранение происходит один раз по завершении выборки. Сохраняется стандартным методом класса TStringList. Так что нет - никого кроме тебя это не смущает.

Если есть желание сравнить скорости записи в файл различными способами - милости просим.

@Avazart · 03.07.2014, 15:10

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

Погонял на разных диапазонах - back_inserter у меня отрабатывает в среднем на 5 - 10 % быстрее.

Ну оценивать в % не корректно, ибо разница будет тем больше чем больше элементов вставляться.
Кроме того логично было бы делать reserve() что бы исключить перераспределение памяти.

@Retyrn0 · 03.07.2014, 15:11

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

сохранение происходит один раз по завершении выборки

Ну я не видел весь код, а ты? Если предположить что функция вызывается внутри другого цикла...мне трудно представить такой длинный список, чтобы ТС не хватало скорости...

@Avazart · 03.07.2014, 15:23

Ну логичнее было сохранять с помощью fstream,
тогда можно было бы с экономить время на излишнем преобразование std::vector<String> -> TStringList

@BRcr · 03.07.2014, 15:51

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

Если предположить что функция вызывается внутри другого цикла...мне трудно представить такой длинный список, чтобы ТС не хватало скорости...

Зачем такое предполагать? На это нет оснований. Спроси у ТС - и всех делов.
А насчет длины списка и скорости - у ТС может быть малопроизводительная система либо очень большие объемы текста. В обоих случаях даже самый оптимизированный алгоритм может работать относительно долго.

Добавлено через 3 минуты
Avazart, провел тесты. Опять смешные результаты.

При увеличении количества элементов в векторах разница скорости уменьшается. При этом использование reserve никаких заметных изменений в картину не вносит. Парадокс какой-то...

@Avazart · 03.07.2014, 19:37

http://microfork.com/stdvector... -analisys/

Пример для понимания разницы

Код

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <string>
 
#include <iostream>
#include <vector>
#include <string>
 
class test
{
    public:
        test(const int n):n_(n)
        {
            std::cout<<"constructor "<<n_<<std::endl;
        };
 
        test(const test& some)
        {
           std::cout<<"copy constructor "<<some.n_<<std::endl;
           n_= some.n_;
        }
 
        test& operator=(const test& some)
        {
            std::cout<<"assign "<<n_<<"="<<some.n_<<std::endl;
            n_= some.n_;
            return *this;
        }
 
        ~test()
        {
            std::cout<<"destructor "<<n_<<std::endl;
        };
 
    private:
        int n_;
};
 
int main()
{
    std::vector<test> vtest1;
    std::vector<test> vtest2;
 
    const size_t size= 4;
    vtest1.reserve(size);
    vtest2.reserve(size);
 
    std::cout<<std::endl<<"insert():"<<std::endl;
    for(size_t i=0; i<size; ++i)
    {
        std::cout<<i<<")"<<std::endl;
        vtest1.insert(vtest1.begin(),test(i));
    }
 
    std::cout<<std::endl<<"push_back():"<<std::endl;
    for(size_t i=0; i<size; ++i)
    {
        std::cout<<i<<")"<<std::endl;
        vtest2.push_back(test(i));
    }
 
    getchar();
    return 0;
}

Вывод для МSVС2010

insert():
0)
constructor 0
copy constructor 0
destructor 0
1)
constructor 1
copy constructor 1
copy constructor 1
assign 1=0
assign 0=1
destructor 1
destructor 1
2)
constructor 2
copy constructor 2
copy constructor 0
assign 0=1
assign 1=0
destructor 0
copy constructor 0
assign 0=2
assign 2=0
destructor 0
destructor 2
3)
constructor 3
copy constructor 3
copy constructor 1
assign 1=2
assign 2=1
destructor 1
copy constructor 1
assign 1=3
assign 3=1
destructor 1
copy constructor 1
assign 1=0
assign 0=1
destructor 1
destructor 3

push_back():
0)
constructor 0
copy constructor 0
destructor 0
1)
constructor 1
copy constructor 1
destructor 1
2)
constructor 2
copy constructor 2
destructor 2
3)
constructor 3
copy constructor 3
destructor 3

Вывод для С++BuilderXE3 (x86)

insert():
0)
constructor 0
copy constructor 0
copy constructor 0
destructor 0
destructor 0
1)
constructor 1
copy constructor 1
copy constructor 0
assign 0=1
destructor 1
destructor 1
2)
constructor 2
copy constructor 2
copy constructor 0
assign 0=1
assign 1=2
destructor 2
destructor 2
3)
constructor 3
copy constructor 3
copy constructor 0
assign 0=1
assign 1=2
assign 2=3
destructor 3
destructor 3

push_back():
0)
constructor 0
copy constructor 0
destructor 0
1)
constructor 1
copy constructor 1
destructor 1
2)
constructor 2
copy constructor 2
destructor 2
3)
constructor 3
copy constructor 3
destructor 3

Онлайн компилятор http://codepad.org/qp9FP2b1

Чет с XE3 непонятки, как обычно...

@Retyrn0 · 03.07.2014, 21:09

Не по теме:

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

На это нет оснований

Нет оснований утверждать обратное.

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

Спроси у ТС - и всех делов

Вот тут согласен.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Avazart 8488 / 6155 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	03.07.2014, 15:23
	Ну логичнее было сохранять с помощью fstream, тогда можно было бы с экономить время на излишнем преобразование std::vector<String> -> TStringList 0