C ++: функция оптимальной сложности - PullRequest
Новая
       8

C ++: функция оптимальной сложности

0 голосов
/ 19 декабря 2018

Мне задали вопрос в интервью:

У нас есть пакеты, указанные ниже (пакеты, как в компонентах программной системы) -

pkg1 -> pkg2, pkg3, pkg4

pkg2 -> pkg5, pkg6

pkg7 -> pkg8, pkg9

pkg9 -> pkg10, pkg11

, где Pkg1 зависит от pkg2, 3, 4.

pkg2 зависит от pkg5, 6 и т. Д.

Эти пакеты должны быть собраны (скомпилированы).Независимые пакеты могут быть построены параллельно для самой быстрой компиляции.

Напишите функцию C ++, чтобы вывести список независимых пакетов и зависимых пакетов с максимальной сложностью по времени.Вы можете создать сигнатуру функции, чтобы вы могли выбрать, каким контейнером будут данные входного пакета.

Вывод (на стандартный вывод) - Независимые пакеты - pkg3, pkg4, pkg5, pkg6, pkg8, pkg10,pkg11 Зависимые пакеты - pkg1, pkg2, pkg7, pkg9

В моем решении я использовал std :: map для входных пакетов и использовал std :: set и std :: vector для зависимых иНезависимые пакеты соответственно.

Временная сложность, которую я мог достичь, была O (mn), где m - количество зависимых пакетов, а n - количество независимых пакетов.Можем ли мы достичь большего?Как?Любая помощь / руководство приветствуется.

Заранее спасибо.

Редактировать 1: Думаю, я приведу здесь мою реализацию - 

#include <iostream>
void filterPackages(const std::map<int, std::vector<int> > &packages)
{
    std::vector<int> potential_independent_packages;
    std::set<int> dependent_packages;

    for(auto iter : packages)
    {
        dependent_packages.insert(iter.first);
        for(auto iter1 : iter.second)
        {
            potential_independent_packages.push_back(iter1);
        }
    }

    std::cout<<"Independent package - ";
    for( auto iter2 : potential_independent_packages)
    {
        if(dependent_packages.found(iter2) == std::set::end)
        {
            std::cout<<iter2;
        }
    }

    std::cout<<std::endl<<"Dependent packages - ";
    for( auto iter3 : dependent_packages)
    {
        std::cout<<iter3;
    }
}

1 Ответ

0 голосов
/ 20 декабря 2018

Это не было четко указано в описании, но я предполагаю, что вы имели в виду, что пакет не может быть скомпилирован, если некоторые из пакетов, от которых он зависит, еще не скомпилированы.

При таком предположении существует довольно простой код, который оптимизирует порядок компиляции.Вычислить глубину зависимости для каждого пакета, а затем скомпилировать в параллельные пакеты одинаковой глубины, начиная с пакетов с наименьшей глубиной.

(Что такое «глубина зависимости»? Думайте о зависимости как о направленном дереве, тогда глубина элемента - это самый длинный путь от элемента до листьев, от которых она зависит. Формально, если пакет не имеетзависимости, тогда его глубина равна нулю, а для других Depth [package] = max (Depth [depen_of_the_package]) + 1. Обратите внимание, что пакеты одинаковой глубины обязательно независимы друг от друга)

Я бы использовал следующий код 

class PackageOptimizer
{
    public:
    struct PackageDependency
    {  
        size_t Count() const
        {
            return m_end - m_begin;
        }
        size_t m_begin;
        size_t m_end;
    };

    vector<size_t> FindLeaves()
    {
        vector<size_t> leaves;
        for(size_t i = 0; i<m_deps.size(); i++)
        {
            if(m_deps[i].m_begin == m_deps[i].m_end)
                leaves.push_back(i);
        }

        return leaves;
    }

    vector<int> ComputeDepthMap()
    {
        vector<int> Depth(m_deps.size());
        vector<int> Count(m_deps.size(),0);
        vector<size_t> currSet = FindLeaves();
        vector<size_t> nextSet;

        int currDepth = 0;
        while(!currSet.empty())
        {
           for(size_t elem : currSet)
           {
               Depth[elem] = currDepth;

               for( size_t  upPackage = m_depsInv[elem].m_begin;
                            upPackage < m_depsInv[elem].m_end; 
                            upPackage++)
                {
                    Count[upPackage]++;

                    if(Count[upPackage] == m_deps[upPackage].Count())
                    {
                        nextSet.push_back(upPackage);
                    }
                }
           } 
           swap(nextSet, currSet);
           currDepth++;
           nextSet.clear();
        }

        return Depth;
    }

    private:
    // package i is dependent on
    // m_indices[m_deps[i].m_begin], m_indices[m_deps[i].m_begin+1], ... m_indices[m_deps[i].m_end-1]
    vector<PackageDependency>   m_deps; 
    vector<size_t>              m_indices;

    // following packages are dependant on package i
    // m_indicesInv[m_depsInv[i].m_begin], m_indicesInv[m_depsInv[i].m_begin+1], ... m_indicesInv[m_deps[i].m_end-1]
    vector<PackageDependency>   m_depsInv; 
    vector<size_t>              m_indicesInv;
};

У него просто нет методов для инициации m_deps, m_indices, m_depsInv, m_indicesInv, но это не сложно.С вычислением Depth вы можете легко организовать пакеты, соответствующие порядку выполнения.Кроме того, вам нужно убедиться, что в пакетах нет циклов зависимости, иначе этот код никогда не завершится.

С точки зрения производительности этот алгоритм занимает около O(n + m), где n - это числопакетов и m - общее количество зависимостей.Создание m_deps, m_indices, m_depsInv, m_indicesInv должно занимать примерно одинаковое количество времени.

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

...