Volevo provare la piattaforma e per iniziare con una bella sfida ho preso quello che veniva considerato il piu’ “hard” tra i problemi. Mi ha dato filo da torcere ma alla fine sono riuscito nell’intento di risolverlo (anche se non sono riuscito ad arrivare -perlomeno ancora- ai tempi dei primi).
Quello che pero’ ho notato nell’utilizzo della piattaforma e’ che alcune soluzioni che funzionavano in locale non funzionavano piu’ correttamente in remoto in funzione ad esempio della lunghezza di un buffer, oppure la soluzione che in locale ho misurato piu’ veloce alla fine non lo e’ stata su olinfo.
Per cercare di preparare meglio le soluzioni desideravo sapere come poter replicare al meglio le condizioni di test remoto in locale, come ad esempio con quali parametri viene compilato il programma, che librerie vengono linkate, come viene eseguito, etc.
Il grader che trovi tra gli allegati del problema viene dato per aiutarti a testare la tua soluzione in locale ma non è necessariamente quello che viene usato per valutare la tua soluzione. Quest’ultimo, a volte, può contenere molta più logica per poter garantire che le soluzioni prendano tutti e soli i punti che debbano prendere. Ciò, di contro, può causare che il tuo programma si comporti in modo leggermente diverso sul server rispetto che in locale.
In particolare, nel task bigsomma il file di input non è un file regolare e perciò alcune funzioni come fstat o mmap non funzionano.
Nel problema in questione il file e’ chiaramente stdin, ma il problema che ponevo e’ diverso e piu’ generale.
Immagino che la piattaforma utilizzata sia Linux, e GNU G++ il compilatore ma ci sarebbero molte altre scelte (in particolare sul compilatore, come ad esempio clang/LLVM, o il bellissimo tcc). Inoltre anche a parita’ di compilatore solitamente vi sono una moltitudine di parametri utilizzabili.
E questo senza arrivare alle librerie, come ad esempio la musl, o all’ambiente di esecuzione, con la sua tipologia di processore, etc…
Secondo me queste informazioni dovrebbero essere rese pubbliche, per fare in modo che uno non utilizzi la piattaforma per fare i benchmarks ma solo per sottomettere le soluzioni gia’ provate e confrontate in locale!
Non c’è molto da dire a riguardo, il server non ha niente di speciale. Le sottoposizioni vengono compilate con GCC 7.3 in ambiente Linux e le uniche flag utilizzate sono -O2 e -std=gnu++11, non vengono usate librerie eccetto che per quella standard.
Ma comunque considera che bigsomma è un task abbastanza diverso dagli altri task che trovi nella piattaforma. Nella maggior parte dei casi ti basta trovare una soluzione che abbia la complessità giusta senza preoccuparti di doverla ottimizzare pesantemente.
No, non puoi usare fork e non puoi creare nuovi processi (e non vedo nemmeno il motivo per cui dovresti farlo). Credo che sia possibile creare nuovi thread ma comunque il tempo di ogni thread viene sommato per cui è abbastanza inutile.
Comunque in generale non dovresti mai usare nessuna syscall direttamente ma piuttosto affidarti alle funzioni della libreria standard.
Sono abbastanza d’accordo. Magari toglierlo del tutto è un po’ drastico, ma farlo finire a pagina 47428 e mettere un bel disclaimer all’inizio può essere una soluzione. C’è una percentuale spropositatamente alta di thread su questo forum che si riferiscono a bigsomma, e onestamente non capisco perché abbia tanto (sex?) appeal. Anzi, mi vengono in mente due motivi (non mutualmente esclusivi):
È un task particolare, e pertanto genera curiosità.
La piattaforma è frequentata principalmente da “informatici” piuttosto che da “computer scientists”.
Secondo me la seconda è quella predominante, che è un po’ un peccato. Comunque non è questo il posto per discuterne.
Concludo invitando tutti a non sprecare troppo tempo pensando seriamente a bigsomma (ovvero: ci sta lavorarci a tempo perso per divertimento, ma farlo pensando che possa essere un allenamento efficace per le olimpiadi, o che questo tipo di ottimizzazioni possano risultare utili nelle gare, è da evitare).
Personalmente mi ritengo sia un “informatico” che un “computer scientist”
Il task in questione richiede comunque sia una soluzione efficace da un punto di vista di lettura disco (informatica), anche se devo dire che con tutte le prove non sono riuscito a trovarne una molto diversa da quella abbastanza standard, ma anche ed a questo punto soprattutto nel mio caso, un algoritmo e delle strutture dati efficaci a minimizzare i calcoli necessari.
Nonostante la mia esperienza devo dire comunque che ho approfondito ed imparato parecchie cose nuove nel processo (ad esempio la modalita’ di gestione dei memory mapped files da parte del kernel anche se non sono riuscito ad usarla), cosa che a priori non mi sarei aspettato.
Questo non toglie che non sia esattamente un task tipico da olimpiadi, e speravo che fosse sufficientemente chiaro dall’impostazione del testo e dal tag “extreme optimization” – evidentemente no, quindi forse è meglio modificarlo un po’
