fork download
copy 
  1. #include <string>
  2. #include <cstdlib>
  3. #include <chrono>
  4. #include <algorithm>
  5. #include <cassert>
  6. #include <climits>
  7. #include <iostream>
  8.  
  9. void append_Ethon(std::string& s, int value, int radix=10)
  10. {
  11.     if(value < 0)
  12.     {
  13.         s.push_back('-');
  14.         value = -value;
  15.     }
  16.  
  17.     assert(radix > 1 && radix < 17);
  18.     char const* chars = "0123456789abcdef";
  19.  
  20.     char buffer[sizeof(int) * CHAR_BIT];
  21.     char* iter = buffer;
  22.     while(value >= radix)
  23.     {
  24.         *iter = chars[value % radix];
  25.         value /= radix;
  26.         ++iter;
  27.     }
  28.     *iter = chars[value];
  29.  
  30.     s.append(std::reverse_iterator<char*>(iter + 1), std::reverse_iterator<char*>(buffer));
  31. }
  32.  
  33. void append_Ethon2(std::string& s, int value, int radix=10)
  34. {
  35.     if(value < 0)
  36.     {
  37.         s.push_back('-');
  38.         value = -value;
  39.     }
  40.  
  41.     assert(radix > 1 && radix < 11);
  42.  
  43.     char buffer[sizeof(int) * CHAR_BIT];
  44.     char* iter = buffer;
  45.     while(value >= radix)
  46.     {
  47.         *iter = '0' + value % radix;
  48.         value /= radix;
  49.         ++iter;
  50.     }
  51.     *iter = '0' + value % radix;
  52.  
  53.     s.append(std::reverse_iterator<char*>(iter + 1), std::reverse_iterator<char*>(buffer));
  54. }
  55.  
  56. void append_Ethon3(std::string& s, int value)
  57. {
  58.     if(value < 0)
  59.     {
  60.         s.push_back('-');
  61.         value = -value;
  62.     }
  63.  
  64.     char const* chars =
  65.         "00010203040506070809"
  66.         "10111213141516171819"
  67.         "20212223242526272829"
  68.         "30313233343536373839"
  69.         "40414243444546474849"
  70.         "50515253545556575859"
  71.         "60616263646566676869"
  72.         "70717273747576777879"
  73.         "80818283848586878889"
  74.         "90919293949596979899"
  75.       ;
  76.  
  77.     char buffer[64];
  78.     char* iter = buffer;
  79.     while(value >= 100)
  80.     {
  81.         *iter = chars[value % 100 * 2 + 1];
  82.         ++iter;
  83.         *iter = chars[value % 100 * 2];
  84.         value /= 100;
  85.         ++iter;
  86.     }
  87.     if(value >= 10)
  88.     {
  89.         *iter = chars[value * 2];
  90.         ++iter;
  91.         *iter = chars[value * 2 + 1];
  92.         ++iter;
  93.     }
  94.     else
  95.     {
  96.         *iter = '0' + value;
  97.     }
  98.  
  99.     s.append(std::reverse_iterator<char*>(iter + 1), std::reverse_iterator<char*>(buffer));
  100. }
  101.  
  102. void append_Ethon4(std::string& s, int value)
  103. {
  104.     if(value < 0)
  105.     {
  106.         s.push_back('-');
  107.         value = -value;
  108.     }
  109.  
  110.     char const* chars =
  111.         "00010203040506070809"
  112.         "10111213141516171819"
  113.         "20212223242526272829"
  114.         "30313233343536373839"
  115.         "40414243444546474849"
  116.         "50515253545556575859"
  117.         "60616263646566676869"
  118.         "70717273747576777879"
  119.         "80818283848586878889"
  120.         "90919293949596979899"
  121.       ;
  122.  
  123.     unsigned size;
  124.     if(value >=10000)
  125.     {
  126.         if(value >=10000000)
  127.         {
  128.             if(value >=1000000000)
  129.                 size=10;
  130.             else if(value >=100000000)
  131.                 size=9;
  132.             else 
  133.                 size=8;
  134.         }
  135.         else
  136.         {
  137.             if(value >=1000000)
  138.                 size=7;
  139.             else if(value >=100000)
  140.                 size=6;
  141.             else
  142.                 size=5;
  143.         }
  144.     }
  145.     else 
  146.     {
  147.         if(value >=100)
  148.         {
  149.             if(value >=1000)
  150.                 size=4;
  151.             else
  152.                 size=3;
  153.         }
  154.         else
  155.         {
  156.             if(value >=10)
  157.                 size=2;
  158.             else
  159.                 size=1;
  160.         }
  161.     }
  162.  
  163.     s.resize(s.size() + size);
  164.     std::reverse_iterator<std::string::iterator> iter( (s.end()) );
  165.     while(value >= 100)
  166.     {
  167.         *iter = chars[value % 100 * 2 + 1];
  168.         ++iter;
  169.         *iter = chars[value % 100 * 2];
  170.         value /= 100;
  171.         ++iter;
  172.     }
  173.     if(value >= 10)
  174.     {
  175.         *iter = chars[value * 2];
  176.         ++iter;
  177.         *iter = chars[value * 2 + 1];
  178.         ++iter;
  179.     }
  180.     else
  181.     {
  182.         *iter = '0' + value;
  183.     }
  184. }
  185.  
  186. void append_snprintf(std::string& s, int value)
  187. {
  188.     char buffer[64];
  189.     snprintf(buffer, 64, "%d", value);
  190.     s.append(buffer);
  191. }
  192.  
  193. void append_tostring(std::string& s, int value)
  194. {
  195.     s.append(std::to_string(value));
  196. }
  197.  
  198. void append_stackoverflow1(std::string& s, int n)
  199. {
  200.     const char digit_pairs[201] = {
  201.       "00010203040506070809"
  202.       "10111213141516171819"
  203.       "20212223242526272829"
  204.       "30313233343536373839"
  205.       "40414243444546474849"
  206.       "50515253545556575859"
  207.       "60616263646566676869"
  208.       "70717273747576777879"
  209.       "80818283848586878889"
  210.       "90919293949596979899"
  211.     };
  212.  
  213.     if(n==0)
  214.     {
  215.         s += "0";
  216.         return;
  217.     }
  218.  
  219.     int sign = -(n<0);
  220.     unsigned int val = (n^sign)-sign;
  221.  
  222.     int size;
  223.     if(val>=10000)
  224.     {
  225.         if(val>=10000000)
  226.         {
  227.             if(val>=1000000000)
  228.                 size=10;
  229.             else if(val>=100000000)
  230.                 size=9;
  231.             else 
  232.                 size=8;
  233.         }
  234.         else
  235.         {
  236.             if(val>=1000000)
  237.                 size=7;
  238.             else if(val>=100000)
  239.                 size=6;
  240.             else
  241.                 size=5;
  242.         }
  243.     }
  244.     else 
  245.     {
  246.         if(val>=100)
  247.         {
  248.             if(val>=1000)
  249.                 size=4;
  250.             else
  251.                 size=3;
  252.         }
  253.         else
  254.         {
  255.             if(val>=10)
  256.                 size=2;
  257.             else
  258.                 size=1;
  259.         }
  260.     }
  261.     size -= sign;
  262.     auto oldSize = s.size();
  263.     s.resize(oldSize + size);
  264.     char* c = &s[oldSize];
  265.     if(sign)
  266.         *c='-';
  267.  
  268.     c += size-1;
  269.     while(val>=100)
  270.     {
  271.        int pos = val % 100;
  272.        val /= 100;
  273.        *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
  274.        c-=2;
  275.     }
  276.     while(val>0)
  277.     {
  278.         *c--='0' + (val % 10);
  279.         val /= 10;
  280.     }
  281. }
  282.  
  283. unsigned const N = 10000000;
  284.  
  285. int main()
  286. {
  287.     using namespace std;
  288.     srand(time(0));
  289.  
  290.     vector<int> values( (N) );
  291.     generate(values.begin(), values.end(), rand);
  292.  
  293.     // Warmup.
  294.     {
  295.         string s;
  296.  
  297.         for(unsigned i = 0; i < N; ++i)
  298.             append_Ethon(s, values[i]);
  299.  
  300.         cout << "Anti Optimize: " << s.back() << endl;
  301.     }
  302.  
  303.     {
  304.         string s;
  305.  
  306.         auto start = chrono::high_resolution_clock::now();
  307.         for(unsigned i = 0; i < N; ++i)
  308.             append_Ethon(s, values[i]);
  309.         auto end = chrono::high_resolution_clock::now();
  310.  
  311.         cout << "Ethon (Lookuptable): " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  312.         cout << "Anti Optimize: " << s.back() << endl;
  313.     }
  314.  
  315.     {
  316.         string s;
  317.  
  318.         auto start = chrono::high_resolution_clock::now();
  319.         for(unsigned i = 0; i < N; ++i)
  320.             append_Ethon2(s, values[i]);
  321.         auto end = chrono::high_resolution_clock::now();
  322.  
  323.         cout << "Ethon (No Lookuptable): " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  324.         cout << "Anti Optimize: " << s.back() << endl;
  325.     }
  326.  
  327.     {
  328.         string s;
  329.  
  330.         auto start = chrono::high_resolution_clock::now();
  331.         for(unsigned i = 0; i < N; ++i)
  332.             append_Ethon3(s, values[i]);
  333.         auto end = chrono::high_resolution_clock::now();
  334.  
  335.         cout << "Ethon (Larger Lookuptable): " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  336.         cout << "Anti Optimize: " << s.back() << endl;
  337.     }
  338.  
  339.     {
  340.         string s;
  341.  
  342.         auto start = chrono::high_resolution_clock::now();
  343.         for(unsigned i = 0; i < N; ++i)
  344.             append_Ethon4(s, values[i]);
  345.         auto end = chrono::high_resolution_clock::now();
  346.  
  347.         cout << "Ethon (Larger Lookuptable, no Buffer): " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  348.         cout << "Anti Optimize: " << s.back() << endl;
  349.     }
  350.  
  351.     {
  352.         string s;
  353.  
  354.         auto start = chrono::high_resolution_clock::now();
  355.         for(unsigned i = 0; i < N; ++i)
  356.             append_tostring(s, values[i]);
  357.         auto end = chrono::high_resolution_clock::now();
  358.  
  359.         cout << "std::to_string: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  360.         cout << "Anti Optimize: " << s.back() << endl;
  361.     }
  362.  
  363.     {
  364.         string s;
  365.  
  366.         auto start = chrono::high_resolution_clock::now();
  367.         for(unsigned i = 0; i < N; ++i)
  368.             append_snprintf(s, values[i]);
  369.         auto end = chrono::high_resolution_clock::now();
  370.  
  371.         cout << "snprintf: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  372.         cout << "Anti Optimize: " << s.back() << endl;
  373.     }
  374.  
  375.     {
  376.         string s;
  377.  
  378.         auto start = chrono::high_resolution_clock::now();
  379.         for(unsigned i = 0; i < N; ++i)
  380.             append_stackoverflow1(s, values[i]);
  381.         auto end = chrono::high_resolution_clock::now();
  382.  
  383.         cout << "stackoverflow1: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
  384.         cout << "Anti Optimize: " << s.back() << endl;
  385.     }
  386. }
  387.  
Time limit exceeded #stdin #stdout 5s 74816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Anti Optimize: 4
https://ideone.com/lGkIcy
language:
C++14 (gcc 8.3)
created:
13 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!