Aiuto Trova il massimo (fast input)

Aiuto
1

Sto cercando di risolvere il problema Trova il massimo, che richiede di fare input di numeri in modo velocissimo.
Ma per quanto sono riuscito a vedere, la performance richiesta è irraggiungibile. Solo due persone hanno risolto il problema (tra l’altro uno con 0.005 sec, wtf?) e io non sono riuscito ad andare oltre la subtask 4.
Solo leggere tutte le cifre dei numeri (senza convertirle in decimale o farci nient’altro) fa andare il mio programma in timeout. Allego il codice che ho usato sotto:

#include <iostream>

using namespace std;

// _getchar_nolock funziona su windows, getchar_unlocked su linux. non sapendo cosa funziona sul server ho lasciato la possibilità di usare entrambi
#ifndef WIN32
#define _getchar_nolock getchar_unlocked
#define _putchar_nolock putchar_unlocked
#endif

#pragma GCC diagnostic warning "-Wall"
__attribute__((flatten))
int main() {
    // disattiva tutte le sincronizzazioni fra gli stream di input/output
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    register int N;
    register char input;
    N = 0;
    input = _getchar_nolock();
    do {
        N = (N<<1) + (N << 3) + input - '0';
        input = _getchar_nolock();
    } while (input != '\n');
    N--;
    while (N--) {
        // controllo solo se il carattere è uno spazio per ottimizzare
        do {} while (_getchar_nolock() !=' ');
    }
    // l'ultimo numero non finisce con uno spazio ma con un a capo
    do {} while (_getchar_nolock() != '\n');
    return 0;
}

Qualcuno (in particolare chi l’ha fatto) sa spiegarmi come va risolto il problema, ho almeno darmi qualche indicazione su cosa sto sbagliando?

2

Dato che questo problema è essenzialmente una competizione per chi ha l’input più veloce, dubito che nessuno che l’ha risolto ti sveli i suoi segreti.

In ogni caso ti posso dare qualche commento sul tuo codice:

  • register è una keywork deprecata quindi evita di usarlo;
  • scrivere (x<<1)+(x<<3) è inutile e rende solo il codice più difficile da leggere. L’assembly che viene generato scrivendo 10*x oppure (x<<1)+(x<<3) non solo è identico, ma lo shift non viene nemmeno usato;
  • usare ios_base::sync_with_stdio(false) può senz’altro farti guadagnare un po’ di tempo quando usi cin e cout ma in questo caso non li usi quindi è abbastanza inutile quella parte;
  • potrai aver già intuito che la parte lenta del tuo codice è getchar_unlocked. Prova a dare un’occhiata alle system call di linux e vedi se trovi qualche alternativa
3

Il mio codice presenta 2 ottimizzazioni principali:

  1. L’utilizzo della funzione mmap (presente solo sui sistemi unix) per la lettura dell’input
  2. L’utilizzo di un formato alternativo che mi permetta di parsare e confrontare i numeri più efficientemente rispetto alla rappresentazione classica degli interi
1 Mi Piace
4

Grazie a entrambi per le risposte. Implementerò tutti i consigli che mi avete dato (specialmente la rappresentazione alternativa dei numeri, che stavo per provare prima di rendermi conto che non avrebbe funzionato in ogni caso).
Ho una sola domanda: mmap non ha nessun equivalente in windows? Ossia, non potrò testare le soluzioni in locale sul mio pc?

5

Ti consiglio di incapsulare la chiamata a mmap in una funzione e se su Windows simularne l’effetto con un implementazione alternativa.

Un abbozzo di implementazione:

#ifdef WIN32

char const *mmap_input() {
    // implementazione per Windows
}

#else

char const *mmap_input() {
    return mmap(...);
}

#endif
6

Si fa complicato… proverò. Grazie

7

Abbiamo tolto il problema, ma l’abbiamo sostituito con CMSocial - a social coding app - buon divertimento!

8

Bene…

… ma non benissimo.

3 Mi Piace