Информация об изменениях

Сообщение Re[3]: Исправление скобок от 09.06.2017 9:35

Изменено 09.06.2017 9:50 rg45

Старый текст
Новый текст
Разница

Re[3]: Исправление скобок

Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, rg45, Вы писали:

R>>Ну вот, например, такое решение канает как красивое?

R>>http://ideone.com/8jWHts

_>С этой строкой попробуй c "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))"
_>

_>g++ aa.cpp && time ./a.out "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" | tail
_>681114 ()(())(()())(())((())(()))(((((()(((((()))))))))))
_>681115 ()(())(()())(())((())(()))(()(((())(()())((())))))
_>681116 ()(())(()())(())((())(()))((()((())(()())((())))))
_>681117 ()(())(()())(())((())(()))(()((())(()())((())())))
_>681118 ()(())(()())(())((())(()))((()(())(()())((())())))
_>681119 ()(())(()())(())((())(()))(()(())(()())((())(())))
_>681120 ()(())(()())(())((())(()))((()())(()())((())(())))
_>681121 ()(())(()())(())((())(()))(()())(()())((())(()()))
_>681122 ()(())(()())(())((())(()))((()))(()())((())(()()))
_>variants count=681122
_>

Ну так то ведь был просто эскиз безо всякой оптимизации. После самой косметической оптимизации у меня этот пример считается за 7.5 секунды. Только количество вариантов у меня получается побольше, чем у тебя, а именно 966730. Кто-то из нас где-то налажал

Оптимизированный вариант

#include <iostream>
#include <set>
#include <string>
#include <windows.h>

class RedundantBracketRemover
{
public:

   RedundantBracketRemover(const std::string& s)
   {
      remove_redundant_brackets(s, 0);
   }

   const std::set<std::string>& get() const { return m_output; }

private:
   void remove_redundant_opening_brackets(const std::string& s, size_t end)
   {
      int level = 0;
      for (size_t i = end; i--;)
      {
         if (s[i] == ')')
         {
            ++level;
         }
         else if (s[i] == '(' && --level < 0)
         {
            char last = 0;
            for (size_t j = i; j < s.length(); ++j)
            {
               if (s[j] == '(' && last != '(')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                     remove_redundant_opening_brackets(s2, i);
               }
               last = s[j];
            }
            return;
         }
      }
      m_output.insert(s);
   }

   void remove_redundant_brackets(const std::string& s, size_t begin)
   {
      int level = 0;
      for (size_t i = begin; i < s.length(); ++i)
      {
         if (s[i] == '(')
         {
            ++level;
         }
         else if (s[i] == ')' && --level < 0)
         {
            char last = 0;
            for (size_t j = 0; j <= i; ++j)
            {
               if (s[j] == ')' && last != ')')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                  {
                     remove_redundant_brackets(s2, i);
                  }
               }
               last = s[j];
            }
            return;
         }
      }
      remove_redundant_opening_brackets(s, s.length());
   }
private:
   std::set<std::string> m_output;
   std::set<std::string> m_nodes;
};

std::set<std::string> remove_redundant_brackets(const std::string& s)
{
   return RedundantBracketRemover(s).get();
}

int main()
{
   const auto s = "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))";
   //const auto s = "(a)())()))((b(b)";

   auto t0 = GetTickCount();
   auto variants = remove_redundant_brackets(s).size();
   auto time  = GetTickCount() - t0;

   std::cout << "variants: " << variants << std::endl;
   std::cout << "time: " << time << std::endl;

//   for (auto&& s : remove_redundant_brackets(s))
//   {
//      std::cout << s << std::endl;
//   }
}

Re[3]: Исправление скобок

R>>http://ideone.com/8jWHts

_>С этой строкой попробуй c "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))"
_>

_>g++ aa.cpp && time ./a.out "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" | tail
_>681114 ()(())(()())(())((())(()))(((((()(((((()))))))))))
_>681115 ()(())(()())(())((())(()))(()(((())(()())((())))))
_>681116 ()(())(()())(())((())(()))((()((())(()())((())))))
_>681117 ()(())(()())(())((())(()))(()((())(()())((())())))
_>681118 ()(())(()())(())((())(()))((()(())(()())((())())))
_>681119 ()(())(()())(())((())(()))(()(())(()())((())(())))
_>681120 ()(())(()())(())((())(()))((()())(()())((())(())))
_>681121 ()(())(()())(())((())(()))(()())(()())((())(()()))
_>681122 ()(())(()())(())((())(()))((()))(()())((())(()()))
_>variants count=681122
_>

Ну так то ведь был просто эскиз безо всякой оптимизации. После самой косметической оптимизации у меня этот пример считается за 7.5 секунды (с переходом с dinkumware на stlport время уменьшается до 5 сек). Только количество вариантов у меня получается побольше, чем у тебя, а именно 966730. Кто-то из нас где-то налажал

Оптимизированный вариант

#include <iostream>
#include <set>
#include <string>
#include <windows.h>

class RedundantBracketRemover
{
public:

   RedundantBracketRemover(const std::string& s)
   {
      remove_redundant_brackets(s, 0);
   }

   const std::set<std::string>& get() const { return m_output; }

private:
   void remove_redundant_opening_brackets(const std::string& s, size_t end)
   {
      int level = 0;
      for (size_t i = end; i--;)
      {
         if (s[i] == ')')
         {
            ++level;
         }
         else if (s[i] == '(' && --level < 0)
         {
            char last = 0;
            for (size_t j = i; j < s.length(); ++j)
            {
               if (s[j] == '(' && last != '(')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                     remove_redundant_opening_brackets(s2, i);
               }
               last = s[j];
            }
            return;
         }
      }
      m_output.insert(s);
   }

   void remove_redundant_brackets(const std::string& s, size_t begin)
   {
      int level = 0;
      for (size_t i = begin; i < s.length(); ++i)
      {
         if (s[i] == '(')
         {
            ++level;
         }
         else if (s[i] == ')' && --level < 0)
         {
            char last = 0;
            for (size_t j = 0; j <= i; ++j)
            {
               if (s[j] == ')' && last != ')')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                  {
                     remove_redundant_brackets(s2, i);
                  }
               }
               last = s[j];
            }
            return;
         }
      }
      remove_redundant_opening_brackets(s, s.length());
   }
private:
   std::set<std::string> m_output;
   std::set<std::string> m_nodes;
};

std::set<std::string> remove_redundant_brackets(const std::string& s)
{
   return RedundantBracketRemover(s).get();
}

int main()
{
   const auto s = "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))";
   //const auto s = "(a)())()))((b(b)";

   auto t0 = GetTickCount();
   auto variants = remove_redundant_brackets(s).size();
   auto time  = GetTickCount() - t0;

   std::cout << "variants: " << variants << std::endl;
   std::cout << "time: " << time << std::endl;

//   for (auto&& s : remove_redundant_brackets(s))
//   {
//      std::cout << s << std::endl;
//   }
}