Оптимизировать поиск в std :: deque - PullRequest
Новая
       14

Оптимизировать поиск в std :: deque

0 голосов
/ 06 ноября 2018

Я делаю программу, которая имеет объекты другого типа, и все они являются детьми виртуального класса. Я делаю это в поисках преимуществ полиморфизма, которые позволяют мне вызывать из класса менеджера определенный метод для всех объектов без проверки конкретного типа объекта.

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

В тот момент мой цикл класса менеджера продумал все объекты и проверил тип объекта. Он создает список и возвращает его так: 

std::list<std::shared_ptr<Object>> ObjectManager::GetObjectsOfType(std::string type)
{
    std::list<std::shared_ptr<Object>> objectsOfType;

    for (int i = 0; i < m_objects.size(); ++i)
    {
        if (m_objects[i]->GetType() == type)
        {
            objectsOfType.push_back(m_objects[i]);
        }
    }

    return objectsOfType;
}

m_objects это deque. Я знаю, что повторение структуры данных стоит обычно дорого, но я хочу знать, возможно ли немного ее отшлифовать, потому что теперь эта функция занимает треть всего времени, используемого в программе.

У меня такой вопрос: Существует ли какая-либо схема проектирования или функция, которую я не принимаю во внимание, чтобы снизить стоимость этой операции в моей программе?

Ответы [ 2 ]

0 голосов
/ 06 ноября 2018

В приведенном коде есть только одна оптимизация, которая может быть выполнена локально: 

for (auto const& obj : m_objects)
{
    if (obj->GetType() == type)
    {
        objectsOfType.push_back(obj);
    }
}

Смысл в том, что operator[], как правило, не самый эффективный способ доступа к deque. Сказав это, я не ожидаю значительного улучшения. Ваше месторасположение очень плохое: по сути, вы смотрите на две разыменования (shared_ptr и string).

Логическим подходом было бы сделать m_objects a std::multimap ключом по типу.

0 голосов
/ 06 ноября 2018

Некоторые вещи, которые вы можете сделать, чтобы ускорить:

  • Храните тип в базовом классе, это удалит довольно дорогой виртуальный поиск.
  • Если тип string и т. Д., Измените его на
    тип simpel, такой как enum или int
  • A vector эффективнее
    ход, чем deque
  • если останется с deque, используйте итераторы или диапазон, основанный на цикле for, чтобы избежать случайных поисков (которые дороже в deque)

Диапазон на основе выглядит следующим образом: 

for (auto const& obj : m_objects)
{
    if (obj->GetType() == type)
    {
        objectsOfType.push_back(obj);
    }
}

Обновление: Также я бы рекомендовал не использовать std::list (если по какой-то причине вам не нужно), так как во многих случаях он не очень хорошо работает - опять же std::vector приходит на помощь!

...