fork(1) download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <chrono>
  4. #include <cassert>
  5. #include <cstddef>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <ctime>
  9.  
  10. class muTimer
  11. {
  12.     using Clock = std::chrono::high_resolution_clock;
  13.     bool active = false;
  14.     Clock::duration   duration_;
  15.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  16.  
  17.     muTimer(const muTimer&)             = delete;
  18.     muTimer& operator=(const muTimer&)  = delete;
  19. public:
  20.     using ns       = std::chrono::nanoseconds;
  21.     using mks      = std::chrono::microseconds;
  22.     using ms       = std::chrono::milliseconds;
  23.     muTimer() { reset(); start(); }
  24.     ~muTimer() = default;
  25.     muTimer& reset()
  26.     {
  27.         duration_ = std::chrono::nanoseconds(0);
  28.         active    = false;
  29.         return *this;
  30.     }
  31.     muTimer& start()
  32.     {
  33.         if (!active)
  34.         {
  35.             start_ = Clock::now();
  36.             active = true;
  37.         }
  38.         return *this;
  39.     }
  40.     muTimer& stop()
  41.     {
  42.         if (active)
  43.         {
  44.             stop_      = Clock::now();
  45.             duration_ += stop_ - start_;
  46.             active     = false;
  47.         }
  48.         return *this;
  49.     }
  50.     template<typename T = mks>
  51.         unsigned long long duration()
  52.     {
  53.         return static_cast<unsigned long long>
  54.             (std::chrono::duration_cast<T>(stop_-start_).count());
  55.     }
  56. };
  57.  
  58. #ifdef _MSC_VER
  59. #define VTT_NO_INLINE __declspec(noinline)
  60. #else
  61. #define VTT_NO_INLINE __attribute__((noinline))
  62. #endif
  63.  
  64. void VTT_NO_INLINE TrimRight(char* s)
  65. {
  66.     size_t len = strlen(s);
  67.     char* iter = s + len - 1;
  68.     if (*iter != ' ') {
  69.         // Если последний символ не пробел,
  70.         // то и обрезать нечего
  71.         return;
  72.     }
  73.     while (*iter == ' ' && iter != s) {
  74.         // Идти от конца к началу,
  75.         // пока не кончатся пробелы либо строка
  76.         iter--;
  77.     }
  78.     if (iter == s) {
  79.         // Если строка пройдена
  80.         // и полностью состоит из пробелов
  81.         // то результатом будет пустая строка
  82.         *iter = '\0';
  83.     }
  84.     else {
  85.         // Если пройдены все пробелы
  86.         // и поиск дошел до первого не пробела,
  87.         // то заменить первый пробел на конец строки.
  88.         *(iter + 1) = '\0';
  89.     }
  90. }
  91.  
  92. void VTT_NO_INLINE qrimRight(char *s)
  93. {
  94.   char *spc=0, *p=s;
  95.  
  96.   while (*p)
  97.     if (*p == ' ')
  98.       for (spc=p; *++p==' '; );
  99.     else
  100.       ++p;
  101.  
  102.   if (spc && p!=s && p[-1]==' ') *spc = '\0';
  103. }
  104.  
  105. void VTT_NO_INLINE Trim_Naive(char * p_char)
  106. {
  107.     auto p_begin_or_last_non_ws{p_char};
  108.     for(;;)
  109.     {
  110.         switch(*p_char)
  111.         {
  112.             case '\0':
  113.             {
  114.                 break;
  115.             }
  116.             case ' ':
  117.             {
  118.                 ++p_char;
  119.                 continue;
  120.             }
  121.             default:
  122.             {
  123.                 p_begin_or_last_non_ws = p_char;
  124.                 ++p_char;
  125.                 continue;
  126.             }
  127.         }
  128.         break;
  129.     }
  130.     if(' ' == *p_begin_or_last_non_ws)
  131.     {
  132.         p_begin_or_last_non_ws[0] = '\0';
  133.     }
  134.     else
  135.     {
  136.         p_begin_or_last_non_ws[1] = '\0';
  137.     }
  138.     return;
  139. }
  140.  
  141. ::std::size_t VTT_NO_INLINE StrlenNaive(char * const psz_text)
  142. {
  143.     char * p_char{psz_text};
  144.     for(;;)
  145.     {
  146.         if('\0' == *p_char)
  147.         {
  148.             break;
  149.         }
  150.         ++p_char;
  151.     }
  152.     return(static_cast<::std::size_t>(p_char - psz_text));
  153. }
  154.  
  155. void test
  156. (
  157.     int const spaces_percent
  158. ,   ::std::size_t const trailing_spaces_percent
  159. ,   ::std::size_t const chars_count = 64'000'000
  160. )
  161. {
  162.     ::std::size_t const trailing_spaces_count{(chars_count * trailing_spaces_percent) / ::std::size_t{100}};
  163.     auto str_a{::std::make_unique<char[]>(chars_count)};
  164.     auto str_b{::std::make_unique<char[]>(chars_count)};
  165.     auto str_c{::std::make_unique<char[]>(chars_count)};
  166.     {
  167.         size_t i{};
  168.         for(; i < (chars_count - trailing_spaces_count); ++i)
  169.         {
  170.             str_a[i] = str_b[i] = str_c[i] = ((::std::rand() % 100) < spaces_percent) ? ' ' : (' ' + 1 + (::std::rand() % 87));
  171.         }
  172.         for(; i < (chars_count - 1); ++i)
  173.         {
  174.             str_a[i] = str_b[i] = str_c[i] = ' ';
  175.         }
  176.         str_a[i] = str_b[i] = str_c[i] = '\0';
  177.     }
  178.     ::std::cout << "chars count = " << chars_count << ::std::endl;
  179.     ::std::cout << "trailing spaces_percent = " << trailing_spaces_percent << ::std::endl;
  180.     ::std::cout << "spaces percent = " << spaces_percent << ::std::endl;
  181.     {
  182.         muTimer mt;
  183.         auto const len = strlen(str_c.get());
  184.         mt.stop();
  185.         ::std::cout << "strlen " << len << " " << mt.duration() << ::std::endl;
  186.     }
  187.     {
  188.         muTimer mt;
  189.         auto const len = StrlenNaive(str_c.get());
  190.         mt.stop();
  191.         ::std::cout << "strlen naive " << len << " " << mt.duration() << ::std::endl;
  192.     }
  193.     {
  194.         muTimer mt;
  195.         TrimRight(str_a.get());
  196.         mt.stop();
  197.         ::std::cout << "OP    " << mt.duration() << ::std::endl;
  198.     }
  199.     {
  200.         muTimer mt;
  201.         qrimRight(str_b.get());
  202.         mt.stop();
  203.         ::std::cout << "Q     " << mt.duration() << ::std::endl;
  204.     }
  205.     {
  206.         muTimer mt;
  207.         Trim_Naive(str_c.get());
  208.         mt.stop();
  209.         ::std::cout << "naive " << mt.duration() << ::std::endl;
  210.     }
  211.     ::std::cout << "cmp:"
  212.         " " << ::std::strcmp(str_a.get(), str_b.get()) <<
  213.         " " << ::std::strcmp(str_a.get(), str_c.get()) << ::std::endl;
  214. }
  215.  
  216. int main(int argc, const char * argv[])
  217. {
  218.     ::std::srand(::std::time(nullptr));
  219.     test(20, 1);
  220.     test(20, 50);
  221.     test(20, 99);
  222.     return 0;
  223. }
  224.  
Success #stdin #stdout 2.8s 190664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
chars count = 64000000
trailing spaces_percent = 1
spaces percent = 20
strlen 63999999 4612
strlen naive 63999999 22563
OP    4568
Q     115138
naive 36754
cmp: 0 0
chars count = 64000000
trailing spaces_percent = 50
spaces percent = 20
strlen 63999999 4268
strlen naive 63999999 22313
OP    21058
Q     76234
naive 59876
cmp: 0 0
chars count = 64000000
trailing spaces_percent = 99
spaces percent = 20
strlen 63999999 4167
strlen naive 63999999 22302
OP    37292
Q     19284
naive 37376
cmp: 0 0
https://ideone.com/ZUBQiw
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!