Hash Table 2.0 (αναθεώρηση 134)

Σε αυτή την αναθεώρηση διόρθωσε ένα θέμα με την εντολή ΣΤΟΚ.
Αυτή η εντολή κάνει διάφορες εργασίες με τους πίνακες. Όπως να βάζει τιμές σε μια περιοχή, ή να μετακινεί από πίνακα σε πίνακα ή στον ίδιο πίνακα τιμές..λογαριάζοντάς τον σαν μονοδιάστατο.
Υπήρχε ένα πρόβλημα όταν ο πίνακας ήταν εντός ομάδας (αντικείμενο) εντός στοιχείου πίνακα!

HashTable 2.0
Το παράδειγμα είναι ένας πίνακας κατακερματισμού όπως εδώ αλλά τώρα πιο ανώτερος. Το χρησιμοποιούμε για να αποφευχθεί η αναζήτηση με δυαδική ή σειριακή αναζήτηση. Ο χρόνος αναζήτησης είναι ο γρηγορότερος δυνατός και από τη δυαδική και από τη σειριακή αναζήτηση! Είναι σχεδόν σταθερός, και αυτό γιατί υπάρχουν περιπτώσεις που έχουμε σύγκρουση, όπως θα δούμε παρακάτω.

Στη προηγούμενη έκδοση χρησιμοποιούσα μια οριζόντια διάταξη, όπου η περίπτωση της σύγκρουσης, δηλαδή να μας δίνει η συνάρτηση κατακερματισμού ένα στοιχείο πίνακα που ήδη έχει δοθεί σε άλλο στοιχείο, αντιμετωπίζονταν με την μετάθεση προς τα άνω - και κυκλικά αν φτάναμε στο τέλος. Επιπλέον το πρόβλημα δυσκόλευε αν θέλαμε να διαγράψουμε στοιχείο, διότι τότε έπρεπε να γίνει rehash δηλαδή προσδιορισμό ξανά των θέσεων, άρα δημιουργία ενός νέου πίνακα. Δηλαδή το πέναλτι είναι μεγάλο! Παρόλα αυτά η αναζήτηση ήταν γρήγορη.

Στη σημερινή ανάρτηση έχουμε τον πίνακα κατακερματισμού έκδοση 2. Εδώ έχουμε μια άλλη προσέγγιση. Σε κάθε στοιχείο πίνακα (που δίνεται ο δείκτης του από τον υπολογισμό της συνάρτησης κατακερματισμού) θα γράψουμε μια λίστα στοιχείων. Ακόμα και αν ο πίνακας κατακερματισμού έχει 1 στοιχείο...θα μπορούμε να γράψουμε χιλιάδες νέα στοιχεία στη μια και μοναδική λίστα (απλά η συνάρτηση θα δίνει συνέχεια το στοιχείο αυτό, τη λίστα αυτή). Κάθε στοιχείο του πίνακα κατακερματισμού έχει ένα αντικείμενο! Αυτό το αντικείμενο μπορεί να μεγαλώνει ή να μικραίνει σε στοιχεία. Έτσι αν σβήσουμε ένα στοιχείο δεν χρειάζεται rehash. Ενώ λοιπόν στο παλιό κώδικα είχαμε μια συνάρτηση percentfull και έδειχνε πόσο επί τοις εκατό έχει χρησιμοποιηθεί, τώρα εδώ δεν έχει νόημα, αφού δεν έχουμε μονοδιάστατο πίνακα αλλά ουσιαστικά έναν δυο διαστάσεων με μεταβλητό αριθμών στοιχείων στην μια διάσταση, ανά στοιχείο της πρώτης!

Και σε αυτό το πρόγραμμα έχω βάλει τον ορισμό της κλάσης στο τέλος, και καλώ μια απλή ρουτίνα τη MyClass για να φτιάξει την κλάση (οι απλές ρουτίνες είναι σαν ο κώδικας να είναι ακριβώς στη θέση που καλούμε, ενώ οι ρουτίνες SUB END SUB, ότι δημιουργούν το διαγράφουν στην επιστροφή, άρα δεν θα μπορούσαμε να βάλουμε έναν ορισμό που θέλουμε να κρατήσουμε - ουσιαστικά στις ρουτίνες τύπου SUB μπορούμε μόνο νήματα να δημιουργήσουμε και να μείνουν γιατί αυτά έχουν αριθμό (handler) και όχι όνομα, δεν βρίσκονται δηλαδή σε λίστα ονομάτων)


Η νέα κλάση HashTable έχει τώρα δυο εσωτερικούς ορισμούς άλλων κλάσεων, του Item που γεμίζει το πίνακα κατακερματισμού και τον iterator το οποίο το θέλουμε και έξω από το αντικείμενο που θα φτιάξουμε για να μπορούμε να διερχόμαστε από όλα τα στοιχεία με σειρά ταξινόμησης. Η ταξινόμηση εδώ γίνεται με τον ίδιο τρόπο. Απλά η διαφορά είναι ότι στο παλιό πρόγραμμα στη διαγραφή δημιουργούσαμε όλο το πίνακα κλειδιών ξανά, ενώ τώρα σβήνουμε το κλειδί αυτόματα! Μάλιστα το Document είναι εσωτερικά συνδεδεμένη λίστα και έτσι η διαγραφή κλειδιού γίνεται άμεσα χωρίς αντιγραφές ή μετακινήσεις. Στη συνάρτηση Paragraph$() που κανονικά επιστρέφει την παράγραφο, αν δώσουμε τρίτη παράμετρο το -1 μας επιστρέφει την παράγραφο αλλά την διαγράφει κιόλας.  Επιπλέον πρέπει να διαγράψουμε και από το πίνακα στο αντικείμενο Item, τη γραμμή που γνωρίσουμε στο lastId και αυτό γίνεται με την Stock που κάνει αντιγραφή, και κάνουμε ένα redim (η dim είναι και redim preserve ταυτόχρονα στην Μ2000, αν δεν δώσουμε κάτι για αρχική τιμή). και έτσι πετάμε το τελευταίο στοιχείο!

Ο πίνακας data() που κρατάει τα item έχει οριστεί με αρχική τιμή κλάση. Αυτή είναι η περίπτωση που ο κώδικας των συναρτήσεων και τμημάτων της κλάσης γράφεται μια φορά στο πίνακα και χρησιμοποιείται από κάθε αντικείμενο στο πίνακα. Κάθε στοιχείο έχει το πίνακα και τις μεταβλητές μόνο. Αν δεν είχαμε δώσει αρχική τιμή τότε θα δίναμε το κάθε αντικείμενο και σε κάθε στοιχείο θα είχαμε όλο το κώδικα μαζί! Στη Μ2000 τα αντικείμενα δεν έχουν τύπο. Μόνη ευκολία είναι εδώ στο πίνακα που έχουμε κάνει κοινές συναρτήσεις και τμήματα. (παίζει κάτι ακόμα που δεν έχω αναφέρει γιατί δυσκολεύει το θέμα, τα αντικείμενα μπορούν να έχουν τοπικές μεταβλητές με μια έννοια "ιδιωτικές", έχει χρησιμοποιηθεί τέτοια μεταβλητή εδώ)

Ας δούμε τη μεγάλη εικόνα: Έχουμε ένα πίνακα που έχει σε κάθε στοιχείο μια ομάδα με άλλο πίνακα (και άλλα πράγματα, όπως μεταβλητές και συναρτήσεις, τμήματα). Θα μπορούσαμε να έχουμε αντί για ένα πίνακα αλφαριθμητικών στο Item έναν άλλο πίνακα με άλλο αντικείμενο!

Θα προσέξατε ότι χρησιμοποιώ μια Sort για το document sort1$. Αυτή είναι μια Quicksort που ταξινομεί μια συνδεδεμένη λίστα πολύ γρήγορα. Βασίζεται στην ρουτίνα που είχα δημοσιεύσει εδώ.

Αντί να έχουμε στο κώδικα τη κλάση HashTable, μπορούμε να την έχουμε σε ένα αρχείο έστω HashTable.gsb και βάζουμε μια εντολή:
Load HashTable

(η LOAD μπορεί να φορτώσει πολλά με το && αντί για κόμμα, γιατί το κόμμα χρησιμοποιείται για παραμέτρους κατά τη φόρτωση, για το τμήμα που θα τρέξει με τη φόρτωση.)

Flush
Linespace 0 : Window 12,0 : Linespace 30 : Form 84 : Pen 14 : Cls 1 : Back { Cls 1 }
Refresh 100
Report 2,"Hash Table ver2.0"
Gosub MyClass
Alfabeta=Hashtable(6) '' we can make 100 or 1000 or 10000 and time to read and write is the same
Alfabeta.ItemNew "Zorro The Great", "data123456"
Alfabeta.ItemNew "Black Smith", "data1334245", "Alexander III", "data345678"
Alfabeta.ItemNew "Singer Sofia", "data1313113" , "Panatha Maria", "data234234"
Print "Search Alfabeta key ";
Profiler
Print Alfabeta.Item$("Black Smith")
Print Timecount
Print Alfabeta.Item$("Panatha Maria")
Print "Search Alfabeta key ";
Profiler
Print Alfabeta.Item$("Alexander III")
Print Timecount
\Gosub CheckThis()
Gosub DisplayItem(0)
ok=Alfabeta.RemoveItem("Black Smith")
ok=Alfabeta.RemoveItem("Alexander III")
\Gosub CheckThis()
Gosub DisplayItem(0)
Alfabeta.Item "Panatha Maria", "Hello There"
Gosub DisplayItem(0)
Print Alfabeta.ExistItem("Panatha Maria")
Print Alfabeta.FastExistItem("Panatha Maria")
End
// Last part, Subs/Classes
Sub CheckThis()
	local i
	Report Alfabeta.sort1$
	For i=0 to Alfabeta.items-1
		For alfabeta.data(i) {
			Print i, .emp, .items,
			If not .emp Then Print .i$(0,0) Else print
		}
	Next
End Sub
Sub DisplayItem(x)
	local i,j, k$
	i=Alfabeta.Iterator()
	Print @(x),"Items:"; i.itemmax
	While i.NextItem()
		Aa$=i.key$()
		For Alfabeta {
			k$=.Item$(Aa$)
			j=.Hash(Aa$)
			Print @(x),i.item,") "+ Aa$, k$, j
		}
	End While
End Sub

// here is the lablel for Gosub
MyClass:
Class HashTable {
	item_no, items
	lasts$, spos
	newkey=True
	Document sort1$=""
	nl$={
	}
	dim data()
	Class Item {
		dim i$(1)
		items=0, LastId, Emp=True
		Module AddItem {
			dim .i$(.items+1, 2)
			Read .i$(.items,0), .i$(.items,1)
			.items++
			.Emp<=false
		}
		Function Findit {
			Read anykey$
			If .Emp Then exit
			= false
			For .Lastid<=.items-1 to 0
				If .i$(.Lastid,0)=anykey$ Then =true : exit for
			Next
		}
		Function Value$ {
			If .Emp Then error 10030
			=.i$(.Lastid,1)
		}
		Module Delone {
			If .lastid<=.items-2 Then
				Stock .i$(.lastid+1,0) Keep (.items-.lastid-1)*2, .i$(.lastid,0)
			End if
			.items--
			If .items=0 Then
				.emp<=True    //  need <= not =
				Dim .i$()
			Else
				dim .i$(.items, 2)
			End if
		}
	}
	Module HashTable {
		read .items
		A=.Item()
		Clear .sort1$
		Dim .data(.items)=A
	}
	Function F {
		read A, b
		b+=A*1024+A
		push binary.xor(b,0X83F3Cf)
	}
	Function Hash {
		Read Alfabeta$
		Push 0
		For i=1 to len(Alfabeta$)
		call .F(chrcode(mid$(Alfabeta$,i)))
		next
		=Binary.Or(Number, 0XAFFA0000+i*.items) mod .items
	}
	Module Item {
		.newkey<=false
		.ItemNew
		.newkey<=True
	}
	Module ItemNew {
		While match("SS")
			Read name$, data$
			name$=ucase$(name$)
			i=.Hash(name$)
			For this, this.data(i) {
				If ..Findit(name$) Then
					If .newkey Then Error 10010
					..i$(..lastid,1)=data$
				Else
					..AddItem name$, data$
					.sort1$<=name$+.nl$ : sort .sort1$,1, doc.par(.sort1$)-1
				End if
			}
		End While
	}
	Function Item$ {
		Read name$
		name$=ucase$(name$)
		For .data(.Hash(name$)) {
			If Not .Findit(name$) Then Error 10020
			=.value$()
		}
	}
	Function FastExistItem {
		over
		=.data(.Hash(ucase$(letter$))).Findit(ucase$(letter$))
	}
	Function ExistItem {
		If match("S") Then
			read .lasts$
			.lasts$ <= ucase$(.lasts$)
			.spos<=1
		End if
		Find .sort1$, .lasts$, .spos
		Read .spos
		If .spos=0 Else
			Read .item_no, c
			If match("N") Then read ok Else ok=false
			If ok Then
				.spos++ : =True
			Else.If c=1 Then
			.spos++ : =True
		End if
	   End if
	}
	Function ItemKey$ {
		Read No
		=Paragraph$(.sort1$,No)
	}
	Function ValidItems {
		=doc.par(.sort1$)-1
	}
	Function Iterator {
		group aa {
			item, itemmax
			ref$
			Function nextitem {
				.item++
				=.item<=.itemmax
			}
			Function key$ {
				If .item=0 Then error 101010
				= function$(.ref$.ItemKey$(), .item)
			}
		}
		aa.itemmax=.ValidItems()
		aa.ref$=&This
		=aa
	}	 
	Function RemoveItem {
		read Alfabeta$
		Alfabeta$=Ucase$(Alfabeta$)
		If .ExistItem(Alfabeta$) Then
			oldvalue$=paragraph$( .sort1$, .item_no, -1) ' remove line
			For .data(.Hash(Alfabeta$)) {
				If Not .Findit(Alfabeta$) Then exit
				.delone
				=True
		 	}
		End if
	}
}
Return