Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α18.11 · Προβλέποντας το Μέλλον (future)

Εργασία 2 (2024-25), Άσκηση 1 · Δυσκολία ★★☆ · programming · Κεφάλαια: 18, 13, 12

Προβλέποντας το Μέλλον (future - 50 Μονάδες)

Όλες οι προβλέψεις, από τον καιρό μέχρι την επόμενη λέξη σε μια πρόταση, αξιολογούνται με ένα κοινό κριτήριο: το πόσο ακριβείς είναι. Σε αυτήν την άσκηση, θα υλοποιήσουμε έναν αλγόριθμο που χρησιμοποιείται κατεξοχήν για να κάνουμε προβλέψεις, τον κινούμενο μέσο όρο (Simple Moving Average - SMA). Ο κινούμενος μέσος όρος είναι παρεμφερής με τον κανονικό μέσο όρο, με μια διαφορά: ο κινούμενος μέσος όρος απαιτεί και ένα “παράθυρο” (window), δηλαδή τον αριθμό των τιμών (μετρώντας από το τέλος) που θέλουμε να λάβουμε υπόψη μας στον υπολογισμό του μέσου όρου. Για παράδειγμα, ας υποθέσουμε ότι έχουμε αυτές τις 10 τιμές:

9  7  7  1  4  4  4  38  8  4

Ο μέσος όρος αυτών των τιμών είναι \(\frac{9 + 7 + 7 + 1 + 4 + 4 + 4 + 38 + 8 + 4}{10} = 8.60\). Για να υπολογίσουμε τον κινούμενο μέσο, πρέπει να επιλέξουμε ένα παράθυρο, έστω 3. Τότε ο κινούμενος μέσος με παράθυρο 3 για αυτά τα στοιχεία λαμβάνει υπόψη του μόνο τα τελευταία 3:

\[9 \quad 7 \quad 7 \quad 1 \quad 4 \quad 4 \quad 4 \quad \underbrace{38 \quad 8 \quad 4}_{SMA_3}\]

και επομένως \(SMA_3 = \frac{38 + 8 + 4}{3} = 16.67\). Αντίστοιχα, μπορούν να οριστούν κινούμενοι μέσοι με μικρότερα παράθυρα (π.χ., παράθυρο 1 σημαίνει μόνο το τελευταίο στοιχείο) ή μεγαλύτερα παράθυρα (π.χ., παράθυρο 10 θα λάμβανε υπόψη του όλες τις τιμές παραπάνω).

Σε αυτήν την άσκηση λοιπόν, καλείστε να υλοποιήσετε ένα πρόγραμμα το οποίο θα υπολογίζει τον κινούμενο μέσο όρο για μια σειρά από δεδομένα και να τον εκτυπώνει ως πρόβλεψη.

Τεχνικές Προδιαγραφές

• Repository Name: progintro/hw2-<YourUsername>
• C Filepath: future/src/future.c
• Το πρόγραμμά θα πρέπει να παίρνει ως κυρίως όρισμα το όνομα του αρχείου που περιέχει τα δεδομένα μας. Προαιρετικά, μπορεί να παίρνει και άλλα δύο ορίσματα προκειμένου να ορίσουμε το μέγεθος του “παραθύρου” που θέλουμε για τον κινούμενο μέσο όρο. Για παράδειγμα αν το τρέξουμε ως ./future data.txt --window 42, σημαίνει υπολόγισε τον κινούμενο μέσο όρο με παράθυρο 42 για τα δεδομένα του αρχείου data.txt. Αν δεν δοθεί παράμετρος για το μέγεθος του παραθύρου, τότε το (default) παράθυρο πρέπει να είναι μεγέθους 50. Αν το πρόγραμμα εκτελεστεί με ορίσματα που δεν ακολουθούν τις παραπάνω προδιαγραφές, πρέπει να εκτυπώσει αντίστοιχο μήνυμα όπως στα παρακάτω παραδείγματα και να επιστρέφει με κωδικό εξόδου (exit code) 1.
• Το αρχείο με τα δεδομένα θα περιέχει αριθμούς κινητής υποδιαστολής με μέχρι δύο ψηφία ακριβείας. Γενικά, δεν θα σας ζητηθεί να χρησιμοποιήσετε μεγαλύτερη ακρίβεια από double.
• Αν το παράθυρο είναι μικρότερο από 1 ή μεγαλύτερο από τον συνολικό αριθμό δεδομένων, το πρόγραμμά σας πρέπει να τερματίζει με μήνυμα σφάλματος όπως στα παραδείγματα. Το μήνυμά σας πρέπει να τυπώνεται στο stderr του προγράμματος. Το μέγεθος του παραθύρου δεν θα υπερβεί το \(10^{18}\).
• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): gcc -Os -Wall -Wextra -Werror -pedantic -o future future.c
• README Filepath: future/README.md
• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 1 δευτερόλεπτο.

Παραδείγματα εκτέλεσης ακολουθούν:

$ ./future
Usage: ./future <filename> [--window N (default: 50)]
$ cat values.txt
9 7 7 1 4 4 4 38 8 4
$ ./future values.txt --window 10
8.60
$ echo $?
0
$ ./future values.txt --window 3
16.67
$ ./future values.txt --window 1
4.00
$ ./future values.txt --window 0
Window too small!
$ echo $?
1
$ ./future values.txt --window 0 2> out
$ cat out
Window too small!
$ ./future values.txt --window 12
Window too large!
$ echo $?
1
$ ./future values.txt --window 1000000000000
Failed to allocate window memory

Φυσικά οι ίδιοι έλεγχοι μπορούν να γίνουν με πραγματικά δεδομένα και να δείτε αν οι προβλέψεις του προγράμματός μας είναι καλές (Το αρχείο dow_jones.txt βρίσκεται στο https://github.com/progintro/data):

$ ./future dow_jones.txt
43471.71
$ ./future dow_jones.txt --window 200
40677.19
$ ./future dow_jones.txt --window 1000
35273.61
$ wc -l dow_jones.txt
8302 dow_jones.txt
$ ./future dow_jones.txt --window 8000
15447.33

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης.

Bonus (Προαιρετικό)

Πιστεύετε πως μπορείτε να φτιάξετε αλγορίθμους που προβλέπουν πως θα κινηθεί ένα οικονομικό asset καλύτερα από τον κινούμενο μέσο; Αν ναι, προσθέστε ένα easter egg option στο πρόγραμμά σας ονόματι --compete και θα μπείτε αυτόματα στον διαγωνισμό μας. Η αξιολόγηση θα γίνει με πραγματικά δεδομένα από χρηματιστήρια του κόσμου. Η διεπαφή θα είναι παρόμοια με παραπάνω, απλά υπολογίζετε την καλύτερή σας πρόβλεψη για την επόμενη τιμή σε μια σειρά δεδομένων:

$ ./future dow_jones.txt --compete
43455.32

Οι τρεις καλύτερες υποβολές θα λάβουν 100%, 70% και 40% έξτρα βαθμολογία σε αυτήν την άσκηση.

Υπόδειξη

Χρειάζεστε μόνο τις τελευταίες \(N\) τιμές: ένας κυκλικός πίνακας (ring buffer) μεγέθους ίσου με το παράθυρο, δεσμευμένος με malloc, κρατά αυτές τις τιμές όσο διαβάζετε το αρχείο, χωρίς να ξέρετε από πριν πόσες είναι. Ελέγξτε την τιμή επιστροφής της malloc (δείτε το παράθυρο \(10^{12}\)) και της fopen, διαβάστε το παράθυρο ως 64-bit ακέραιο, και θυμηθείτε ότι τα μηνύματα λάθους πάνε στο stderr.

Αριθμός στον οδηγό: Α18.11 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: hw-2024-hw2-future · Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2024-hw2-future.html · Markdown (GitHub)