Jak zoptymalizować wypisywanie różnicy między większą a mniejszą z dwóch liczb?

UVA problem nr 10055, „Hashmat the Brave Warrior”, chyba ich najłatwiejsze zadanie. Input składa się z par liczb w zakresie od 0 do 2^32 włącznie, więc może mieć sens użycie liczb 64bitowych. Dla każdej pary należy wypisać różnicę między większą a mniejszą z tych liczb.

Według ich statystyk najszybsze rozwiązania lecą w czasie poniżej 0.01 sek. Niestety wszystkie moje próby rozwiązania zadania zazwyczaj lecą w 0.02 sek, chyba losowo wahając się czasem w zakresie ± 0.01.sek.

Próbowałem:

#include <cstdint>
#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  

  uint_fast64_t i, j;
  while(cin >> i >> j) {
    if(i > j)
      cout << i-j << '\n';
    else
      cout << j-i << '\n';
  }
}

A także:

#include <cstdlib>
#include <cstdint>
#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  

  int_fast64_t i, j;
  while(cin >> i >> j) {
    cout << abs(i-j) << '\n';
  }
}

I jeszcze:

#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  

  uint_fast64_t i, j;
  while(cin >> i >> j) {
    cout << max(i,j)-min(i,j) << '\n';
  }
}

Ciągle z tym samym rezultatem.

Próbowałem też używać printf()/scanf() zamiast cin/cout, wciąż z tym samym rezultatem (skądinąd moje benchmarki wskazują, że cin/cout poprzedzony cin.tie(nullptr) może być nawet nieco szybszy niż printf()/scanf() – przynajmniej o ile nie ma jakiś nieznanych mi sposobów na optymalizację cstdio).

Czy jest jakiś sposób na ściągnięcie tego do czasu poniżej 0.01 sek., czy mam założyć że ci, którzy to osiągnęli, albo mieli nieprawdopodobnego farta albo są cziterami, którzy wypisują uprzednio wyliczoną odpowiedź na input sprawdzarki?

Programy są kompilowane z C++11 5.3.0 - GNU C++ Compiler with options: -lm -lcrypt -O2 -std=c++11 -pipe -DONLINE_JUDGE.

Skąd wziąłeś abs w obliczaniach wyniku?
W treści stoi jak byk:

Hashmat's soldier number is never greater than his opponent.

Jak wywalisz abs (i pochodne) to powinno dać upragniony wynik.

Zgaduje, że najpierw drukowałeś i-j a nie rozumiejąc co robisz źle dodałeś abs i wtedy przeszło przez testy.

Kolejna możliwość to nie używać uint_fast64_t, to będzie szybkie tylko dla 64 bitowej maszynie na 32 bitowej nie da to oczekiwanego zysku

Twój kod poprawiony o jedno słowo

#include <cstdint>
#include <iostream>
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  
 
  uint32_t i, j;
  while(cin >> i >> j) {
    if(i > j)
      cout << i-j << '\n';
    else
      cout << j-i << '\n';
  }
  return 0;
}

@MarekR22:

Niestety znowu nie :( Raz: tak jak pisałem, liczby MOGĄ dochodzić do 2^32, czyli o 1 poza zakres uint32_t. Przy odrobinie uporu da się to naprawić ifologią co prawda:

#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  

  uint32_t i, j;
  while(!(cin >> i).eof()) {
    if(cin.fail()) { // 2^32 read
      cin.clear();
      cin >> j;
      if(cin.fail()) {
        cin.clear();
        cout << 0 << '\n';
        continue;
      } else if(j == 0) {
        cout << 4294967296 << '\n';
        continue;
      } else {
        j--; // C++11 mandates in case of overflow i has value of UINT32_MAX
      }      // which equals 2^32-1
    }
    cin >> j;
    if(cin.fail()) {
      cin.clear();
      if(i == 0) {
        cout << 4294967296 << '\n';
        continue;
      } else {
        i--;
      }
    }
    cout << max(i,j)-min(i,j) << '\n';
  }
}

Ale to wciąż idzie w 0.02sek.

Dwa: Upewniłem się: na sprawdzarce zachodzi std::is_same<std::uint_fast32_t, std::uint_fast64_t>::value == true. Co oznacza, że chyba nie powinno być różnicy w wydajności między liczbami 32bitowymi a 64bitowymi, popraw mnie, jeśli się mylę.

Spróbuj scanf: https://www.hackerearth.com/practice/notes/fast-io-optimization-in-c/
i fastscan z: http://www.geeksforgeeks.org/fast-io-for-competitive-programming/

@vpiotr:

#include <cstdint>
#include <cstdio>
#include <cinttypes>
using namespace std;

    bool fastscan(uint_fast64_t &x, uint_fast64_t &y)
    {
        int c = 0;
        x = y = 0;
        for(;!(c>47 && c<58 || c == EOF);c=getchar());
        if(c == EOF) return false;
        do {
          x = (x<<1) + (x<<3) + c - 48;
          c = getchar();
        } while(c>47 && c<58);
        for(;!(c>47 && c<58 || c == EOF);c=getchar());
        do {
          y = (y<<1) + (y<<3) + c - 48;
          c = getchar();
        } while(c>47 && c<58);
    }

int main()
{  
  uint_fast64_t i, j;
  while(fastscan(i, j)) {
    if(i > j)
      printf("%" PRIuFAST64 "\n", i-j);
    else
      printf("%" PRIuFAST64 "\n", j-i);
  }
}

Wciąż 0.02 sek.

Wygłupiłem się jeszcze z czymś takim:

#include <cstdint>
#include <iostream>
#include <sstream>
using namespace std;

istream& fastscan(istream &is, uint_fast64_t &i, uint_fast64_t &j)
{
  i = j = 0;
  char c;
  while(!(is.get(c).eof()) && !(c >= '0' && c <= '9'));
  if(is.eof()) return is;
  do {
    i = 10 * i + (c - '0');
    is.get(c);
  } while(c >= '0' && c <= '9');
  do {
    is.get(c);
  } while(!(c >= '0' && c <= '9'));
  do {
    j = 10 * j + (c - '0');
    is.get(c);
  } while(c >= '0' && c <= '9');
  return is;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  
  
  uint_fast64_t i, j;
  stringstream inp;
  inp << cin.rdbuf();
  stringstream outp;
  while(fastscan(inp, i, j)) {
    if(i > j)
      outp << i-j << '\n';
    else
      outp << j-i << '\n';
  }
  cout << outp.rdbuf();
}

To samo.

A zwykły scanf / printf ?
Spróbuj w ogóle pominąć iostreams, czyli także:

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);  

@vpiotr:

Tego też próbowałem:

#include <cstdint>
#include <cstdio>
#include <cinttypes>
using namespace std;

int main()
{ 
  uint_fast64_t i, j;
  while(scanf("%" SCNuFAST64 "%" SCNuFAST64, &i, &j) == 2) {
    if(i > j)
      printf("%" PRIuFAST64 "\n", i-j);
    else
      printf("%" PRIuFAST64 "\n", j-i);
  }
}

Jedynie co jeszcze mi przychodzi do głowy to napisać branchless abs

template<typename T>
auto BranchlessAbs(T x) -> T
{
    static_assert(std::is_signed<T>::value, "Only for signed values");
    T const mask = x >> (sizeof(T) * CHAR_BIT - 1);
    return (x + mask) ^ mask;
}

Albo oszustwo w postaci twardo wpisanych wyników.

To są bardzo małe czasy jak na testy wydajnościowe. Być może C++ się rozkręca tam gdzie już powinien kończyć i wcale to nie Twój kod tyle trwa.
Przy większych zbiorach wejściowych pewnie większość tych wersji by przeszła. A jesteś pewny że wyniki są poprawne?

sprobuj z fread/fgetc unlocked

@katelx:

No to na razie mam coś takiego:

#include <stdio.h>
#include <stdint.h>

unsigned long long divisors[] = {
  1000000000,
  1000000000,
  1000000000,
  1000000000,
  100000000,
  100000000,
  100000000,
  10000000,
  10000000,
  10000000,
  1000000,
  1000000,
  1000000,
  1000000,
  100000,
  100000,
  100000,
  10000,
  10000,
  10000,
  1000,
  1000,
  1000,
  1000,
  100,
  100,
  100,
  10,
  10,
  10,
  1,
  1,
  1
};
  

int main()
{
  unsigned long long int i, j, res;
  
  unsigned char inbuff[2500000]; /* To be certain there's no overflow here */
  unsigned char *in = inbuff;
  char outbuff[2500000]; /* To be certain there's no overflow here */
  char *out = outbuff;
  
  int c = 0;
  
  while(1) {
    i = j = 0;
    
    inbuff[fread_unlocked(inbuff, 1, 2500000, stdin)] = '\0';
    
    /* Skip whitespace before first number and check if end of input */
    do {
      c = *(in++);
    } while(c != '\0' && !(c >= '0' && c <= '9'));
    
    /* If end of input, print answer and return */
    if(c == '\0') {
      *(--out) = '\0';
      puts(outbuff);
      return 0;
    }
    
    /* Read first integer */
    do {
      i = 10 * i + (c - '0');
      c = *(in++);
    } while(c >= '0' && c <= '9');
    
    /* Skip whitespace between first and second integer */
    do {
      c = *(in++);
    } while(!(c >= '0' && c <= '9'));
    
    /* Read second integer */
    do {
      j = 10 * j + (c - '0');
      c = *(in++);
    } while(c >= '0' && c <= '9');
    
    if(i > j)
      res = i-j;
    else
      res = j-i;
    
    
    
    /* Buffer answer */
    if(res == 0) {
      *(out++) = '0';
    } else {
      unsigned long long divisor = divisors[__builtin_clzll(res)-31];
      /* Skip trailing 0 */
      if(res < divisor) {
        divisor /= 10;
      }
      /* Buffer digits */
      while(divisor != 0) {
        unsigned long long digit = res / divisor;
        *(out++) = digit + '0';
        res -= divisor * digit;
        divisor /= 10;
      }
    }
    *(out++) = '\n';
  }
}

Koszmarek… ale działa wciąż w 0.02 sek.

po zmianie na fgetc_unlocked mam 0.01 :)

#include <stdio.h>
#include <stdint.h>

unsigned long long divisors[] = {
 1000000000,
 1000000000,
 1000000000,
 1000000000,
 100000000,
 100000000,
 100000000,
 10000000,
 10000000,
 10000000,
 1000000,
 1000000,
 1000000,
 1000000,
 100000,
 100000,
 100000,
 10000,
 10000,
 10000,
 1000,
 1000,
 1000,
 1000,
 100,
 100,
 100,
 10,
 10,
 10,
 1,
 1,
 1
};

int main()
{
 unsigned long long int i, j, res;

 char outbuff[2500000]; /* To be certain there's no overflow here */
 char *out = outbuff;

 int c = 0;

 while(1) {
   i = j = 0;

   /* Skip whitespace before first number and check if end of input */
   do {
     c = fgetc_unlocked(stdin);
   } while(c != EOF && !(c >= '0' && c <= '9'));

   /* If end of input, print answer and return */
   if(c == EOF) {
     *(--out) = '\0';
     puts(outbuff);
     return 0;
   }

   /* Read first integer */
   do {
     i = 10 * i + (c - '0');
     c = fgetc_unlocked(stdin);
   } while(c >= '0' && c <= '9');

   /* Skip whitespace between first and second integer */
   do {
     c = fgetc_unlocked(stdin);
   } while(!(c >= '0' && c <= '9'));

   /* Read second integer */
   do {
     j = 10 * j + (c - '0');
     c = fgetc_unlocked(stdin);
   } while(c >= '0' && c <= '9');

   if(i > j)
     res = i-j;
   else
     res = j-i;

   /* Buffer answer */
   if(res == 0) {
     *(out++) = '0';
   } else {
     unsigned long long divisor = divisors[__builtin_clzll(res)-31];
     /* Skip trailing 0 */
     if(res < divisor) {
       divisor /= 10;
     }
     /* Buffer digits */
     while(divisor != 0) {
       unsigned long long digit = res / divisor;
       *(out++) = digit + '0';
       res -= divisor * digit;
       divisor /= 10;
     }
   }
   *(out++) = '\n';
 }
}

0.00 po dodaniu fputc_unlocked

#include <stdio.h>

int main()
{
    unsigned long long int i, j, res;

    char outbuff[20];
    int out;

    int c = 0;

    while (1) {
        i = j = 0;

        /* Skip whitespace before first number and check if end of input */
        do {
            c = fgetc_unlocked(stdin);
        } while (c != EOF && !(c >= '0' && c <= '9'));

        /* If end of input, print answer and return */
        if (c == EOF) {
            return 0;
        }

        /* Read first integer */
        do {
            i = 10 * i + (c - '0');
            c = fgetc_unlocked(stdin);
        } while (c >= '0' && c <= '9');

        /* Skip whitespace between first and second integer */
        do {
            c = fgetc_unlocked(stdin);
        } while (!(c >= '0' && c <= '9'));

        /* Read second integer */
        do {
            j = 10 * j + (c - '0');
            c = fgetc_unlocked(stdin);
        } while (c >= '0' && c <= '9');

        if (i > j)
            res = i - j;
        else
            res = j - i;

        if (res == 0) {
            fputc_unlocked('0', stdout);
        }
        else {
            out = 0;
            while (res) {
                outbuff[out++] = res % 10 + '0';
                res /= 10;
            }
            while (out)
                fputc_unlocked(outbuff[--out], stdout);
        }
        fputc_unlocked('\n', stdout);
    }
}