Ενδιαφέρουσα άσκηση σε C++ από μία εταιρεία

[Επισκέπτης]

Καλησπέρα,

 

Ψάχνοντας για ασκήσεις προγραμματισμού από διάφορες εταιρίες του εξωτερικού βρήκα την συγκεκριμένη άσκηση της εταιρείας Mode Lighting: http://modelighting.com/photos/embedded-software-eng-job.html η οποία παρουσιάζει κάποιες δυσκολίες καθώς απ' ότι λέει η εκφώνηση θα πρέπει η υλοποίηση να είναι πολύ αποτελεσματική/αποδοτική και να μπορεί να τρέξει απροβλημάτιστα σε περιβάλλον περιορισμένων πόρων.

 

Εγώ έχω υλοποιήσει μια λύση στο πρόβλημα καθώς και script που πραγματοποιούν το code validation αλλά δεν πιστεύω ότι είναι αρκετά efficient.

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

[migf1]

Αν ήταν σε C θα έκανα καμιά προσπάθεια, αλλά για C++ πρέπει να "ξεσκονίσω" πάαρα πολύ τη μνήμη και τα κιτάπια μου, οπότε δεν παίζει.

 

Ίσως το κάνω όμως σε C μόλις ευκαιρήσω, πες μου κάτι όμως που δεν έχω καταλάβει στην εκφώνηση. Τα συνεχόμενα % γίνονται treat σαν να είναι ένα;

 

Δηλαδή η παρακάτω γραμμή από το παράδειγμά του...

 

>
SCENE%T%%%%GO,SCENE%%T%%%%GO,SCENE%%%T%%%%GO,SCENE%%%%T%%%%GO:

ισοδυναμεί με...

 

>
SCENE%T%GO,SCENE%T%GO,SCENE%T%GO,SCENE%T%GO:

ή όχι;

 

EDIT:

Άκυρο, δεν ισοδυναμεί. Τώρα κατάλαβα τι θέλει... το κάθε % αντιστοιχεί σε ένα 10δικό ψηφίο.

[Επισκέπτης]

ακριβώς.. όταν λέει πχ. SCENE%GO, SCENE%%GO, SCENE%%%GO, SCENE%%%%GO σημαίνει ότι η είσοδος μπορεί να είναι: SCENE1GO ή SCENE987GO ή ακόμα και SCENE4444GO.

 

Έκανα και εγώ πρώτα μια υλοποίηση σε C και μετά την "πέρασα" σε C++ γιατί δεν θυμόμουν κάποια πράγματα. Η ουσία της άσκησης πάντως είναι να γίνει σωστά η υλοποίηση του parser ώστε να είναι efficient.

[migf1]

Δεδομένου πως τα fixed commands είναι πολύ μικρά και σε πλήθος και σε μέγεθος, μια inplace μετατροπή κατά το input, ενδεχομένως με χρήση ενός μικρού hash table για τα fixed commands (SCENE, GO, κλπ) λογικά πληροί και με το παραπάνω το efficiency.

 

EDIT:

 

Βλέποντας πάλι την εκφώνηση κι εφόσον τους ενδιαφέρει το efficiency, μου κάνει εντύπωση πως το

 

>CommandSet_t;

δεν το έχουν υλοποιημένο με bitflag values (0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, κλπ) και το αποτέλεσμα να επιστρέφεται απλά ως ένα 2byte word (16 είναι οι τιμές που περιέχει ο τύπος: CommandSet_t), με αναμμένα τα bits που αντιστοιχούν στις εντολές που βρέθηκαν.

 

Ίσως όμως εννοούν μονάχα speed efficiency και όχι και memory efficiency.

[ChRis6]

Θα μπορουσε καποιος να γραψει μια γραμματικη με διαφορους κανονες και να αναγνωριζει τις συμβολοσειρες που ζηταει .

 

Π.χ

 

S --> SCENE N GO

N--> %N | id | ε

 

Και στη συχεχεια με αναλυση απο πανω προς τα κατω ελεγχοντας ενα προπορευομενο χαρακτηρα, να βρισκει τις συμβολοσειρες και να επιστρεφει το καταλληλο κωδικο

 

 

ελπιζω να μην ειμαι εκτος τοπου και χρονου

 

[Επισκέπτης]

Θα μπορουσε καποιος να γραψει μια γραμματικη με διαφορους κανονες και να αναγνωριζει τις συμβολοσειρες που ζηταει .

 

Υποθέτω πως μια efficient λύση θα ακολουθούσε αυτή την προσέγγιση (lexer), ωστόσο προσπαθώ να σκεφτώ πως θα γινόταν μια τέτοια υλοποίηση στο συγκεκριμένο πρόβλημα...

 

Όσο για το CommandSet_t δεν νομίζω ότι εννοούν τόσο memory restricted περιβάλλον ώστε να χρειάζεται bitflags.. σίγουρα όμως θέλουν memory + speed efficiency.

[migf1]

...

Όσο για το CommandSet_t δεν νομίζω ότι εννοούν τόσο memory restricted περιβάλλον ώστε να χρειάζεται bitflags.. σίγουρα όμως θέλουν memory + speed efficiency.

Το πιο efficient και σε μνήμη και σε ταχύτητα είναι ένα: inplace parsing με απευθείας σύγκριση μέσω τεράστιων switch-case ή if, με καθόλου ή ελάχιστη χρήση data-structures (για να μην πω και με ελάχιστη χρήση συναρτήσεων και αντικατάστασή τους με macros, μιας και το inlining δεν είναι εγγυημένο)... αλλά κάτι τέτοιο βγάζει κώδικα συγκρίσιμο με basic της 10ετίας του '80

 

Για μένα είναι ambiguous η εκφώνηση σε ότι αφορά τον όρο "efficiency". Ο κανόνας στο efficiency είναι trade-off μεταξύ μνήμης και ταχύτητας, και δεν το ξεκαθαρίζει. Από τα συμφραζόμενα όμως (C++, STL, OOP, κλπ) αντιλαμβάνομαι πως το memory efficiency έχει ήδη πάει περίπατο, οπότε κατά πάσα πιθανότητα εννοεί speed efficiency.

 

Αν είναι όντως έτσι, το inplace parsing είναι μάλλον μονόδρομος, αλλά με τη σειρά του σημαίνει αρκετούς καφέδες, τσιγάρα, ενδεχομένως και ασπιρίνες

[Επισκέπτης]

Με τον όρο in-place parsing τι ακριβώς εννοείς? Μπορείς να δώσεις κάποιο παράδειγμα?

 

Εγώ το έχω λύσει με τον παραδοσιακό "τα ζώα μου αργά" τρόπο.. (θα το βάλω κάποια στιγμή εδώ)

[migf1]

Inplace είναι να διαβάζεις το input έναν-έναν χαρακτήρα και να κάνεις όλες τις ενέργειες που χρειάζεσαι επί τόπου, ώστε να μη χρειαστεί να κάνεις 2ο pass στο input.

 

Σαν φιλοσοφία θυμίζει ολίγον από event-driven προγραμματισμό στα GUI (όπου το κάθε message φεύγει από το message-queue μόλις το επεξεργαστείς).

 

Μισό να σου βρω ένα παράδειγμα inplace processing από άλλο νήμα, που είχα ποστάρει πριν μερικές μέρες...

 

EDIT:

 

Να εδώ: http://www.insomnia.gr/topic/432317-%cf%80%cf%81%cf%8c%ce%b2%ce%bb%ce%b7%ce%bc%ce%b1-%ce%bc%ce%b5-%ce%ac%cf%83%ce%ba%ce%b7%cf%83%ce%b7-%cf%83%cf%84%ce%b7%ce%bd-c/page__view__findpost__p__4503493 (συνάρτηση: handle_input_inplace( ... ); )

[defacer]

Παιδιά οι τύποι λένε embedded development. Προφανώς εννοούν memory efficiency πάνω απ' όλα, εξάλλου είναι λίγο δύσκολο να καταφέρεις να κάνεις κώδικα που να είναι αργός στο parsing μιας εντολής που θα αποτελείται από 5-15 χαρακτήρες.

 

Με μια γρήγορη ματιά που του έριξα αυτό που καταλαβαίνω είναι ότι αν τους κάνεις ένα σωστό implementation όπου τους επιστρέφεις κάτι με έναν input iterator και κάνεις το parsing της επόμενης εντολής on demand κάθε φορά, την άλλη μέρα σε φωνάζουν για interview.

[migf1]

Παιδιά οι τύποι λένε embedded development. Προφανώς εννοούν memory efficiency πάνω απ' όλα, εξάλλου είναι λίγο δύσκολο να καταφέρεις να κάνεις κώδικα που να είναι αργός στο parsing μιας εντολής που θα αποτελείται από 5-15 χαρακτήρες.

Όχι 5-15 χαρακτήρες ρε συ, λίγο πιο κάτω λέει πως θα τεστάρουν τις υλοποιήσεις με strings 1Mb.

 

Με μια γρήγορη ματιά που του έριξα αυτό που καταλαβαίνω είναι ότι αν τους κάνεις ένα σωστό implementation όπου τους επιστρέφεις κάτι με έναν input iterator και κάνεις το parsing της επόμενης εντολής on demand κάθε φορά, την άλλη μέρα σε φωνάζουν για interview.

Εμένα πάντως με κατα-μπέρδεψε η εκφώνηση της άσκησης.

 

Από τη μια μιλάει για input απροσδιόριστου μεγέθους, κι από την άλλη δίνει template για υλοποίηση της συνάρτησης που θα κάνει process το input η οποία παίρνει σαν 2ο όρισμα μέγιστο μήκος για το input.

 

Εν τω μεταξύ φίλε defacer, με τέτοια υλοποίηση που δίνει στο template/api, μόνο το memory footprint που δημιουργεί αρκεί για να μπει κανείς σε σοβαρές αμφιβολίες για το εάν και κατά πόσο τους ενδιαφέρει το memory efficiency.

[MitsakosGR]

Όχι 5-15 χαρακτήρες ρε συ, λίγο πιο κάτω λέει πως θα τεστάρουν τις υλοποιήσεις με strings 1Mb.

 

Η κάθε εντολή είναι 5-15 χαρακτήρες (8-20 για την ακρίβεια), όχι όλο το string. Κάθε string μπορεί να αποτελείται από πολλές εντολές, οπότε μπορείς να κάνεις parse μία μία χωριστά την ώρα που στο ζητάει.

 

Εμένα πάντως με κατα-μπέρδεψε η εκφώνηση της άσκησης.

 

Από τη μια μιλάει για input απροσδιόριστου μεγέθους, κι από την άλλη δίνει template για υλοποίηση της συνάρτησης που θα κάνει process το input η οποία παίρνει σαν 2ο όρισμα μέγιστο μήκος για το input.

 

Εν τω μεταξύ φίλε defacer, με τέτοια υλοποίηση που δίνει στο template/api, μόνο το memory footprint που δημιουργεί αρκεί για να μπει κανείς σε σοβαρές αμφιβολίες για το εάν και κατά πόσο τους ενδιαφέρει το memory efficiency.

 

Το Input απροσδιόριστου μεγέθους εννοεί ότι το σύνολο των εντολών στην αρχή μπορεί να είναι ότι να'ναι. Απλά περνάει και σαν όρισμα στην συνάρτηση το μέγεθος του string για διευκόλυνση μέσα στο υλοποίηση.

Είναι βασικό και αυτό που αναφέρει ότι o parser μηδενίζει κάθε φορά που του κάνει initialize και όχι κάθε φορά που του περνάς εντολές. Οπότε στην ουσία μπορείς να τρέξεις την συνάρτηση processInput πολλές φορές πριν καλέσεις την getCommand ώστε να σου επιστρέψει την πρώτη εντολή από όλα τα processInput που του έχεις περάσει από το Initialization και μετά.

[defacer]

Το Input απροσδιόριστου μεγέθους εννοεί ότι το σύνολο των εντολών στην αρχή μπορεί να είναι ότι να'ναι. Απλά περνάει και σαν όρισμα στην συνάρτηση το μέγεθος του string για διευκόλυνση μέσα στο υλοποίηση.

Είναι βασικό και αυτό που αναφέρει ότι o parser μηδενίζει κάθε φορά που του κάνει initialize και όχι κάθε φορά που του περνάς εντολές. Οπότε στην ουσία μπορείς να τρέξεις την συνάρτηση processInput πολλές φορές πριν καλέσεις την getCommand ώστε να σου επιστρέψει την πρώτη εντολή από όλα τα processInput που του έχεις περάσει από το Initialization και μετά.

 

Πολύ σωστά. Όπως εξάλλου αναφέρει κάπου, θα έχεις να κάνεις με input stream. Δηλαδή θα σου ταϊζουν κάποια bytes κάθε φορά όπως αυτά έρχονται από τη σειριακή (το αναφέρει και αυτό, RS-232), πιθανότατα έναν fixed αριθμό ίσο με το μέγεθος κάποιου buffer όπου συγκεντρώνονται προσωρινά. Βάσει της εφαρμογής ας πούμε ότι λογικά νούμερα είναι 256 <= sizeof(buffer) <= 1024.

 

Τώρα σύμφωνα μ' αυτά που αναφέρει εγώ καταλαβαίνω πως κάθε μία κλήση στην processInput οφείλει να επιστρέφει ένα αντικείμενο T το οποίο θα λειτουργεί ως iterator πάνω στις εντολές που περιέχονταν στα δεδομένα εισόδου που περάστηκαν στην processInput.

 

Σ' αυτό το σημείο τώρα υπάρχουν 2 αδιευκρίνιστα στοιχεία:

 

1. Είναι δυνατόν το input που θα σου περαστεί να περιέχει και μια "μισή" εντολή στο τέλος; Αν ναι, τι πρέπει να γίνει μ' αυτήν;

 

Νομίζω πως η απάντηση στην πρώτη ερώτηση είναι ναι, γιατί το λογικότερο είναι να παίρνεις fixed size buffers από τη σειριακή όπως λέω παραπάνω και δεδομένου ότι ο parser είσαι εσύ δεν υπάρχει κανείς άλλος να κάνει τη διευκόλυνση να σου χωρίζει την είσοδο σε "ολόκληρες" εντολές. Τώρα όσο για το τι θα γίνει με τη μισή εντολή, προφανώς δε μπορεί να επιστραφεί σαν μέρος των αποτελεσμάτων του iterator, εξίσου προφανώς όμως δε μπορούμε και να την πετάξουμε στα σκουπίδια. Για το τι θα την κάνουμε μεταθέτω την απόφαση γιατί έχουμε να σκεφτούμε και το

 

2. Ποιός είναι ο owner της μνήμης του buffer που σου περνάνε σαν είσοδο στην processInput? Με άλλα λόγια, τι θα συμβεί αν κάποιος σου περάσει ένα buffer, μετά τον κάνει overwrite με σκουπίδια και μετά από αυτό προσπαθήσει να κάνει iterate πάνω στο αντικείμενο Τ που επέστρεψε η processInput?

 

Και αυτό δεν δηλώνεται ευθέως στη διατύπωση, οπότε ας το αναλύσουμε. Δεν είναι δύσκολο να υποθέσουμε ότι η ιδιοκτησία του buffer δεν περνάει σε μας (στο αντικείμενο Τ) αφού αν γινόταν κάτι τέτοιο θα έπρεπε να υπάρχει τρόπος να κάνουμε free τον buffer κάποια στιγμή, το οποίο με τη σειρά του σημαίνει ότι θα έπρεπε να κάνουμε μια σειρά από ακόμα μεγαλύτερες υποθέσεις όπως ποιό πρέπει να είναι το lifetime του buffer, ποιός allocator πρέπει να χρησιμοποιηθεί για να τον απελευθερώσει κλπ. Επίσης υπάρχουν και άλλα δείγματα γραφής στο public interface του IParser που δείχνουν προς τα εκεί. Οπότε Occam's razor => δεν είναι owned απο μας ο buffer.

 

Αφού λοιπόν δεν είναι, τότε από τη στιγμή που θα επιστρέψει η processInput είναι υποχρέωση του caller να διασφαλίσει ότι δεν πρόκειται να διαγραφεί ο buffer μέχρι να τελειώσει το iteration πάνω σ' αυτόν. ΟΚ ως εδώ.

 

Γυρνάμε τώρα πίσω στο #1 αφού αποφασίσαμε πως ο buffer δεν είναι ιδιοκτησία μας. Τι γίνεται αν ο buffer περιέχει στο τέλος μισή εντολή; Εδώ σε θέλω κάβουρα. Δεν είναι λογικό το να την πετάξουμε, αλλά σε διαφορετική περίπτωση θα πρέπει

 

* είτε να δώσουμε κάπως στον caller την πληροφορία "μέχρι που χρησιμοποιήσαμε" και να του πετάξουμε το μπαλάκι ότι τα δεδομένα απο κει και πέρα πρέπει να μας τα ξαναπεράσει στην επόμενη processInput

* είτε να κρατήσουμε κάπου σε δικό μας storage τα δεδομένα που περίσσεψαν και να κανονίσουμε με κάποιο τρόπο ο επόμενος iterator που θα επιστρέψουμε να διαβάσει αρχικά τα δεδομένα από το δικό μας "stockpile" (ας το πω έτσι για να μη μπερδευτούμε) και μετά να συνεχίσει να διαβάζει από τα δεδομένα που μας έφερε η processInput με την οποία επιστρέφουμε τον iterator. Επίσης, σε περίπτωση που κληθεί παραπάνω απο μια φορά η processInput, και κάθε φορά περιέχει "μισή εντολή", και δεν χρησιμοποιηθεί κανένας από τους iterator που θα επιστραφούν μέχρι να γίνουν όλες αυτές οι κλήσεις της processInput, θα πρέπει οι iterators αυτοί να έχουν ξεχωριστά stockpiles για να μη μπερδευτεί ο ένας στα πόδια του άλλου. Επομένως είναι λογικό το κάθε stockpile να έχει το ίδιο lifetime με τον iterator στον οποίο αντιστοιχεί, άρα το βάζουμε σαν allocated μνήμη με κάποιο τρόπο στο αντικείμενο Τ και την ελευθερώνουμε στο destructor.

 

(Εδώ τώρα ενδεχομένως μπαίνουμε σε σενάρια επιστημονικής φαντασίας του στυλ αφού το μέγεθος αυτών των stockpiles θα είναι βάσει των όσων έχουμε δει ~10 bytes, ο generic heap allocator AKA new δεν είναι η καταλληλότερη λύση γιατί θα βάλει "πολύ" overhead. Οπότε αμα λάχει γράφουμε και ένα δικό μας allocator ειδικά optimized για allocations μεγέθους π.χ. 16 bytes τη φορα. Αλλά ας μην πάμε εκεί.)

 

Τι ιδιαιτερότητες έχουμε με την κάθε προσέγγιση από τις 2?

 

* με την πρώτη (που θα μπορούσε να υλοποιηθεί βάζοντας στον T μια method int bytesConsumed() const και ο caller ας κόψει το κεφάλι του) είναι φανερό πως για να δώσουμε αυτή την πληροφορία θα πρέπει πρώτα να έχουμε δει πού ακριβώς τελειώνουν οι ολόκληρες εντολές στο buffer (προσοχή -- δε χρειάζεται να τις κάνουμε και parse ως εδώ!). Αυτό όμως είναι κάτι που αναγκαστικά πρέπει να κάνουμε ούτως ή άλλως, γιατί αλλιώς δεν θα ξέρουμε τι να επιστρέψουμε από την T::iterator::end. Αν υπάρχει εύκολος τρόπος να το κάνουμε αυτό (που όπως φαίνεται από το sample input υπάρχει) τότε ΟΚ, αλλιώς γάμα τα: πρέπει να κάνουμε parse όλες τις εντολές απο πριν, και δε μπορούμε και να τις αποθηκεύσουμε οπότε θα γίνει αναγκαστικά 2 φορές το parsing.

* με τη δεύτερη λύση κάθε iterator εν δυνάμει κάνει dynamically allocate μνήμη για το stockpile, η οποία θα απελευθερωθεί όταν τελειώσει το lifetime του allocator, το οποίο σημαίνει ότι με συνεχόμενα calls στην processInput μπορεί κανείς να κάνει το σύστημα να μείνει απο μνήμη.

 

Οπότε εδώ κολλήσαμε -- καμία λύση δεν είναι πιστεύω εμφανώς προτιμότερη από την άλλη. Η πρώτη σίγουρα είναι ευκολότερη για μας. Κανονικά θα έλεγα ότι η δεύτερη είναι και λίγο πιο ύποπτη, αλλά υπάρχουν και ακόμα 2 σημαντικοί παράγοντες.

 

1. Η processInput επιστρέφει instance του iterator, που σημαίνει ότι ο iterator προορίζεται για μικρής διάρκειας ζωή (όπως εξάλλου και όλοι οι iterators) -- οπότε ο caller μας δε θα είναι γραμμένος έτσι που να κρατάει πολλούς χωρίς να τους κάνει τίποτα οπότε δε θα μείνουμε απο μνήμη.

2. Επειδή το κάθε αντικείμενο-iterator θα είναι εντελώς immutable μετά τη δημιουργία του, μπορούμε να επιτρέψουμε στην class να είναι copyable γλυτώνοντας με ένα απλό shallow copy και ένα απλό reference counting για να δούμε πότε μπορούμε να την απελευθερώσουμε.

 

Για να είμαι ειλικρινής, αν ήταν να στείλω αίτηση θα έκανα το implementation και με τους 2 τρόπους για να τους δείξω ποιος είναι το αφεντικό. Εννοείται πως θα τους έστελνα και όλη την ανάλυση που έγραψα (και όση σκέφτηκα αλλά δεν έγραψα) μαζί, πράγμα το οποίο κατά την άποψή μου είναι ακόμα πιο σημαντικό από το implementation.

 

Ένα πράγμα σαν μια περίπτωση άσκησης στο πανεπιστήμιο: έβγαλα ένα λογικό αποτέλεσμα αλλά με λάθος πρόσημο. Οι πράξεις ήταν πάρα πολλές και δεν προλάβαινα να βρω που έγινε το λάθος στο πρόσημο, οπότε έγραψα σε μια παράγραφο ότι γι' αυτό και γι' αυτό το λόγο το πρόσημο πρέπει να είναι έτσι αλλά το έχω βγάλει ανάποδα -- δεν προλαβαίνω όμως να βρω που είναι το λάθος μου. Όπως αποδείχτηκε, είτε είχα γράψει καλύτερα απ' ότι νόμιζα είτε αυτό ήταν αρκετό για να μη μου κόψει τίποτα από εκείνο το αποτέλεσμα.

 

TL;DR: Η "άσκηση" αυτή δεν είναι παίξε γέλασε.

[MitsakosGR]

Εγώ είμαι της άποψης ότι αφού δεν διευκρινίζει τι κάνουμε αν έχει μισή εντολή (ή λάθος ή οτιδήποτε) τότε αν κληθεί η getCommand() τότε να επιστρέψει csUnknown και άσε τον caller να το διαχειριστεί. Δεν αναφέρει κάπου ότι πρέπει να γίνεται έλεγχος του Input κατά την διάρκεια του getCommand().

 

Πώς εννοείς το να κάνει overright την buffer σου; Δεδομένα μέσα μπορεί να περάσει μόνο με την processInput() και η μόνη εντολή τροποποίησης που έχει είναι η initParser() που κάνει initialise τον parser και διαγράφει ότι στοιχεία έχεις μέχρι τώρα (διαγράφει μνήμη, μηδενίζει μετρητές, iterators, τα πάντα).

Για εμένα δεν είναι υποχρεωτικό να κάνουμε όλο το κείμενο parse. Σαν iterator.begin() θα είναι πάντα η αρχή του string. ΤΟ ερώτημά μου είναι για τον iterator.end(): Δείχνει στο τέλος του κειμένου ή στην τελευταία εντολή;

 

Αν δείχνει το τέλος του κειμένου είναι πολύ απλό, τον θέτουμε κάθε φορά που γίνεται processInput() στο τέλος του buffer και τελείωσε.

 

Αν δείχνει στην τελευταία εντολή τότε κάθε φορά που έρχεται ένας χαρακτήρας με την processInput θα πρέπει να κάνουμε έλεγχο αν οι δύο τελευταίοι χαρακτήρες ολοκληρώνουν εντολή για να αλλάξουμε το end(). Έτσι δεν έχουμε και το πρόβλημα της μισής εντολής (στο τέλος τουλάχιστον) που αναφέρεις defacer καθώς ο iterator δείχνει πάντα σε ολοκληρωμένη εντολή.

 

 

Για allocator δεν ξέρω να φτιάχνω αλλά αν ήξερα θα έφτιαχνα ένα που να κάνει allocate 12bytes κάθε φορά. Αυτό γιατί βάσει του συνόλου των εντολών ο μέσος όρος γραμμάτων είναι 11,7 με 33 εντολές με 12 ή λιγότερα γράμματα και 18 και περισσότερα.

[defacer]

Εγώ είμαι της άποψης ότι αφού δεν διευκρινίζει τι κάνουμε αν έχει μισή εντολή (ή λάθος ή οτιδήποτε) τότε αν κληθεί η getCommand() τότε να επιστρέψει csUnknown και άσε τον caller να το διαχειριστεί. Δεν αναφέρει κάπου ότι πρέπει να γίνεται έλεγχος του Input κατά την διάρκεια του getCommand().

 

Η αλήθεια είναι ότι στα σχόλια για την processInput λέει "processes any given number of characters from the stream at a time, returns the sets of identified commands if any". Αλλά το θέμα είναι πως πρέπει είτε να ξέρεις πως δε θα σου περαστούν μισές εντολές είτε να δίνεις τρόπο στον caller να ξέρει πόσο ακριβώς input κατανάλωσες αλλιώς δε μπορεί να λειτουργήσει το πρόγραμμα. Απο τη στιγμή που το αντιλαμβανόμαστε αυτό δε μπορούμε βέβαια να στείλουμε υποβολή που το αγνοεί.

 

Πώς εννοείς το να κάνει overright την buffer σου; Δεδομένα μέσα μπορεί να περάσει μόνο με την processInput() και η μόνη εντολή τροποποίησης που έχει είναι η initParser() που κάνει initialise τον parser και διαγράφει ότι στοιχεία έχεις μέχρι τώρα (διαγράφει μνήμη, μηδενίζει μετρητές, iterators, τα πάντα).

 

Εννοώ αυτό το σενάριο: καλεί την processInput με κάποιο char*. H processInput δεν έχει κάνει ακόμα parsing (γιατι αν είχε κάνει θα έπρεπε να κρατάει στη μνήμη τα αποτελέσματα οπότε πακέτο), περιμένει να ξεκινήσει το iteration για να γίνει parsing on demand. Πριν λοιπόν ξεκινήσει το iteration, σου αντικαθιστά τα περιεχόμενα του char* με άλλα. Όχι ότι θα το κάνει κανείς αυτό, αλλά τα "what if" σενάρια είναι χρήσιμα.

 

Για εμένα δεν είναι υποχρεωτικό να κάνουμε όλο το κείμενο parse. Σαν iterator.begin() θα είναι πάντα η αρχή του string. ΤΟ ερώτημά μου είναι για τον iterator.end(): Δείχνει στο τέλος του κειμένου ή στην τελευταία εντολή;

 

Αν δείχνει το τέλος του κειμένου είναι πολύ απλό, τον θέτουμε κάθε φορά που γίνεται processInput() στο τέλος του buffer και τελείωσε.

 

Ο iterator δε μπορεί να δείχνει άμεσα στον buffer, όπως λέει και η εκφώνηση "T iterators should act as pointers to objects that support the IParserResult interface". Φαντάζομαι ότι εννοείς πως ο iterator θα έχει έναν εσωτερικό pointer σε κάποιο σημείο του buffer (εξάλλου στην τελική πρέπει να υπάρχει κάποιος τρόπος να κάνεις το comparison με το end).

 

Πάντως αυτό που λες γίνεται, αφού μπορούμε στον iterator να κρατάμε και pointer στο το τέλος του buffer κι έτσι να αποφύγουμε το overscanning όταν κληθεί ο operator ++ ενώ ήδη έχουμε φτάσει στην τελευταία μισή εντολή.

 

Αν δείχνει στην τελευταία εντολή τότε κάθε φορά που έρχεται ένας χαρακτήρας με την processInput θα πρέπει να κάνουμε έλεγχο αν οι δύο τελευταίοι χαρακτήρες ολοκληρώνουν εντολή για να αλλάξουμε το end(). Έτσι δεν έχουμε και το πρόβλημα της μισής εντολής (στο τέλος τουλάχιστον) που αναφέρεις defacer καθώς ο iterator δείχνει πάντα σε ολοκληρωμένη εντολή.

 

Εδώ τώρα νομίζω πως έχεις παρανοήσει λίγο: σ' αυτή την κουβέντα όταν λέω iterator, εννοώ το object Τ που επιστρέφει η processInput (παρόλο που technically o iterator είναι το άλλο object που θα σου επιστραφεί με κάποιο τρόπο από το οbject Τ όταν καλέσεις την begin). Δηλαδή η λογική είναι (όπως την περιγράφει η εκφώνηση) ότι κάθε φορά που σου δίνουν input θα επιστρέφεις ένα Τ με το οποίο μπορούμε να κάνουμε iteration στις εντολές που περιεχόταν στο συγκεκριμένο τμήμα input. Οπότε η έννοια του end είναι διαφορετική για κάθε έναν από αυτούς τους iterators, δεν υπάρχει "το" end.

 

Για allocator δεν ξέρω να φτιάχνω αλλά αν ήξερα θα έφτιαχνα ένα που να κάνει allocate 12bytes κάθε φορά. Αυτό γιατί βάσει του συνόλου των εντολών ο μέσος όρος γραμμάτων είναι 11,7 με 33 εντολές με 12 ή λιγότερα γράμματα και 18 και περισσότερα.

 

Ρίξε μια ματιά στο 4o κεφάλαιο του Modern C++ Design. Βασικά σε όλο το βιβλίο, απλά το 4ο κεφάλαιο είναι εκεί που φτιάχνει allocator.