fork(1) download 
  1. // TanosMeanLessMemory.cpp : This file contains the 'main' function. Program execution begins and ends there.
  2. //
  3.  
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <random>
  9. #include <chrono>
  10. #include <iomanip>
  11. #include <string>    
  12. #include <sstream>   
  13. #include <cmath>     
  14. // U
  15. bool IsFinite(double v) {
  16.     return !std::isnan(v) && !std::isinf(v);
  17. }
  18.  
  19. class ThanosMeanLessMemory {
  20. public:
  21.     // --- int[] ---
  22.     static void ThanosIntSortInPlace(std::vector<int>& a) {
  23.         if (a.empty() || a.size() < 2) return;
  24.         std::vector<int> sorted = SortNoExtraCopy(a);
  25.         a = sorted; // Assign the sorted vector back to a
  26.     }
  27.  
  28. private:
  29.     static std::vector<int> SortNoExtraCopy(std::vector<int> seg) {
  30.         int n = seg.size();
  31.         if (n < 2) return seg;
  32.  
  33.         int mn = seg[0], mx = seg[0];
  34.         long long sum = seg[0];
  35.         for (int i = 1; i < n; i++) {
  36.             int v = seg[i];
  37.             if (v < mn) mn = v;
  38.             if (v > mx) mx = v;
  39.             sum += v;
  40.         }
  41.         if (mn == mx) return seg;
  42.  
  43.         double c = static_cast<double>(sum) / n;
  44.  
  45.         int cntL = 0;
  46.         for (int v : seg) if (v <= c) cntL++;
  47.         int cntR = n - cntL;
  48.  
  49.         std::vector<int> left(cntL);
  50.         std::vector<int> right(cntR);
  51.         int iL = 0, iR = 0;
  52.         for (int v : seg) if (v <= c) left[iL++] = v; else right[iR++] = v;
  53.  
  54.         left = SortNoExtraCopy(left);
  55.         right = SortNoExtraCopy(right);
  56.  
  57.         std::vector<int> outArr(n);
  58.         std::copy(left.begin(), left.end(), outArr.begin());
  59.         std::copy(right.begin(), right.end(), outArr.begin() + left.size());
  60.         return outArr;
  61.     }
  62.  
  63. public:
  64.     // --- double[] ---
  65.     static void ThanosDoubleSortInPlace(std::vector<double>& a) {
  66.         if (a.empty() || a.size() < 2) return;
  67.         std::vector<double> sorted = SortDoubleNoExtraCopy(a);
  68.         a = sorted; // Assign the sorted vector back to a
  69.     }
  70.  
  71. private:
  72.     static std::vector<double> SortDoubleNoExtraCopy(std::vector<double> seg) {
  73.         int n = seg.size();
  74.         if (n < 2) return seg;
  75.  
  76.         bool allSame = true;
  77.         for (int i = 1; i < n; i++) if (seg[i] != seg[0]) { allSame = false; break; }
  78.         if (allSame) return seg;
  79.  
  80.         double sum = 0.0;
  81.         int cntFinite = 0;
  82.         for (double v : seg) if (IsFinite(v)) { sum += v; cntFinite++; }
  83.         if (cntFinite == 0) return seg;
  84.  
  85.         double c = sum / cntFinite;
  86.  
  87.         int cntL = 0;
  88.         for (double v : seg)
  89.             if (std::isinf(v) && v < 0 || (IsFinite(v) && v <= c)) cntL++;
  90.         int cntR = n - cntL;
  91.  
  92.         std::vector<double> left(cntL);
  93.         std::vector<double> right(cntR);
  94.         int iL = 0, iR = 0;
  95.         for (double v : seg)
  96.             if (std::isinf(v) && v < 0 || (IsFinite(v) && v <= c)) left[iL++] = v;
  97.             else right[iR++] = v; // +Infinity и NaN здесь
  98.  
  99.         left = SortDoubleNoExtraCopy(left);
  100.         right = SortDoubleNoExtraCopy(right);
  101.  
  102.         std::vector<double> outArr(n);
  103.         std::copy(left.begin(), left.end(), outArr.begin());
  104.         std::copy(right.begin(), right.end(), outArr.begin() + left.size());
  105.         return outArr;
  106.     }
  107.  
  108. public:
  109.     // --- генераторы ---
  110.     static std::vector<double> GenerateDoubleRandomArray(int n, double min, double max) {
  111.         std::random_device rd;
  112.         std::mt19937 gen(rd());
  113.         std::uniform_real_distribution<> dis(min, max);
  114.  
  115.         std::vector<double> arr(n);
  116.         for (int i = 0; i < n; i++) arr[i] = dis(gen);
  117.         return arr;
  118.     }
  119.  
  120.     static std::vector<int> GenerateRandomArray(int n, int min, int max) {
  121.         std::random_device rd;
  122.         std::mt19937 gen(rd());
  123.         std::uniform_int_distribution<> dis(min, max);
  124.  
  125.         std::vector<int> arr(n);
  126.         for (int i = 0; i < n; i++) arr[i] = dis(gen);
  127.         return arr;
  128.     }
  129. };
  130.  
  131. template <typename T>
  132. std::string Arr(const std::vector<T>& a) {
  133.     std::string result = "[";
  134.     for (size_t i = 0; i < a.size(); ++i) {
  135.         result += std::to_string(a[i]);
  136.         if (i < a.size() - 1) {
  137.             result += ", ";
  138.         }
  139.     }
  140.     result += "]";
  141.     return result;
  142. }
  143.  
  144. int main() {
  145.     // Консоль в UTF-8 (Implementation depends on the OS and compiler, omitted for brevity)
  146.  
  147.     // int
  148.     std::vector<int> arr = ThanosMeanLessMemory::GenerateRandomArray(1000000, 0, 1000000);
  149.     auto tumbler = std::chrono::high_resolution_clock::now();
  150.  
  151.     // 1) Главный тестовый код
  152.     std::vector<int> t1 = arr; // Copy the vector
  153.     std::cout << "start Main test code watch." << std::endl;
  154.     tumbler = std::chrono::high_resolution_clock::now();
  155.     ThanosMeanLessMemory::ThanosIntSortInPlace(t1);
  156.     auto end = std::chrono::high_resolution_clock::now();
  157.     std::cout << "stop watch." << std::endl;
  158.     std::cout << "Thanos main test code : " << std::fixed << std::setprecision(2)
  159.         << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
  160.     std::cout << "_________" << std::endl;
  161.  
  162.     // 2) std::sort (internal)
  163.     std::vector<int> t2 = arr; // Copy the vector
  164.     std::cout << "start internal std::sort code watch." << std::endl;
  165.     tumbler = std::chrono::high_resolution_clock::now();
  166.     std::sort(t2.begin(), t2.end());
  167.     end = std::chrono::high_resolution_clock::now();
  168.     std::cout << "stop watch." << std::endl;
  169.     std::cout << "std::sort , internal     : " << std::fixed << std::setprecision(2)
  170.         << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
  171.     std::cout << "_________" << std::endl;
  172.  
  173.     // double
  174.     std::vector<double> arrD = ThanosMeanLessMemory::GenerateDoubleRandomArray(1000000, 0.0, 1000000.0);
  175.  
  176.     // 1) Главный тестовый код
  177.     std::vector<double> tD1 = arrD; // Copy the vector
  178.     std::cout << "start Main test double code watch." << std::endl;
  179.     tumbler = std::chrono::high_resolution_clock::now();
  180.     ThanosMeanLessMemory::ThanosDoubleSortInPlace(tD1);
  181.     end = std::chrono::high_resolution_clock::now();
  182.     std::cout << "stop watch." << std::endl;
  183.     std::cout << "Thanos main double test code : " << std::fixed << std::setprecision(2)
  184.         << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
  185.     std::cout << "_________" << std::endl;
  186.  
  187.     // 3) std::sort
  188.     std::vector<double> tD3 = arrD; // Copy the vector
  189.     std::cout << "start internal std::sort double code watch." << std::endl;
  190.     tumbler = std::chrono::high_resolution_clock::now();
  191.     std::sort(tD3.begin(), tD3.end());
  192.     end = std::chrono::high_resolution_clock::now();
  193.     std::cout << "stop watch." << std::endl;
  194.     std::cout << "std::sort , double internal     : " << std::fixed << std::setprecision(2)
  195.         << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
  196.     std::cout << "_________" << std::endl;
  197.  
  198.     return 0;
  199. }
  200.  
Success #stdin #stdout 1.33s 70804KB
comments (?)
stdin 
Standard input is empty
stdout 
start Main test code watch.
stop watch.
Thanos main test code : 423.57 ms
_________
start internal std::sort code watch.
stop watch.
std::sort , internal     : 88.74 ms
_________
start Main test double code watch.
stop watch.
Thanos main double test code : 654.86 ms
_________
start internal std::sort double code watch.
stop watch.
std::sort , double internal     : 100.05 ms
_________
https://ideone.com/jf0e8x
language:
C++ (gcc 8.3)
created:
100 days ago
visibility:
secret

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!