0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
1

Нужен совет в оптимизации кода

18.09.2018, 23:48. Показов 1349. Ответов 10

Нужно оптимизировать метод Deallocate, который переводит нужный указатель из allotted в exempted, и, если указателя нет, бросает ошибку. Я сделал через find, но есть ли способ сделать это быстрее?

C++
1
2
3
4
5
6
7
8
9
10
11
    void Deallocate(T* object) {//O(N)
        auto a = find(allotted.begin(), allotted.end(), object);//O(N)
        if (a != allotted.end()) {
            T* param = *a;
            exempted.push_back(param);          //O(1)
            allotted.erase(a);                  //O(end - a)
        }
        else {
            throw invalid_argument("");
        }
    }







Ниже весь код:
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
template <class T>
class ObjectPool {
public:
    T* Allocate() {//O(1)
        if (exempted.begin() != exempted.end()) {       //O(1)
            T* param = exempted.front();//O(1)
            allotted.push_back(param);  //O(1)
            exempted.pop_front();       //O(1)
            return param;
        }
        else {
            T* param = new T;
            allotted.push_back(param);//O(1)
            return param;
        }
    }
 
    T* TryAllocate() {//O(1)
        if (exempted.begin() != exempted.end()) {           //O(1)
            T* param = exempted.front();    //O(1)
            allotted.push_back(param);      //O(1)
            exempted.pop_front();           //O(1)
            return param;
        }
        else {
            return nullptr;
        }
    }
 
    void Deallocate(T* object) {//O(N)
        auto a = find(allotted.begin(), allotted.end(), object);//O(N)
        if (a != allotted.end()) {
            T* param = *a;
            exempted.push_back(param);          //O(1)
            allotted.erase(a);                  //O(end - a)
        }
        else {
            throw invalid_argument("");
        }
    }
 
    ~ObjectPool() {
 
    }
 
private:
    deque<T*> allotted, exempted;
};
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.09.2018, 23:48
Ответы с готовыми решениями:

Нужен совет!
Доброго времени суток! Возможно таких тем как эта было уже миллион.. но всё же, хотелось бы...

Нужен совет:
я учусь в 2-ом курсе на программиста у меня есть базовые знание c++,STL до сих пор работал...

Нужен совет с Canvas
Доброго времени суток, Нужен совет, через чего сделать следующее Дано: картинка с нарисованными...

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

10
165 / 108 / 57
Регистрация: 30.08.2018
Сообщений: 357
19.09.2018, 00:07 2
Например, взять другой контейнер с быстрым поиском, вместо дека. map set или что там ещё есть .

Добавлено через 1 минуту
А если удалять без проверки существования например ?
C++
1
allotted.erase(a);
Добавлено через 42 секунды
А нет, там UB
An invalid position or range causes undefined behavior.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
19.09.2018, 00:11  [ТС] 3
Я бы попытался использовать другой контейнер, но методы Allocate и TryAllocate должны возвращать объекты в порядке FIFO, т.е. множество exempted объектов должно представлять собой очередь: методы [Try]Allocate должны извлекать объекты из её начала, а метод Deallocate должен помещать объект в её конец. Так что, как мне кажется, дек там лучше всего подойдет(queue не взял потому что у него нет degin и end).
0
Форумчанин
Эксперт CЭксперт С++
8183 / 5033 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
19.09.2018, 14:36 4
Vakarine, можно кешировать указатели в каком-нибудь std::unordered_set. То есть дополнительно хранить их в контейнере, предназначенном для поиска.
Однако, в любом случае надо сначала определить, является ли данный участок кода слабым местом. Вы профилировали?

Добавлено через 2 минуты
Плюс можно производить деаллоцирование кучками, то есть сначала помечать их "флагом протухания" или помещать в специальный контейнер, а в свободное для процессора время начинать процесс очистки. Тут всё уже от архитектуры зависит. Но, в любом случае, такие действия должны быть оправданы. Если у вас небольшое количество данных, то разницы в микросекундах не принесут профита. Как говорил дедушка Кнут, "Преждевременная оптимизация - корень всех бед".
0
285 / 176 / 21
Регистрация: 16.02.2018
Сообщений: 666
19.09.2018, 17:21 5
boost::multi_index с sequenced и ordered индексами
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
19.09.2018, 17:41  [ТС] 6
MrGluck, Ну, там сложности я посчитал(в коде комментарии), и у Deallocate самая большая сложность, вот и предположил, что это он так время съедает.
0
15880 / 8643 / 2114
Регистрация: 30.01.2014
Сообщений: 14,871
19.09.2018, 18:42 7
Цитата Сообщение от Vakarine Посмотреть сообщение
есть ли способ сделать это быстрее?
Сделать интрузивный контейнер. Например список.
Тогда элемент сам будет знать своих соседей, и можно будет безопасно удалить его за O(1) без поиска вообще. Можно будет также совместить удаление и вставку в другой контейнер в одну операцию.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
19.09.2018, 18:50  [ТС] 8
DrOffset, Список - это queue? Но там ведь нельзя найти нужный элемент т.к нету begin и end, да и из него не удалить элемент, который ты перенес в другой список, если он не первый.
0
15880 / 8643 / 2114
Регистрация: 30.01.2014
Сообщений: 14,871
19.09.2018, 18:53 9
Vakarine, queue - это очередь.
Список - это list. Но не тот, который std::, с ним будут те же проблемы с поиском. А сделать свой - интрузивный (тут вы берете и идете гуглить что это), или взять из boost::intrusive_containers.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
19.09.2018, 18:57  [ТС] 10
Понятно, пойду пробовать, спасибо.
0
15880 / 8643 / 2114
Регистрация: 30.01.2014
Сообщений: 14,871
19.09.2018, 21:14 11
Лучший ответ Сообщение было отмечено MrGluck как решение

Решение

Vakarine,
С бустом примерчик быстро пишется (все умолчания оставил как были):
Кликните здесь для просмотра всего текста
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
65
66
67
68
69
#include <boost/intrusive/list.hpp>
#include <stdexcept>
#include <iostream>
 
using namespace boost::intrusive;
 
template <class T>
class ObjectPool {
    struct IntrusiveNode
        : T, list_base_hook<>
    { };
 
public:
    T * Allocate() {//O(1)
        if (!exempted.empty()) {       //O(1)
            allotted.splice(allotted.end(), exempted, exempted.begin()); // O(1)
            return &allotted.back();
        }
        else {
            IntrusiveNode * param = new IntrusiveNode;
            allotted.push_back(*param); //O(1)
            return param;
        }
    }
 
    T* TryAllocate() {//O(1)
        if (!exempted.empty()) {           //O(1)
            allotted.splice(allotted.end(), exempted, exempted.begin());
            return &allotted.back();
        }
        else {
            return nullptr;
        }
    }
 
    void Deallocate(T * object) {//O(1)
        IntrusiveNode * node = static_cast<IntrusiveNode *>(object);
 
        if(object && node->is_linked())
        {
            auto a = allotted.iterator_to(*node); // O(1)
            exempted.splice(exempted.end(), allotted, a); // O(1)
        }
        else {
            throw std::invalid_argument("");
        }
    }
 
    ~ObjectPool() {
        std::cout << "Allotted: " << allotted.size() << std::endl;
        std::cout << "Exempted: " << exempted.size() << std::endl;
    }
 
private:
    list<IntrusiveNode> allotted, exempted;
};
 
class A {};
 
int main()
{
    ObjectPool<A> pool;
 
    A * p1 = pool.Allocate();
    pool.Deallocate(p1);
 
    A * p2 = pool.Allocate();
    pool.Deallocate(p2);
}
http://rextester.com/DIRJQ73151
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.09.2018, 21:14
Помогаю со студенческими работами здесь

Змейка. Нужен совет как доработать программу
Недавно я зашел в тупик, работая над программой &quot;Змейка&quot;. Но несмотря на то, что в общем и целом...

Нужен совет. С++ курсовая с графикой в Linux или в Windows MSVS?
Добрый день. Необходимо сделать небольшой проект, который соответствовал требованиям. Для...

Дайте совет по реорганизации и оптимизации исходника
Здравствуйте, формчане. У Вас здесь я пишу впервые, хотя некоторое время уже следил за жизнью...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru