Ingresso/uscita veloce nella programmazione competitiva

Question

Ho incontrato questo particolare snippet di codice molte volte in soluzioni di concorsi di programmazione competitivi. Capisco l'uso di base di questo codice per superare i limiti di tempo ma voglio capirlo più profondamente. So che unistd.h dà accesso alle funzioni di call wrapper di sistema come fork, pipe e primitive di I/O (read, write, ..).

Sarà anche bello se qualcuno può spiegarmi o guidarmi a risorse che possono aiutarmi a capirlo ulteriormente.

#include <stdlib.h> 
#include <stdint.h> 
#include <unistd.h> 
class FastInput { 
public: 
    FastInput() { 
     m_dataOffset = 0; 
     m_dataSize = 0; 
     m_v = 0x80000000; 
    } 
    uint32_t ReadNext() { 
     if (m_dataOffset == m_dataSize) { 
      int r = read(0, m_buffer, sizeof(m_buffer)); 
      if (r <= 0) return m_v; 
      m_dataOffset = 0; 
      m_dataSize = 0; 
      int i = 0; 
      if (m_buffer[0] < '0') { 
       if (m_v != 0x80000000) { 
        m_data[m_dataSize++] = m_v; 
        m_v = 0x80000000; 
       } 
       for (; (i < r) && (m_buffer[i] < '0'); ++i); 
      } 
      for (; i < r;) { 
       if (m_buffer[i] >= '0') { 
        m_v = m_v * 10 + m_buffer[i] - 48; 
        ++i; 
       } else { 
        m_data[m_dataSize++] = m_v; 
        m_v = 0x80000000; 
        for (i = i + 1; (i < r) && (m_buffer[i] < '0'); ++i); 
       } 
      } 
     } 
     return m_data[m_dataOffset++]; 
    } 
public: 
    uint8_t m_buffer[32768]; 
    uint32_t m_data[16384]; 
    size_t m_dataOffset, m_dataSize; 
    uint32_t m_v; 
}; 
class FastOutput { 
public: 
    FastOutput() { 
     m_dataOffset = 0; 
    } 
    ~FastOutput() { 
    } 
    void Flush() { 
     if (m_dataOffset) { 
      if (write(1, m_data, m_dataOffset)); 
      m_dataOffset = 0; 
     } 
    } 
    void PrintUint(uint32_t v, char d) { 
     if (m_dataOffset + 11 > sizeof(m_data)) Flush(); 
     if (v < 100000) { 
      if (v < 1000) { 
       if (v < 10) { 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 1; 
       } else if (v < 100) { 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 2; 
       } else { 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 3; 
       } 
      } else { 
       if (v < 10000) { 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 4; 
       } else { 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 5; 
       } 
      } 
     } else { 
      if (v < 100000000) { 
       if (v < 1000000) { 
        m_data[m_dataOffset + 5] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 6; 
       } else if (v < 10000000) { 
        m_data[m_dataOffset + 6] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 5] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 7; 
       } else { 
        m_data[m_dataOffset + 7] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 6] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 5] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 8; 
       } 
      } else { 
       if (v < 1000000000) { 
        m_data[m_dataOffset + 8] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 7] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 6] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 5] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 9; 
       } else { 
        m_data[m_dataOffset + 9] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 8] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 7] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 6] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 5] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 4] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 3] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 2] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 1] = v - v/10 * 10 + 48; 
        v /= 10; 
        m_data[m_dataOffset + 0] = v + 48; 
        m_dataOffset += 10; 
       } 
      } 
     } 
     m_data[m_dataOffset++] = d; 
    } 
    void PrintChar(char d) { 
     if (m_dataOffset + 1 > sizeof(m_data)) Flush(); 
     m_data[m_dataOffset++] = d; 
    } 
    void ReplaceChar(int offset, char d) { 
     m_data[m_dataOffset + offset] = d; 
    } 
public: 
    uint8_t m_data[32768]; 
    size_t m_dataOffset; 
}; 

Un'altra cosa: è buona pratica impiegare tecniche simili nel codice del livello di produzione?

Answer 1

È buona pratica impiegare tecniche simili nel codice del livello di produzione?

No. Il reimplementing della ruota causa errori. I bug richiedono tempi di sviluppo e costi aggiuntivi.

può aiutarmi a capirlo ulteriormente.

Se non si capisce il codice, il codice è scritto male. Il codice è scritto dagli umani e per gli umani. Se un altro programmatore non capisce rapidamente il codice, potrebbe esserci un grosso problema.La logica alla base di questo pensiero ("scritto per gli umani") è semplice: il tempo di sviluppo costa molto e il codice illeggibile aumenta i tempi di sviluppo.

Il frammento di codice in questione utilizza diversi pratiche di codifica cattive:

1. notazione ungherese (non c'è bisogno di questo in notazione maiuscole e minuscole e soprattutto in C++),
2. brevi membri variabili (si può dire ciò significa m_v senza leggere il resto del programma, per esempio?)
3. valori hard-coded (+ 48, + 11)
4. (soggettiva) Miscele firmato/unsigned int/caratteri (minGW/wil gcc ti annoio fuori di testa mentre compili).
5. Codice copia-incolla (v /= 10 e simili - C++ ha macro/modelli, dannazione, quindi se si desidera srotolare il ciclo a mano, usarli!).
6. Inevitabilmente multilivello se/else.

A meno che non si desideri peggiorare la programmazione, consiglierei di evitare di cercare di "capire" questo frammento di codice. È cattivo.

Dubito seriamente che questo particolare progetto sia stato il risultato della profilatura. Molto probabilmente uno scenario "geniale" presuppone che il suo frammento di codice supererà le funzioni integrate.

Quando si desidera prestazioni, si segue questo modello:

1. Scrivi versione iniziale.
2. Ripetere l'operazione fino guadagno di prestazioni non è più vale la pena o fino a quando non c'è una soluzione:
   1. Non fare molte ipotesi su ciò che migliorerà le prestazioni. Sei umano, il lavoro dell'uomo è commettere errori. Secondo la legge di Murphy, le tue supposizioni saranno errate.
   2. Considerare prima l'ottimizzazione algoritmica.
   3. Eseguire il codice tramite profiler.
   4. Individuare i colli di bottiglia.
   5. Indagare sul guadagno di prestazione totale se il tempo totale trascorso in questa particolare routine verrà ridotto a zero.
   6. Se il guadagno è ragionevole (tempo/costo), ottimizzare la routine. Altrimenti ignora.

Answer 2

Nella funzione PrintUint, in pratica sta semplicemente srotolando un ciclo a mano. A volte i loop di svolgimento sono una buona cosa da fare - tuttavia il compilatore lo fa già, e lo farà meglio di te, il più delle volte.

di collegare la mia caratteristica lingua preferita, sarebbe meglio implementata utilizzando i modelli: una semplice implementazione (più intelligente probabilmente esiste) sarebbe simile:

// I'm sure the compiler can figure out the inline part, but I'll add it anyways 
template<unsigned int N> 
inline void print_uint_inner(uint32_t v) { 
    m_data[m_dataOffset + N] = v - v/10 * 10 + 48; 
    print_uint_inner<N-1>(v/10); 
} 

// For situations just like this, there's a trick to avoid having to define the base case separately. 
inline void print_uint_inner<0>(uint32_t v) { 
    m_data[m_dataOffset] = v - v/10 * 10 + 48; 
} 

template<unsigned int N> 
inline void print_uint_helper(uint32_t v) { 
    print_uint_inner<N-1>(v); 
    m_dataOffset += N; 
} 

// We could generate the compile-time binary search with templates too, rather than by hand. 
void PrintUint(uint32_t v, char d) { 
    if (m_dataOffset + 11 > sizeof(m_data)) Flush(); 
    if (v < 100000) { 
     if (v < 1000) { 
      if (v < 10) { 
       print_uint_helper<1>(v); 
      } else if (v < 100) { 
       print_uint_helper<2>(v); 
      } else { 
       print_uint_helper<3>(v); 
      } 
     } else { 
      if (v < 10000) { 
       print_uint_helper<4>(v); 
      } else { 
       print_uint_helper<5>(v); 
      } 
     } 
    } else { 
     if (v < 100000000) { 
      if (v < 1000000) { 
       print_uint_helper<6>(v); 
      } else if (v < 10000000) { 
       print_uint_helper<7>(v); 
      } else { 
       print_uint_helper<8>(v); 
      } 
     } else { 
      if (v < 1000000000) { 
       print_uint_helper<9>(v); 
      } else { 
       print_uint_helper<10>(v); 
      } 
     } 
    } 
    m_data[m_dataOffset++] = d; 
} 

sta facendo cose come questa buona pratica di codifica in generale? Sì, ma solo se sono soddisfatti tutti i seguenti criteri:

• Hai già scritto la versione semplice, ovvia e comprensibile.
• quali hai profilate il vostro programma, in modo da sapere questo tratto di codice sta costando il tempo sufficiente per essere vale la pena
• Siete disposti a passare attraverso il lavoro supplementare per assicurare la versione più complessa è in realtà corretto
• Hai profilato il programma aggiornato, in modo che tu sappia che la riscrittura ha effettivamente migliorato il tuo tempo di esecuzione.

Inoltre, si dovrebbe probabilmente mantenere la possibilità di tornare alla versione semplice, utilizzando costanti in fase di compilazione o direttive pre-processore. Questo sarà importante per due motivi:

• Quando sei il debug, la possibilità di tornare alla versione semplice contribuirà a limitare i luoghi in cui ci potrebbero essere problemi
• quando si tenta in esecuzione su un diverso computer (o anche lo stesso computer in condizioni diverse), è possibile che la versione complicata non sia più veloce della versione semplice.

Answer 3

provare questo per I più veloce/O

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

Imposta se i flussi C++ standard sono sincronizzati con i flussi C standard dopo ogni operazione di input/output. Per impostazione predefinita, gli oggetti iostream e i flussi cstdio sono sincronizzati.