Τετάρτη, 18 Νοεμβρίου 2015

Διερεύνηση ρουτίνας ταξινόμησης!

Μια αναθεώρηση ακόμα, η 89, όπου άλλαξα την ρουτίνα με άλλη, για να αποφύγω το τυχαίο πρόβλημα "κολλήματος" κατά το σώσιμο των προγραμμάτων. Παλιά έκανα το εξής..έσβηνα το όνομα.bck,  μετά έκανα αλλαγή ονόματος από όνομα.gsb σε όνομα.bck και τέλος δημιουργούσα ένα νέο  όνομα.gsb όπου έγραφα τα νέα στοιχεία. Και τα τρία στάδια γίνονταν με διαφορετικές βιβλιοθήκες, και ενώ στη τρίτη φάση διόρθωσα το πρόβλημα, την ενδιάμεση, στην αλλαγή ονόματος, όπως διαπίστωσα...περιστασιακά έφερνε κολλήματα. Τώρα τα βήματα είναι δυο, και η βιβλιοθήκη μία, ίδια δηλαδή για τα δύο βήματα. Το πρώτο βήμα κάνει αντιγραφή το όνομα.gsb στο όνομα.bck, και αν βρει το όνομα.bck, το αλλάζει με το αντιγραμμένο. Έτσι σε κάθε περίπτωση έχω το αντιγραμμένο με μια κίνηση! Το επόμενο βήμα είναι το παλιό! Το οποίο είχα διορθώσει. Προς το παρόν δεν βλέπω πρόβλημα!
Σε αυτήν την αναθεώρηση διόρθωσα και άλλα πράγματα, που έχουν σχέση με την ανανέωση των γραφικών. Με την εντολή ΑΝΑΝΕΩΣΗ μπορούμε πια και τις εντολές γραφικών ΧΑΡΑΞΕ, ΚΑΜΠΥΛΗ, ΠΟΛΥΓΩΝΟ, ΚΥΚΛΟΣ, κ.α. να τα κάνουμε να εμφανίζουν το "σύνολο" της δουλειάς σε χρόνο που ορίζουμε με την Ανανέωση. Το Ανανέωση 5000 κάνει το χρόνο εμφάνισης τα 5 δευτερόλεπτα, ενώ δίνει άμεσα μια εμφάνιση. Η εντολή Ανανέωση δίνει άμεσα μια εμφάνιση και ξεκινάει τον μετρητή ξανά. Η εντολή Ανανέωση 0 ξεκινάει πάλι τον μετρητή χωρίς να εμφανίσει. Η Εντολή Κάθε τώρα πια περιλαμβάνει μια "Ανανέωση 0" εσωτερικά. Οι μεταβλητές μόνο ανάγνωσης Ενκομ$ (ένα κομβίο) και Δείκτης, γυρνάνε τιμές για το πληκτρολόγιο και το ποντίκι, με πρόκληση ανανέωσης εκτός μετρήματος. άρα πρέπει να χρησιμοποιούνται σε φάσεις που η ανανέωση δεν μας πειράζει. Αν θέλουμε μπορούμε να χρησιμοποιούμε την ειδική συνάρτηση πατημένο() που στο 1 και 2 μας δίνει τα πλήκτρα του δείκτη (όπως η Δείκτης) χωρίς αν προκαλεί ανανέωση, ενώ η πατημένο(32) για παράδειγμα δίνει -1 αν πατάμε το διάστημα. Όλα τα πλήκτρα του πληκτρολογίου, έχουν νούμερο και μπορούμε να κοιτάμε την κατάστασή τους ανεξάρτητα! Έτσι σε περιπτώσεις που δεν θέλουμε ανανέωση -ανεξέλεγκτη- έχουμε τρόπο. Ορισμένες φορές αντί να βάλουμε μια Ανανέωση βάζουμε μια Αν ενκομ$=" " Τότε Έξοδος και έχουμε δυο σε ένα!



Ένα παράδειγμα-άσκηση-ασχολία στη Μ2000. 
Περιέχει μια ρουτίνα ταξινόμησης που πρόσφερε στο Vbforoums ένα παλιός προγραμματιστής (60+), δείτε εδώ τον κώδικα που είχε παρουσιάσει, και όπως λέει ήταν από το PDP-11
minicomputer. (σε εκείνο το φόρουμ δημοσιεύω ως GeorgeKar μια επέκταση της quicksort, και γίνεται σύγκριση ρουτινών, κόντρα με την καλή έννοια).

Η ρουτίνα είναι μια Shell Sort με υλοποίηση κάπως μυστήρια. Τα αλφαριθμητικά βρίσκονται όλα σε ένα και δεν μπορούν να μετακινηθούν. Υπάρχει ένας αρχικός πίνακας (δίνεται ως σειρά σε σωρό, η Σειρά στη Μ2000 χρησιμοποιεί το σωρό - εσωτερική ειδική στοίβα- ως FIFO. Τα στοιχεία τα "σηκώνουμε" με τη διάβασε. Έχω δημιουργήσει ένα μπλοκ με νέο σωρό -αλλά δεν χρειάζεται λογικά, εκτός και αν παραμένουν στοιχεία στον υπάρχον σωρό, οπότε ο νέος παρεμβάλλεται και στο πέρας επιστρέφει τον παλιό- κάτι σαν stack frame.

Για κάθε αλφαριθμητικό υπάρχει η αρχή και το τέλος, σε δυο μονοδιάστατους πίνακες. Επιπλέον υπάρχει ξεχωριστός πίνακας για τους δείκτες στους δυο προηγούμενους, που κρατάει την σειρά, και την οποία θα την ταξινομήσουμε.
Έτσι το ν στοιχείο του πίνακα sortptrs() δίνει ένα δείκτη για τους άλλους δυο πίνακες, απ΄όπου θα πάρουμε την αρχή και το τέλος ενός αλφαριθμητικού, σε ένα μοναδικό αλφαριθμητικό που περιέχει όλα τα άλλα (ας πούμε την μνήμη), το strSearch$

Φτιάχνουμε μια οθόνη με χρώμα Magenta (το 5), χωρίς χωριστή οθόνη (το μηδέν μετά το πέντε) και πλάτος 60 χαρακτήρες και γραμμές (ή ύψος σε χαρακτήρες) 30. Χρώμα πένας το κίτρινο.
Φτιάχνω δυο γενικές μεταβλητές τον αριθμό των συγκρίσεων και τον αριθμό αλλαγών. Θέλω να διερευνήσω, πόσες συγκρίσεις και πόσες αλλαγές κάνει ο αλγόριθμος σε διάφορες περιπτώσεις.
Έχω καταγράψει κάποια αποτελέσματα σε δεδομένα που έχω πια σκιάσει - ως σημειώσεις.
Με ενδιαφέρει από ένα σημείο και μετά να δω τι γίνεται όταν κάνω προσθήκες.
Οι πίνακες στη Μ2000 μπορούν να οριστούν ξανά (και να αλλάξουν διάσταση) χωρίς να χάσουν τα στοιχεία τους (εκτός αν βάλουμε ένα π.χ. Πίνακας Α$(10)="" οπότε το μηδενίζουμε, βάζουμε "" σε κάθε στοιχείο).



Έχω κάνει μερικά στοιχεία βοηθητικά, όπως μια συνάρτηση η Getone$(). Εκεί δίνω με αναφορά το strSearch$ για να μην το αντιγράψω, αν και το Μεσ$() θα πάρει αντίγραφο, αφού δουλεύει με εκφράσεις! Το ίδιο κάνω και στην mxstrcmp(), αλλά εκεί τουλάχιστον η σύγκρινε δουλεύει με μεταβλητές και κάνει σύγκριση χωρίς αντιγραφές (δεν παίρνει εκφράσεις).
Επίσης χρησιμοποιώ ένα τμήμα γενικής χρήσης, για να γεμίσω τιμές σε ένα πίνακα (ο sortptrs()), και περνάω τον πίνακα με αναφορά, και εκεί μέσα διαβάζω το μέγεθός του.

Τον αλγόριθμο ταξινόμησης τον μετέφερα σε μια ρουτίνα απλή. Οι απλές ρουτίνες είναι μέρη του τμήματος, σαν να ήταν σε ένα οποιοδήποτε μέρος του. Έχουν ένα όνομα και χρειάζεται η εντολή επιστροφή για να γυρίσουν. Έτσι με την μεταφορά του τον χρησιμοποιώ μερικές φορές ακόμα. Χρησιμοποιώ μια ρουτίνα με παράμετρο. Εδώ οι ρουτίνες έχουν το Ρουτίνα Όνομα() και στο τέλος το Τέλος Ρουτίνας. Η διαφορά τους από τις απλές ρουτίνες είναι ότι κάθε νέο εντός τους θα χαθεί μετά - εκτός από την αλλαγή τιμών και διαστάσεων σε πίνακες...και τιμών σε μεταβλητές γενικές και άλλε του τμήματος. Επειδή ουσιαστικά και η ενισχυμένη ρουτίνα είναι μέρος του τμήματος, τα ονόματα των μεταβλητών που δίνουμε για εισαγωγή, δεν πρέπει να υπάρχουν σαν ονόματα μεταβλητών στο τμήμα - αλλιώς θα γυρίσει ο διερμηνευτής λάθος. Η strAdd θα χαθεί μετά την διαμέσου ΠρόσθεσεΈνα().


Σε αυτό το πρόγραμμα "διερεύνυσης" έχει χρησιμοποιηθεί Συνάρτηση, Τμήμα, Ρουτίνα, Απλή Ρουτίνα, Προς. Έχουν χρησιμοποιηθεί τα Για και Επανέλαβε Πάντα και Επανέλαβε Μέχρι. Επίσης τα Αν Τότε και Αν Τοτε Αλλιώς.
Βλέπουμε επίσης μεγάλη χρήση ετικετών (αναγνωριστικά με άνω κάτω τελεία στο τέλος τους, και μόνα τους στη γραμμή).

Επίσης χρησιμοποιείται η εντολή Άλλαξε (Swap) που δουλεύει μόνο για μεταβλητές, αλλάζοντας έναν εσωτερικό μοναδικό δείκτη. Επίσης το ++ και -=. Τις γενικές μεταβλητές τις καθαρίζουμε με μια εντολή την Καθαρό (προσοχή χωρίς μεταβλητές ως παραμέτρους..σβήνει όλες τις μεταβλητές, επίσης μπορεί να καθαρίσει και πίνακες..με μηδέν διάσταση)



Οθόνη 5, 0
Φόρμα 60,30
Πένα 14
Γενικές συγκρίσεις, αλλαγές
Συνάρτηση Getone$ {
      Διάβασε &buffer$, start1, end1 
\\    :  ? start1, end1      end1-=start1-1
      =Μεσ$(buffer$,start1,end1)
}
Συνάρτηση mxstrcmp {
      Διάβασε &Cmp$, start1,end1, start2,end2
      end1-=start1-1 \\ end=end-start+1
      end2-=start2-1
      hlp1$=Μεσ$(Cmp$,start1,end1)
      hlp2$=Μεσ$(Cmp$,start2,end2)
      =σύγκρινε(hlp1$,hlp2$) \\ μόνο μεταβλητές
      συγκρίσεις++
}
\\ Σε τυχαία σειρά, κανένα δεν είναι στη θέση του
\\ 10 συγκρίσεις - 7 αλλαγές
\\strSearch$ = "OneTwoThreeFourFive*"
\\Σειρά 1,4,7,12,16,20,0


\\ Είναι σε σωστή σειρά - 0 αλλαγές
\\ 8 συγκρίσεις - 0 αλλαγές
\\strSearch$ = "*FiveFourOneThreeTwo"
\\Σειρά 1,2,6,10,13,18,0
\\  Είναι σε φθίνουσα σειρά!
\\ 12 Συγκρίσεις - 9 αλλαγές
strSearch$ = "TwoThreeOneFourFive*"
Σωρός Νέος {
      Σειρά 1,4,9,12,16,20,0
   
      i=1 ' χρησιμοποιούμε πίνακες με βάση το 0 αλλά εδώ ξεκινάμε από το 1
      k=0
      Διάβασε startKeyWord
      Επανέλαβε {
            Πίνακας smarkerskt(i) \* αλλάζουμε μέγεθος χωρίς να σβήσουμε στοιχεία
            smarkerskt(k)=startKeyWord : i++
            Πίνακας emarkerskt(i) : Διάβασε startKeyWord
            Αν startKeyWord = 0 Τότε Έξοδος
            emarkerskt(k)=startKeyWord-1 : k++
      } Πάντα
}
emarkerskt(k)=len(strSearch$)
nKeywordskt=6
Πίνακας sortptrs(nKeywordskt) 'έχουμε ένα παραπάνω στοιχείο στη θέση 0
\* general form to fill array with a variable value
Τμήμα fillme {
      Διάβασε &ar()
      k=διάσταση(ar(),1) : i=0 : Επανέλαβε { ar(i)=i : i++ : k-- } Μέχρι k=0
}
fillme &sortptrs()
\\Διαμέσου αταξινόμητα
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
\\ θα προσθέσουμε ένα στοιχείο
Διαμέσου ΠρόσθεσεΈνα("George")
Καθαρο συγκρίσεις , αλλαγές
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
Διαμέσου ΠρόσθεσεΈνα("Hello")
Καθαρο συγκρίσεις , αλλαγές
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
Διαμέσου ΠρόσθεσεΈνα("1")
Καθαρο συγκρίσεις , αλλαγές
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
Διαμέσου ΠρόσθεσεΈνα("Zero")
Καθαρο συγκρίσεις , αλλαγές
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
Διαμέσου ΠρόσθεσεΈνα("Mark")
Καθαρο συγκρίσεις , αλλαγές
Διαμέσου στη_τάξη
Διαμέσου εδω_τυπώνουμε
\*

Έξοδος
αταξινόμητα:
      για i=1 έως nKeywordskt {
           Πένα 15 { Τύπωσε getone$( &strSearch$, smarkerskt(sortptrs(i-1)), emarkerskt(sortptrs(i-1))) }
      }
      Τύπωσε "Στοιχεία:";nKeywordskt
Επιστροφή
εδω_τυπώνουμε:
      \* Εδώ τυπώνουμε
      for i=1 to nKeywordskt {
      Πένα 15 { Τύπωσε getone$( &strSearch$, smarkerskt(sortptrs(i-1)), emarkerskt(sortptrs(i-1))) }
      }
      Τύπωσε "Έγινε"
      Τύπωσε "συγκρίσεις:";συγκρίσεις
      Τύπωσε "αλλαγές:";αλλαγές
      Τύπωσε "Πάτα Ένα Πλήκτρο, για να συνεχίσω"
      π$=κομ$
Επιστροφή
στη_τάξη:
      \* Εδώ είναι ο παλιός κώδικας - έχω βάλει την Άλλαξε για ευκολία!
      \* s5 και s6 είναι δείκτες για τον πίνακα που έχει τους δείκτες για την "μνήμη"
      \* όλες οι λέξεις είναι σε μια μνήμη (ένα αλφαριθμητικό) και παραμένουν ως έχουν
      s1 = nKeywordskt
      s2 = s1
      s3 = 0 : s4 = 0 : s5 = 0 : s6 = 0
      a = 0
   
      GP_SP_S1:
   
      s1 = int(s1 / 2)
      Αν s1 = 0 Τότε {
            Προς GP_SP_S5
      }
   
      s3 = s2 - s1
      s4 = 1
   
      GP_SP_S2:
      s5 = s4
   
      GP_SP_S3:
      s6 = s5 + s1
      \\? s1, s2,s3,s4
      \\? s5-1,s6-1
      a = mxstrcmp( &strSearch$, smarkerskt(sortptrs(s5-1)), emarkerskt(sortptrs(s5-1)), smarkerskt(sortptrs(s6-1)), emarkerskt(sortptrs(s6-1)))
      Αν a = 0 Τότε {
            Αν sortptrs(s5-1) < sortptrs(s6-1) Τότε {
                  a = -1
            } Αλλιώς {
                  a = 1
      }
      }
      Αν a <= 0 Τότε {
            Προς GP_SP_S4
      }
      Άλλαξε sortptrs(s5-1), sortptrs(s6-1)
      Αλλαγές++
      s5 = s5 - s1
   
      Αν s5 >= 1 Τότε {
            Προς GP_SP_S3
      }
   
      GP_SP_S4:
      s4 = s4 + 1
      Αν s4 > s3 Τότε {
            Προς GP_SP_S1
      }
      Προς GP_SP_S2
   
      GP_SP_S5:
      s1 = 0 \* απλά υπήρχε αυτό στο κώδικα!
Επιστροφή
Ρουτινα ΠρόσθεσεΈνα(strAdd$)
      Πένα 11 { Τύπωσε :Τύπωσε "Νέα λέξη:";strAdd$ }
      Πίνακας smarkerskt(nKeywordskt+1), emarkerskt(nKeywordskt+1) \\ αυξάνουμε τα στοιχεία χωρίς να σβήνουμε
      smarkerskt(nKeywordskt)=μήκος(strSearch$)+1
      emarkerskt(nKeywordskt)=smarkerskt(nKeywordskt)+μήκος(strAdd$)-1
      strSearch$=strSearch$+strAdd$
      Πίνακας sortptrs(nKeywordskt+1)
      sortptrs(nKeywordskt) =nKeywordskt
      nKeywordskt++
Τέλος Ρουτίνας




Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου