fork download
copy 
  1. #include <algorithm>
  2. #include <array>
  3. #include <ctime>
  4. #include <iostream>
  5. #include <random>
  6. #include <vector>
  7.  
  8. #define PRECOMPUTE_RANDOM 1
  9.  
  10. bool isPermutation(const std::string &inputa, const std::string &inputb)
  11. {
  12.   static const size_t MAX_CHAR = 256;
  13.   std::array<int, MAX_CHAR> allChars;
  14.   allChars.fill(0);
  15.  
  16.   for (auto c : inputa)
  17.     ++allChars[c];
  18.  
  19.   for (auto c : inputb)
  20.   {
  21.     --allChars[c];
  22.     if (allChars[c] < 0)
  23.       return false;
  24.   }
  25.  
  26.   return true;
  27. }
  28.  
  29. bool isPermutationSort(const std::string& a, const std::string& b) {
  30. 	return std::is_permutation(a.begin(), a.end(), b.begin());
  31. }
  32.  
  33. int main()
  34. {
  35.   const std::vector<std::string> bag
  36.   {
  37.     "god", "dog", "thisisaratherlongerinput", "thisisarathershorterinput",
  38.     "armen", "ramen"
  39.   };
  40.  
  41.   const unsigned stop = 1000000;
  42.  
  43. #if !PRECOMPUTE_RANDOM
  44.   static std::mt19937 engine;
  45.   std::uniform_int_distribution<std::size_t> rand(0, bag.size() - 1);
  46. #else
  47.   static size_t engine = 0;
  48.   static unsigned int evals[4 * stop];
  49. {
  50.   static std::mt19937 engine;
  51.   std::uniform_int_distribution<std::size_t> rand(0, bag.size() - 1);
  52.   for(unsigned int i = 0; i < sizeof(evals)/sizeof(*evals); ++i)
  53.     evals[i] = rand(engine);
  54. }
  55.   auto rand = [](size_t& engine) {
  56.     return evals[engine++];
  57.   };
  58. #endif
  59.  
  60.   unsigned counter = 0;
  61.   std::clock_t start = std::clock();
  62.   for (unsigned i(0); i < stop; ++i)
  63.     counter += isPermutation(bag[rand(engine)], bag[rand(engine)]);
  64.  
  65.   double time = (clock() - start) / (double)CLOCKS_PER_SEC;
  66.   std::cout << counter << ": " << time << " s\n";
  67.  
  68.   counter = 0;
  69.   start = std::clock();
  70.   for (unsigned i(0); i < stop; ++i)
  71.     counter += isPermutationSort(bag[rand(engine)], bag[rand(engine)]);
  72.  
  73.   time = (clock() - start) / (double)CLOCKS_PER_SEC;
  74.   std::cout << counter << ": " << time << " s\n";
  75.  
  76.   return 0;
  77. }
  78.  
Success #stdin #stdout 0.72s 19048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
277564: 0.408146 s
278252: 0.051862 s
https://ideone.com/4Rpcwe
language:
C++14 (gcc 8.3)
created:
9 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!