Το HotXLS, η εγγενής βιβλιοθήκη Excel για Delphi και C++Builder, εκτελεί σταδιακό επαναϋπολογισμό τύπων (incremental formula recalculation) μέσω της TXLSXWorkbook.Recalculate. Η πρώτη κλήση κατασκευάζει έναν γράφο εξαρτήσεων τύπων και αξιολογεί κάθε κελί τύπου· κάθε μεταγενέστερη κλήση επαναξιολογεί μόνο τα κελιά που επηρεάζονται από εγγραφές τιμών μετά το τελευταίο πέρασμα, με τοπολογική σειρά, σε ένα μόνο πέρασμα του οποίου το κόστος είναι ανάλογο με τον αριθμό των τροποποιημένων (dirty) κελιών και όχι με το μέγεθος του βιβλίου εργασίας
Αυτή η μοναδική σχεδιαστική απόφαση είναι η διαφορά ανάμεσα σε ένα χρηματοοικονομικό μοντέλο που ανταποκρίνεται σε μια τροποποιημένη υπόθεση σε χιλιοστά του δευτερολέπτου και σε ένα άλλο που καθυστερεί για δευτερόλεπτα. Εάν δημιουργείτε αναφορές όπου ελάχιστα κελιά εισόδου τροφοδοτούν χιλιάδες κατάντη τύπους, το υπόλοιπο αυτού του άρθρου εξηγεί τι κάνει ο γράφος, ποιες συναρτήσεις εξαιρούνται από τη σταδιακή επανεκτίμηση, και πώς αναφέρονται οι κυκλικές αναφορές αντί να δημιουργούν ατέρμονη λούπα
Γιατί η αλλαγή ενός κελιού επαναϋπολογίζει εκατό χιλιάδες τύπους;
Μια απλοϊκή μηχανή τύπων δεν έχει μνήμη για το ποιος εξαρτάται από ποιον, επομένως η μόνη ασφαλής κίνηση μετά από οποιαδήποτε επεξεργασία είναι να αξιολογήσει τα πάντα ξανά. Ακόμη χειρότερα, η κλασική αναδρομική στρατηγική — όταν ο τύπος Α αναφέρεται στον τύπος Β, να αξιολογεί τον Β επί τόπου — επαναξιολογεί τα αναφερόμενα κελιά άνευ όρων, αγνοώντας οποιαδήποτε αποθηκευμένη τιμή (cached value). Μια αλυσίδα n τύπων όπου καθένας αναφέρεται στον προηγούμενο κοστίζει O(n²) αξιολογήσεις ανά πλήρες πέρασμα, και μια κυκλική αναφορά στέλνει την αναδρομή στον γκρεμό. Κάθε προγραμματιστής υπολογιστικών φύλλων που έχει συνδέσει ένα μοντέλο διαδοχικών υπολογισμών (cascading model) σε έναν αναδρομικό αξιολογητή έχει δει να συμβαίνουν και οι δύο τρόποι αποτυχίας
Το Excel ίδιο το έλυσε αυτό πριν από δεκαετίες με την αλυσίδα υπολογισμών του (calculation chain): μια διάταξη των κελιών τύπων που διατηρείται έτσι ώστε μια επεξεργασία να επισημαίνει ένα μικρό σύνολο κελιών ως τροποποιημένα (dirty) και η μηχανή να διατρέχει μόνο το επηρεαζόμενο τέλος της αλυσίδας. Το HotXLS εφαρμόζει την ίδια ιδέα ως έναν ρητό γράφο εξαρτήσεων, ο οποίος κατασκευάζεται μία φορά από τα μεταγλωττισμένα δέντρα τύπων και επαναχρησιμοποιείται στα περάσματα επαναϋπολογισμού. Το θέμα δεν είναι η ευφυΐα· είναι ότι το κόστος επαναϋπολογισμού θα πρέπει να ακολουθεί το μέγεθος της επεξεργασίας σας, όχι το μέγεθος του βιβλίου εργασίας σας
Πώς ο γράφος εξαρτήσεων μετατρέπει μια επεξεργασία σε ένα μόνο πέρασμα
Ο γράφος εξαρτήσεων του HotXLS δίνει σε κάθε κελί τύπου έναν κόμβο, με τις ακμές να ξεκινούν από το προηγούμενο (precedent) προς το εξαρτώμενο (dependent) κελί. Όταν ο κώδικάς σας γράφει μια τιμή κελιού, το βιβλίο εργασίας καταγράφει το κελί ως τροποποιημένο· όταν εκτελείται η Recalculate, η τροποποίηση διαδίδεται κατά μήκος των ακμών σε κάθε κατάντη τύπο, και ο τροποποιημένος υπογράφος αξιολογείται ακριβώς μία φορά σε τοπολογική σειρά χρησιμοποιώντας τον αλγόριθμο του Kahn. Επειδή ένας τύπος δεν επισκέπτεται ποτέ πριν από τα προηγούμενα κελιά του, κάθε κόμβος χρειάζεται μία μόνο αξιολόγηση — αυτό είναι που καθιστά το πέρασμα O(dirty)
Η τοπολογική σειρά διορθώνει επίσης το πρόβλημα της αναδρομής στη ρίζα του. Κατά τη διάρκεια ενός περάσματος επαναϋπολογισμού, η μηχανή μεταβαίνει σε μια αποκλειστική λειτουργία στην οποία οποιαδήποτε αναφορά σε άλλο κελί τύπου διαβάζει απευθείας την αποθηκευμένη τιμή αυτού του κελιού αντί να το επαναξιολογήσει — η διάταξη εγγυάται ότι η αποθηκευμένη τιμή είναι ήδη ενημερωμένη. Ο ίδιος μηχανισμός σημαίνει ότι ένας κύκλος αναφορών δεν μπορεί να προκαλέσει απεριόριστη αναδρομή: τίποτα μέσα στο πέρασμα δεν εισέρχεται ξανά στον αξιολογητή για ένα γειτονικό κελί
var
Book: TXLSXWorkbook;
Inputs, Model: TXLSXWorksheet;
begin
Book := TXLSXWorkbook.Create;
try
Inputs := Book.Sheets.Add('Inputs');
Model := Book.Sheets.Add('Model');
Inputs.Cells[2, 2].Value := 0.05; // growth assumption
Model.Cells[2, 2].Formula := 'Inputs!B2*1000'; // XLSX formulas take no leading '='
Model.Cells[3, 2].Formula := 'B2*(1+Inputs!B2)';
// ... thousands more rows cascading off the same assumption ...
Book.Recalculate; // first call: builds the graph, full evaluation
Inputs.Cells[2, 2].Value := 0.07; // one edit marks one cell dirty
Book.Recalculate; // second call: only the downstream chain runs
finally
Book.Free;
end;
end;Κάθε αποτέλεσμα καταλήγει στην αποθηκευμένη Value του κελιού, οπότε μετά την επιστροφή της Recalculate διαβάζετε τα αποτελέσματα με τον ίδιο τρόπο που διαβάζετε οποιοδήποτε άλλο κελί. Σε έναν βρόχο δημιουργίας αναφορών, το μοτίβο είναι ακριβώς ο παραπάνω κώδικας: φορτώστε ή κατασκευάστε το μοντέλο μία φορά, και στη συνέχεια εναλλάσσετε την εγγραφή μερικών κελιών εισόδου με την κλήση της Recalculate, πληρώνοντας μόνο για τους τύπους που πραγματικά εξαρτώνται από αυτό που άλλαξε
Ποιες συναρτήσεις του Excel επιβάλλουν επαναϋπολογισμό σε κάθε πέρασμα;
Το HotXLS αντιμετωπίζει τις NOW, TODAY, RAND, OFFSET και INDIRECT ως πτητικές (volatile): οποιοσδήποτε τύπος περιέχει μία από αυτές επαναξιολογείται σε κάθε πέρασμα της Recalculate, ανεξάρτητα από το αν άλλαξε κάτι ανάντη. Οι πρώτες τρεις είναι πτητικές για τον ίδιο λόγο που είναι και στο Excel — το αποτέλεσμά τους εξαρτάται από τη στιγμή της αξιολόγησης, όχι από άλλα κελιά. Οι OFFSET και INDIRECT είναι πτητικές για έναν πιο λεπτό λόγο: τα κελιά που διαβάζουν υπολογίζονται κατά το χρόνο εκτέλεσης, επομένως ο γράφος δεν μπορεί να γνωρίζει στατικά ποιες ακμές πρέπει να σχεδιάσει για αυτές
Ο ίδιος συντηρητικός κανόνας επεκτείνεται σε αναφορές που ο δημιουργός του γράφου δεν μπορεί να περιορίσει σε ένα μόνο ορθογώνιο. Ένας τύπος που περνά μέσα από ένα ονοματισμένο εύρος πολλαπλών περιοχών (multi-area named range), ή ένας που αναφέρεται σε εξωτερικό βιβλίο εργασίας, υποβαθμίζεται ομοίως σε πτητικό και επαναξιολογείται σε κάθε πέρασμα. Η πολιτική αυτή είναι σκόπιμη: μια επιπλέον αξιολόγηση κοστίζει λίγο χρόνο, αλλά μια χαμένη ακμή εξάρτησης σημαίνει μια σιωπηρά μπαγιάτικη τιμή σε μια απεσταλμένη αναφορά, και αυτό είναι η πολύ χειρότερη αποτυχία. Εάν το μοντέλο σας βασίζεται σε ονόματα εμβέλειας βιβλίου εργασίας, το συνοδευτικό άρθρο σχετικά με τα ορισμένα ονόματα και τους τύπους μεταξύ φύλλων καλύπτει τον τρόπο επίλυσης ονομάτων μεμονωμένης περιοχής — αυτά συμμετέχουν κανονικά στον γράφο
Η πρακτική καθοδήγηση προκύπτει άμεσα. Κρατήστε τις κρίσιμες διαδρομές ενός μεγάλου μοντέλου σε απλές αναφορές κελιών και ευρών όπου ο γράφος μπορεί να κάνει τη δουλειά του, και περιορίστε τις OFFSET και INDIRECT στα λίγα σημεία που πραγματικά χρειάζονται δυναμική διευθυνσιοδότηση. Ένα μοντέλο με χίλιους πτητικούς τύπους εκτελεί αυτούς τους χίλιους σε κάθε πέρασμα, ανεξάρτητα από το πόσο μικρή ήταν η επεξεργασία — ακριβώς η συμπεριφορά που γνωρίζουν οι χρήστες του Excel από βιβλία εργασίας που "επαναϋπολογίζονται με κάθε πάτημα πλήκτρου"
Πώς αναφέρει το HotXLS τις κυκλικές αναφορές;
Η TXLSXWorkbook.Recalculate επιστρέφει lxOk σε ένα καθαρό πέρασμα και lxErrorRef όταν ανιχνεύει έναν κύκλο αναφορών. Τα μέλη του κύκλου αναγνωρίζονται κατά την τοπολογική ταξινόμηση — είναι οι κόμβοι που ο αλγόριθμος του Kahn δεν μπορεί ποτέ να απελευθερήσει — και παρακάμπτονται αντί να μπαίνουν σε βρόχο: οι αποθηκευμένες τιμές τους παραμένουν όπως ήταν, ενώ κάθε τύπος εκτός του κύκλου εξακολουθεί να αξιολογείται κανονικά με τη σειρά. Το σημείο κλήσης σας λαμβάνει έναν συγκεκριμένο κωδικό σφάλματος αντί για πάγωμα
case Book.Recalculate of
lxOk:
SaveReport(Book);
lxErrorRef:
// a reference cycle exists; cycle members kept their previous
// cached values and everything outside the cycle is up to date
LogWarning('Circular reference detected - review model inputs');
end;Η εύρεση των κελιών που σχηματίζουν τον κύκλο είναι μια εργασία αποσφαλμάτωσης, και ο ανιχνευτής αξιολόγησης τύπων (formula evaluation tracer) είναι το κατάλληλο εργαλείο για αυτό: ανιχνεύστε τον ύποπτο τύπο και η αλυσίδα αναφορών που αναδιπλώνεται στον εαυτό της γίνεται ορατή βήμα προς βήμα. Οι κύκλοι σε πραγματικά μοντέλα είναι σχεδόν πάντα ένα συντακτικό λάθος — μια γραμμή σύνοψης που περιλαμβάνεται κατά λάθος στο δικό της εύρος SUM — επομένως ένας σαφής κωδικός σφάλματος κατά το χρόνο επαναϋπολογισμού είναι ακριβώς αυτό που θέλετε
Τύποι πινάκων, παρακολούθηση τροποποιήσεων και πότε ανακατασκευάζεται ο γράφος
Οι τύποι πινάκων CSE (CSE array formulas) λαμβάνουν έναν κόμβο για ολόκληρο το αγκυρωμένο ορθογώνιο, όχι έναν κόμβο ανά κελί. Ο βασικός τύπος αξιολογείται μία φορά ανά πέρασμα· ο προκύπτων πίνακας γράφεται απευθείας σε κάθε κελί μέλος, και ένας τύπος που αναφέρεται σε οποιοδήποτε κελί εντός του αγκυρωμένου εύρους — όχι μόνο στην πάνω αριστερή άγκυρα — λαμβάνει μια ακμή εξάρτησης από αυτόν τον βασικό κόμβο. Τα βαθμωτά (scalar) αποτελέσματα μεταδίδονται σε όλο το ορθογώνιο με τον τρόπο που ορίζει η παλαιά σημασιολογία πινάκων του Excel
Η παρακολούθηση τροποποιήσεων (dirty tracking) συνδέεται με τους συνηθισμένους setters ιδιοτήτων, οπότε τίποτα δεν αλλάζει στον κώδικά σας. Η εγγραφή της Value σε ένα κελί ειδοποιεί το βιβλίο εργασίας και επισημαίνει τα εξαρτώμενα κελιά ως τροποποιημένα· η εκχώρηση ενός νέου Formula είναι μια δομική αλλαγή, επομένως επισημαίνει ολόκληρο τον γράφο ως παρωχημένο, και η επόμενη Recalculate τον ανακατασκευάζει πριν από την αξιολόγηση. Η προσθήκη, η διαγραφή ή η μετακίνηση φύλλων ακυρώνει επίσης τον γράφο, καθώς η ταυτότητα του κόμβου κωδικοποιεί τον δείκτη φύλλου. Όταν δεν είναι ενεργός κανένας γράφος — ένα βιβλίο εργασίας στο οποίο δεν καλείτε ποτέ την Recalculate — οι συνδέσεις κοστίζουν έναν μόνο έλεγχο nil ανά ανάθεση, επομένως οι απλές εργασίες ανάγνωσης-εγγραφής δεν επηρεάζονται
Ένα όριο που αξίζει να αναφερθεί με ειλικρίνεια: ο γράφος παρακολουθεί τις εξαρτήσεις μεταξύ των κελιών, οπότε μια συνάρτηση ορισμένη από το χρήστη που έχει καταχωρηθεί μέσω της OnUserFunction επαναξιολογείται όταν αλλάζουν τα κελιά που τροφοδοτούν τα ορίσματά της, όπως κάθε άλλος τύπος. Εάν επεκτείνετε τη μηχανή με αυτόν τον τρόπο, το άρθρο σχετικά με τις προσαρμοσμένες συναρτήσεις στη μηχανή τύπων του HotXLS περιγράφει το συμβόλαιο επιστροφής κλήσης και τον τρόπο άφιξης των τιμών των ορισμάτων
Ο σταδιακός επαναϋπολογισμός είναι μέρος της τυπικής μηχανής XLSX στο HotXLS Delphi Excel Component, μαζί με τον υπολογιστή τύπων, τα ορισμένα ονόματα και τη ροή εργασίας εισαγωγής/εξαγωγής που επιταχύνει. Εάν η εφαρμογή σας σε Delphi ή C++Builder διατηρεί ζωντανά μοντέλα — φύλλα τιμολόγησης, βιβλία εργασίας ενοποίησης, διαδοχικές αναφορές — η Recalculate είναι η διαφορά μεταξύ του επανυπολογισμού ενός βιβλίου εργασίας και του επανυπολογισμού μιας επεξεργασίας