Send a PR on GitHub

progintro @ dit

</img>

trolley

</div

Το trolley είναι ένα μικρό πρόγραμμα αυτόματου πιλότου διαμοφωμένο έτσι ώστε να μπορεί να δώσει μια αντικειμενική λύση σε τυχόν καταστάσεις παρόμοιες με το ομώνυμο ερώτημα που ταλανίζει φιλόσοφους κάθε ηλικίας εδώ και πολλές γενιές. Εμποτισμένο με την Σύγχρονη Τεχνολογία Επίλυσης Φιλοσοφικών Ζητημάτων™, αυτό το πρόγραμμα παίρνει το βάρος μιας τέτοιας απόφασης επάνω του και αφήνει τον οδηγό να χρησιμοποιήσει τον πολύτιμο χρόνο του πιο παραγωγικά. Για να αναρωτηθεί, για παράδειγμα, για ποιον ακριβώς λόγο δεν λειτουργούν τα φρένα του οχήματός του.

Usage

Το πρόγραμμα μπορεί να τρέξει ο οδηγός όταν ξεκινήσει το δρομολόγιό του και να to κρατήσει ανοιχτό και να το χρησιμοποιήσει αν ή όταν προκύψει μια τέτοια κατάσταση. Δεν δέχεται κανένα όρισμα. Κάθε είσοδος στο πρόγραμμα γίνεται μέσω του standard input.

Building

make

$ make

Μπορούμε επίσης να δώσουμε την μεταβλητή CFLAGS για να περάσουμε επιπλέον σημαίες στον compiler, τον οποίον μπορούμε και αυτόν να εναλλάξουμε με την μεταβλητή CC.

$ make CC=clang CFLAGS="-static"

Όσο γράφουμε κώδικα είναι χρήσιμο να βλέπουμε αμέσως τα λάθη στο πρόγραμμα. Αν δεν έχουμε κάποιο LSP όπως το clangd, μπορούμε να χρησιμοποιήσουμε make watch που θα τρέχε make build κάθε φορά που αλλάζει ο πηγαίος κώδικας. (Απαιτεί την ύπαρξη των εργαλείων inotify-tools).

manually

$ gcc src/trolley.c -o trolley

nix

$ nix build

Testing

Χρησιμοποιώντας ένα ειδικά γραμμένο πρόγραμμα, test.py, μπορούμε να περάσουμε πολλές εισόδους και να τσεκάρουμε ότι κάθε απόφαση που παίρνει ο αυτόματος πιλότος είναι σωστή.

$ python test.py -e ./trolley tests/benchmark_10000_1

Στο test.py δίνουμε το μονοπάτι στο εκτελέσιμο πρόγραμμα του trolley και ένα ή περισσότερα άρχεια που περιέχουν τις εισόδους. Τέτοια αρχεία είναι το benchmark_10000_1 και benchmark_10000_2, που βρίσκονται στο φάκελο tests/. Αυτά τα αρχεία περιέχουν διάφορες περιπτώσεις εισόδων και το αναμενόμενο αποτέλεσμα στo format:

{left cost} {right cost} {direction}

Όπου left cost και right cost είναι οι 2 είσοδοι του προγράμματος και direction είναι είτε “left” είτε “right”. Το test.py θα φορτώσει όλες αυτές τις περιπτώσεις και θα τις τρέξει, χρονομετρώντας την εκτέλεση του προγράμματος με ακρίβεια nanosecond. Στο τέλος θα ελέγξει ότι το πρόγραμμα για κάθε περίπτωση πήρε την σωστή απόφαση με βάση το direction της κάθε περίπτωσης.

Για την δημιουργία των tests/benchmark_10000_* χρησιμοποιήθηκε το πρόγραμμα tests/gen_vectors.py.

Performance

[!NOTE] Όλα τα παρακάτω benchmarks έχουν χρονομετρηθεί στο linux24 χωρίς κανέναν άλλον χρήστη ενεργό.

Τα αρχεία tests/benchmark_10000_* περιέχουν το καθένα 10000 τυχαίες περιπτώσεις εισόδων. Χρησιμοποιώντας το test.py μπορούμε να χρονομετρήσουμε, με αποδεκτή ακρίβεια, τον χρόνο εκτέλεσης του trolley.

benchmark

Αν δεν θέλουμε να χρησιμοποιήσουμε το test.py, μπορούμε να χρονομετρήσουμε το trolley πάνω στις ίδιες περιπτώσεις όπως πριν με μια δημιουργική χρήση του awk.

$ awk '!/^#/ {print $1, $2}' tests/benchmark_10000_1 | /usr/bin/time -p ./trolley

Για να αποφύγουμε, όσο γίνεται, να μετράμε την καθυστέρηση της εκτύπωσης στην οθόνη μπορούμε να χρησιμοποιήσουμε:

$ awk '!/^#/ {print $1, $2}' tests/benchmark_10000_1 | /usr/bin/time -p ./trolley >/dev/null

benchmark-time

Observations

Data types

Σύμφωνα με την εκφώνηση:

Όλα τα κόστη που θα δοθούν στο πρόγραμμά σας θα είναι δεκαδικοί ακέραιοι στο εύρος: −10^18 έως 10^18.

Αυτό το εύρος ακέραιων τιμών είναι αναπαραστήσιμο από προσημασμένους ακέραιους αριθμούς των 61 bit και πάνω. Το κοντινότερο μέγεθος ακεραίου που έχουμε στην C είναι οι int64_t. Για αυτό το λόγο τα κόστη εσωτερικά αναπαρίστανται από int64_t.

Errors

Φαίνεται ότι στα μηχανήματα του εργαστηρίου το gcc, όταν χρησιμοποιείται με την σημαία -m32 δεν βρίσκει το asm/errno.h header file το οποίο απαιτείται από το errno.h. Δηλαδή δεν μπορούμε να χρησιμοποιήσουμε το errno.h. Χωρίς το errno.h είναι σχεδόν αδύνατο να καταλάβουμε το είδος των προβλημάτων κατά το διάβασμα των 2 τιμών κόστους. Κατά συνέπεια είναι επίσης πολύ δύσκολο να τυπώσουμε και τα κατάλληλα μηνύματα στον χρήστη προκειμένου να ξέρει τι πήγε στραβά. Σε κανονική χρήση του προγράμματος, τέτοια λάθη δεν θα έπρεπε ποτέ να συμβούν, όμως είναι μια περίπτωση που αν συμβούν, για οποιονδήποτε λόγο, είναι δύσκολο να καταλάβουμε ποιο ήταν το πρόβλημα χωρίς να χρησιμοποιήσουμε κάτι σαν το strace.

Resources