Αλγοριθμική ερώτηση

[imitheos]

Μια hash function θα δώσει πάντα όπως λες το ίδιο αποτέλεσμα ανεξάρτητα από το μέγεθος του table. Για παράδειγμα αν πάρουμε το "hello" που είπες και την πιο χαζή HF που απλά προσθέτει τους χαρακτήρες, αυτή θα δώσει πάντα αποτέλεσμα 72+101+108+108+111=500 ανεξάρτητα από το μέγεθος του table.

 

Συνήθως όμως σε απλές εφαρμογές για να μην έχουμε πολύ μεγάλα hash tables, είθισται να μην χρησιμοποιείται η πλήρης τιμή που επιστρέφει η HF αλλά να έχουμε μικρό hash table και να ανάγεται η τιμή που επιστρέφει η HF. Έτσι, ενώ η HF θα επιστρέφει πάντα 500, η λέξη "hello" σε ένα table με μέγεθος 100 θα καταχωρηθεί στην θέση 0 (500 % 100) ενώ σε table με μέγεθος 256 θα καταχωρηθεί στη θέση 244 (500 % 256). Υπό αυτή την έννοια παίζει ρόλο το μέγεθος του table.

 

Όλα αυτά φυσικά με το σκεπτικό ότι κατάλαβα σωστά αυτά που λέτε αλλιώς αγνοήστε με

[migf1]

...

Μήπως, λέω μήπως, η σελίδα του Virginia Tech απευθύνεται σε εντελώς αρχάριους και γι' αυτό το λόγο κάποια πράγματα τα εξηγεί στο περίπου και όχι τόσο technically correctly;

 

http://research.cs.v...ntroduction.php

 

Μπα, η ιδέα μου θα είναι.

 

Όχι δεν είναι ιδέα σου, είναι γνωστό πως εσύ τα ξέρεις όλα και πως τα Αμερικάνικα πανεπιστήμια διδάσκουν όχι τα technically correct που ξέρεις εσύ, αλλά απλοποιημένες αρλούμπες που δεν χρησιμοποιούνται πουθενά.

 

Δεν σου κάνει το Virginia Tech? Ορίστε και το Princeton που μάλιστα απαντάει ΑΚΡΙΒΩΣ στην ερώτηση του nik234 (εκείνο το απανταχού παρόν Μ είναι προφανώς απλοποιημένο, μη technically corrcet πράγμα που απευθύνεται σε εντελώς αρχάριους): http://algs4.cs.princeton.edu/34hash/

 

Ειλικρινά θα σου πρότεινα να διαβάσεις πρώτα ολοκληρωμένα όσα απευθύνονται σε εντελώς αρχάριους, πριν αρχίσεις να καταπιάνεσαι με και καλά technically correct για και καλά φτασμένους. Αν το κάνεις υπάρχει μια αμυδρή πιθανότητα να καταλάβεις πως το αν το size του πίνακα περνιέται ή όχι σαν όρισμα στην hash-function είναι τελειώς άσχετο με το αν χρησιμοπείται από την hash-function και άρα το αν επηρεάζει ή όχι το hashing μέσω της hash-function.

 

Πάρε κι άλλη μια μη technically correct "στο περίπου" αρλούμπα από το MIT...

 

http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-five/

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-7-hashing-hash-functions/

...

A good hash function should distribute the keys uniformly into the slots of the table and the regularity in the key distributions should not affect uniformity.

 

Two hash function creating methods are introduced - the division method, which defines h(k) = k mod m, and the multiplication method, where h(k) = (A·k mod 2w)>>(w-r), where w is bits in a word, A is an odd integer between 2w-1 and 2w, and r is lg(m).

...

[defacer]

Λοιπόν κάνοντας κλικ στο site του βιβλίου του Sedgewick έφαγα φλας και πήγα και άνοιξα το πρωτότυπο όπου επίσης λέει σαφώς:

 

The first step is to compute a hash function that transforms the search key into a table address.

 

Αυτό είναι ακριβώς το ίδιο πράγμα που λες και συ επομένως τα πράγματα είναι... δύσκολα για τη θέση μου μιας και ο Sedgewick συμφωνεί μαζί σου. Έχοντας φάει λοιπόν μια μεριδούλα humble pie αποσύρω το απόλυτο της τοποθέτησής μου.

 

Θα προσπαθήσω όμως να εξηγήσω το γιατί λέω αυτά που λέω με σκοπό να μην αφήσω λάθος εντυπώσεις.

 

Ξεκινάω λέγοντας πως όταν φαντάζομαι ένα hash table, αυτό που φέρνω στο μυαλό μου (σημαντικό: από ίδια επιλογή, όχι από ανάγκη) είναι ένας container που μπορεί να δεχτεί στοιχεία διαφορετικού τύπου ανάλογα με το configuration του (για το οποίο δε μπαίνω σε λεπτομέρειες για να είμαστε language-agnostic). Τα στοιχεία αυτά μπορεί να είναι primitives ή μπορεί και όχι (π.χ. ένας hashtable από αντικείμενα με user-defined type).

 

Σχετικά μ' αυτά ο Sedgewick λέει τα εξής:

 

Strictly speaking, we need a different hash function for each kind of key that might be used. For efficiency, we generally want to avoid explicit type conversion, striving instead for a throwback to the idea of considering the binary representation of keys in a machine word as an integer that we can use for arithmetic computations. [...]

 

Some high-level languages make it difficult to write programs that depend on how keys are represented on a particular computer, because such programs, by their very nature, are machine dependent and therefore are difficult to transfer to a new or different computer. Hash functions generally are dependent on the process of transforming keys to integers, so machine independence and efficiency are sometimes difficult to achieve simultaneously in hashing implementations.

 

Επιστώ την προσοχή ιδιαίτερα στην τελευταία πρόταση. Τι κρατάμε από όλα αυτά;

 

Πρώτον, αν θέλουμε να έχουμε ένα hash table που μπορεί να χρησιμοποιηθεί για αντικείμενα διαφορετικών τύπων τότε χρειαζόμαστε όχι μία και μόνη αλλά κατα πάσα πιθανότητα μία διαφορετική hash function για κάθε τύπο αντικειμένου που υποστηρίζεται. Και αυτό γιατί το να πούμε "ο,τι και να είναι θα το πάρω σαν bits", παρόλο που ακούγεται σαν μια χαρά πρώτη προσέγγιση, έχει σημαντικά μειονεκτήματα:

• δε μας επιτρέπει να αξιοποιήσουμε τυχόν γνώση που έχουμε για τη δομή των αντικειμένων
  
• τα αποτελέσματα αυτής της τεχνικής είναι machine dependent όπως λέει και ο Sedgewick
  
• υπάρχει περίπτωση η τεχνική να μην εφαρμόζεται καν σε ένα γενικό hash table -- για παράδειγμα στη C αν έχεις string keys (τύπου char*) τότε δε μπορείς να πεις "θα πάρω sizeof(char*) bytes για να βγάλω το hash" όπως μπορείς να κάνεις με όλους τους non-pointer τύπους
  

Είναι προφανές πως για να λυθεί ικανοποιητικά αυτό το πρόβλημα θα πρέπει να βάλουμε ένα abstraction layer ανάμεσα στο key και το hash tableμ και αυτό το layer είναι που είχα στο μυαλό μου μιλώντας για hash function νωρίτερα. Κάπως έτσι ορίζεται η hash function και στο Wolfram MathWorld:

 

A hash function H projects a value from a set with many (or even an infinite number of) members to a value from a set with a fixed number of (fewer) members.

 

Η hash function δηλαδή θα επιστρέφει μια τιμή σε ένα προκαθορισμένο ικανοποιητικό range και απο κει και πέρα ο χρήστης της hash function (δηλαδή εδώ το hash table) μπορεί να κάνει modulo ή οτιδήποτε άλλο σ' αυτή την τιμή για να την προσαρμόσει στις δικές του απαιτήσεις. Ακριβώς αυτό που γίνεται και με τους random number generators, και αυτό που συμβαίνει επίσης και με την GetHashCode() που ανέφερα παραπάνω.

 

Σ' αυτό το σημείο ελπίζω πως είναι κατανοητό το που εδράζεται η διαφωνία: όταν μιλάμε για ένα συγκεκριμένο hash table τότε δεν έχει νόημα να κάνουμε τις διακρίσεις στις οποίες επέμενα, όμως όταν μιλάμε για hash table σαν μια αφηρημένη έννοια τότε η hash function δεν είναι μία. Για να είναι δυνατή η χρήση οποιασδήποτε hash function με οποιοδήποτε είδος hash table λοιπόν θα πρέπει οι πολλές hash functions να έχουν το ίδιο interface (π.χ. δεν παίρνει καμία παράμετρο και επιστρέφει 32 bits).

 

Σ' αυτήν λοιπόν την περίπτωση το modulo ή όποια άλλη παρόμοια διαδικασία δεν είναι μέρος της hash function όπως την φαντάζομαι. Από την άλλη ακόμα κι ένα απλό modulo που παίρνει μια 32-bit τιμή και την βάζει στο [0, Ν] όπου Ν λογικό νούμερο ικανοποιεί επίσης τον ορισμό του Wolfram άρα είναι κι αυτό μια χαρά hash function από μόνο του.

 

Κλείνοντας λοιπόν ελπίζω ότι είναι κατανοητό το σκεπτικό μου και ζητώ συγγνώμη για το τσίτωμα των νεύρων που σε κανέναν μας δε χρειάζεται.

 

 

ΥΓ: Παρόλα αυτά, η επιλογή του μεγέθους του πίνακα εξακολουθεί να μην έχει σχέση με τη χρησιμοποιούμενη hash function, και αντίστροφα η επιλογή της hash function ("πάρε ένα string και δώσε μου το hash") γενικά μιλώντας δεν έχει σχέση με το μέγεθος του πίνακα για τους λόγους που αναλύω σε προηγούμενο post (load factor κλπ).

[migf1]

...

Κλείνοντας λοιπόν ελπίζω ότι είναι κατανοητό το σκεπτικό μου και ζητώ συγγνώμη για το τσίτωμα των νεύρων που σε κανέναν μας δε χρειάζεται.

 

Από μένα δεκτή

 

ΥΓ: Παρόλα αυτά, η επιλογή του μεγέθους του πίνακα εξακολουθεί να μην έχει σχέση με τη χρησιμοποιούμενη hash function, και αντίστροφα η επιλογή της hash function ("πάρε ένα string και δώσε μου το hash") γενικά μιλώντας δεν έχει σχέση με το μέγεθος του πίνακα για τους λόγους που αναλύω σε προηγούμενο post (load factor κλπ).

 

Οπότε συνεχίζεις να υποστηρίζεις πως για παράδειγμα αν επιλέξεις να κανεις variable string addition hashing στα strings σου δεν έχει απολύτως καμία σημασία στο efficiency του hashing αν ο πίνακάς σου θα έχει 256, 100 ή 3 slots.

 

Ή για παράδειγμα, συνεχίζεις να υποστηρίζεις πως η επιλογή ενός table με μέγεθος που είναι prime number ή δύναμη του 2 δεν έχει απολύτως καμία σχέση για το efficiency του hashing σου το αν η hash function είναι γραμμένη με τα παραπάνω ως δεδομένα ή όχι.

 

Σφάλλεις ξανά.

[defacer]

Οπότε συνεχίζεις να υποστηρίζεις πως για παράδειγμα αν επιλέξεις να κανεις variable string addition hashing στα strings σου δεν έχει απολύτως καμία σημασία στο efficiency του hashing αν ο πίνακάς σου θα έχει 256, 100 ή 3 slots.

 

Ή για παράδειγμα, συνεχίζεις να υποστηρίζεις πως η επιλογή ενός table με μέγεθος που είναι prime number ή δύναμη του 2 δεν έχει απολύτως καμία σχέση για το efficiency του hashing σου το αν η hash function είναι γραμμένη με τα παραπάνω ως δεδομένα ή όχι.

 

Θα παρακαλούσα για να συνεννοούμαστε να είσαι σαφής σχετικά με το τι εννοείς "efficiency του hashing". Έχοντας πει τόσα πολλά για τις hash functions νωρίτερα νομίζω ότι λέγοντας "hashing" θα έπρεπε να αναφερόμαστε στη λειτουργία της hash function αυτής καθαυτής, ενώ αν θέλουμε να αναφερθούμε στην απόδοση του hash table μπορούμε να πούμε "απόδοση του hash table" (ούτε το efficiency ούτε το hashing νομίζω πως ταιριάζουν εκεί). Οπότε which is it?

[migf1]

Θα παρακαλούσα για να συνεννοούμαστε να είσαι σαφής σχετικά με το τι εννοείς "efficiency του hashing". Έχοντας πει τόσα πολλά για τις hash functions νωρίτερα νομίζω ότι λέγοντας "hashing" θα έπρεπε να αναφερόμαστε στη λειτουργία της hash function αυτής καθαυτής, ενώ αν θέλουμε να αναφερθούμε στην απόδοση του hash table μπορούμε να πούμε "απόδοση του hash table" (ούτε το efficiency ούτε το hashing νομίζω πως ταιριάζουν εκεί). Οπότε which is it?

 

Δεν έχει σημασία which is it, το ίδιο πράγμα είναι, διότι η ουσία είναι πως οι hash functions κάνουν mapping, οπότε βρίσκονται εξ'ορισμού σε εξάρτηση με το μέγεθος του map (άλλοτε μικρότερη άλλοτε μεγαλύτερη).

 

Ακόμα κι εκείνες που έχεις αναφέρει πως δεν έχουν σχέση επειδή δεν σου ζητάνε το μέγεθος, δεν σου το ζητάνε γιατί internally κάνουν map το key σε συγκεκριμένο πλήθος bits.

[defacer]

Sorry αλλά δεν είναι καθόλου το ίδιο πράγμα. Ως "efficiency" της hash function θα μπορούσε να χαρακτηρίσει κανείς είτε την αλγοριθμική της πολυπλοκότητα είτε τη σταθερά αν μιλάμε π.χ. για μια O(n), ενώ ως "efficiency" του hash table θα μπορούσε να μιλήσει για τη μέση τιμή της σταθεράς του O(1) lookup κάτω από διάφορες συνθήκες.

 

Ρωτάω συγκεκριμένα γιατί σε καμία από τις προηγούμενες περιπτώσεις δε νομίζω πως ο όρος "efficiency" ταιριάζει μιας και α) αυτός γενικά έχει άλλη έννοια (φαντάσου βαθμός απόδοσης) και β) υπάρχουν άλλοι όροι για τα συγκεκριμένα πράγματα. Δεδομένου ότι πριν είχαμε ολόκληρη ιστορία η οποία είχε να κάνει καθαρά με θέμα ορολογίας μου φαίνεται κάπως το ότι τρία posts μετά έχουμε πετάξει την ορολογία στα σκουπίδια.

 

Τώρα όσον αφορά τα υπόλοιπα θα σου προτείνω να ξαναδιαβάσεις πιο προσεκτικά το κείμενο που παρέθεσες νωρίτερα. Η επιλογή του μεγέθους του πίνακα (το είχα υπογραμμίσει κιόλας) δεν έχει καμία σχέση με τη hash function -- όποιο κι αν είναι το μέγεθος αυτή τελικά θα το λάβει υπόψη για να βγάλει αποτέλεσμα αλλά μέχρι εκεί.

 

Επίσης η επιλογή της hash function στη γενικευμένη της εκδοχή (θα κάνεις πρόσθεση τα bytes του key? θα τα κάνεις xor μεταξύ τους? θα τα αντιμετωπίσεις σαν 4-byte unsigned ακέραιο σε BE αναπαράσταση? θα κάνεις κάτι άλλο?) φανερά δεν έχει καμία σχέση με το μέγεθος του πίνακα, άσχετα που μετά από (ή παράλληλα με) τα παραπάνω μπορεί να κάνεις ένα modulo. Εφόσον το μέγεθος του πίνακα είναι άγνωστο at compile time στη γενική περίπτωση, η επιλογή της hash function (η οποία θέλω να ελπίζω πως συμφωνούμε ότι δεν γίνεται at runtime) είναι φύσει αδύνατον να βασίζεται σ' αυτό.

 

Δε θέλω να προκαλέσω νέες συγκινήσεις αλλά μου δίνεις την εντύπωση ότι ή δεν έχεις διαβάσει προσεκτικά τα post μου ή δεν ξέρω και γω τι άλλο συμβαίνει.

 

 

Και το δικό μου παράπονο: στην αρχή του thread προτείνεις μεγέθη για τον πίνακα λαμβάνοντας υπόψη τα χαρακτηριστικά του κλειδιού, κάτι που όπως είπα παραπάνω είναι φάουλ. Από τη συνέχεια της κουβέντας αρχίζω να υποψιάζομαι πως αυτό το λάθος το κάνεις γιατί όπως εγώ θεωρούσα technically incorrectly ότι η hashf δεν έχει σχέση με το μέγεθος του πίνακα, κατ' αναλογία εσύ θεωρείς πως ντε και καλά πάνε πακέτο.

 

Θα ήθελα να μου απαντήσεις λοιπόν στο εξής: έστω ότι με την οποιαδήποτε μέθοδο προτιμάς επιλέγεις το μέγεθος του πίνακα Ν. Έρχομαι εγώ και σου φέρνω μια λίστα με Ν+1 keys να μπουν στον πίνακα. Τι θα πρέπει να γίνει;

 

Αν η απάντηση είναι "χωράνε γιατί θα μπουν σε λίστες" τότε α) λυπάμαι αλλά αυτό είναι implementation detail που δεν ισχύει στη γενική περίπτωση και β) μπορώ αντί για N + 1 να πω Ν * 1000.

 

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

 

Αν η απάντηση είναι άλλη είμαι περίεργος να την ακούσω.

 

 

[migf1]

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

 

Επαναλαμβάνω, οι hash functions είναι mapping functions, οπότε εξ'ορισμού βρίσκονται σε άμεση εξάρτηση από το μέγεθος του map.

 

Προσωπικά δεν έχω συναντήσει ποτέ, ούτε μια hash function που να μην χρησιμοποιεί το μέγεθος του map. Αν υπάρχει τέτοια hash-function πολύ ευχαρίστως να μου την γνωστοποιήσετε, αλλά και να υπάρχει (αδυνατώ να σκεφτώ πως είναι δυνατόν) σίγουρα δεν αποτελεί τον κανόνα.

 

Σχετικά με το efficiency τώρα, το ιδανικό hashing efficiency επιτυγχάνεται στο perfect hashing. Μιας και αυτό δεν είναι εφικτό στην γενική περίπτωση, καταφέυγουμε σε λύσεις με collisions.

 

Αφήνοντας έξω την κατανομή (όχι επειδή είναι ασήμαντη, αλλά επειδή ως έννοια έπεται της γενικής έννοιας hashing) όσο λιγοτερα collisions δημιουργήσουμε, τόσο πιο efficient είναι το hashing μας (αναφερομενος φυσικά στο γρήγορο data retrieval, που είναι και ο λόγος που κάνουμε hashing in the first place).

 

Εδώ λοιπόν παίζει ρόλο και το μέγεθος του πίνακα και η επιλογή της hash function, τα οποία επαναλαμβάνω βρίσκονται εξορισμού σε αλληλο-εξάρτηση... όχι όμως πάντα στον ίδιο βαθμό σε όλες τις περιπτώσεις.

 

Παίζει λοιπόν ρόλο το μέγεθος και η hash function, διότι για παράδειγμα (το κρατάω απλό για να καταλαβαίνουν και όσοι δεν έχουν ασχοληθεί) πες πως θέλουμε να κάνουμε hash αγνώστου πλήθους strings βάση του αρχικού τους χαρακτήρα.

 

Είναι προφανές πως αν χρησιμοποιήσουμε ως μέγεθος πίνακα όλο το ascii table (256 slots) θα εχουμε πολύ λιγότερα collisions από το αν τα ομαδοποιούσαμε π.χ. σε ομάδες 4 συνεχόμενων χαρακτήρων του ascii table (64 slots).

 

Μπορούμε φυσικά να ορίσουμε περισσότερα από 256 slots (ας πούμε 1000) και να υποστηρίξουμε πως δεν παίζει ρόλο το μέγεθος του πίνακα, αλλά κάτι τέτοιο πρoφανώς δεν στέκει (είναι σαν να λέμε πως χρειαζόμαστε να αποθηκεύσουμε το πολύ 5 πράγματα σε έναν πίνακα και να ορίζουμε τον πίνακα με 100 θέσεις).

 

Σε γενικές γραμμές λοιπόν, κι εφόσον είναι δεδομένο πως οι hash functions χρειάζονται το μέγεθος του πίνακα, πρέπει να επιλέξουμε το μέγεθος του πίνακα και την hash-function μας που το χρησιμοποιεί με τέτοιο τρόπο που θα μας δώσει τα ελάχιστα δυνατά collisions στο genral case, ή τέλος πάντως στον case που μας ενδιαφέρει περισσότερο.

 

Κατά κανόνα λοιπόν, αν οι πόροι μας επιτρέπουν perfect hashing, το κάνουμε και εχουμε maximum efficiency. Αν όχι, προσπαθούμε να κάνουμε το μέγεθος του πίνακά μας όσο το δυνατόν μεγαλύτερο και προφανώς μικρότερο του sizeof(perfect hashing) συνδυάζοντάς το με μια κατάληλη hash-function.

[defacer]

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

 

I beg to differ. Επίσης θα μπορούσες να μου κάνεις το χατήρι με τις ορολογίες προκειμένου να βγάλουμε συμπέρασμα στην κουβέντα, ακόμα κι αν δεν χρειάζονται όπως λες (χρειάζονταν μόνο μέχρι το σημείο που έχω λάθος στον ορισμό του τι είναι hash function και μετά τις ξεχνάμε? ελπίζω να μη με παρεξηγήσεις, αλλά περίμενα πιο συνεπή αντιμετώπιση).

 

Επαναλαμβάνω, οι hash functions είναι mapping functions, οπότε εξ'ορισμού βρίσκονται σε άμεση εξάρτηση από το μέγεθος του map.

 

Προσωπικά δεν έχω συναντήσει ποτέ, ούτε μια hash function που να μην χρησιμοποιεί το μέγεθος του map. Αν υπάρχει τέτοια hash-function πολύ ευχαρίστως να μου την γνωστοποιήσετε, αλλά και να υπάρχει (αδυνατώ να σκεφτώ πως είναι δυνατόν) σίγουρα δεν αποτελεί τον κανόνα.

 

Η επιλογή όμως της hash function δεν μπορεί να εξαρτάται από το μέγεθος του map. Αυτό λέω από την αρχή και πηγαίνουν τζάμπα τα underline μου.

 

Σχετικά με το efficiency τώρα, το ιδανικό hashing efficiency επιτυγχάνεται στο perfect hashing. Μιας και αυτό δεν είναι εφικτό στην γενική περίπτωση, καταφέυγουμε σε λύσεις με collisions.

 

Μόνο που δεν έχεις πει ακόμα τι είναι για σένα το hashing efficiency. Όταν είπα μήπως αυτό μήπως το άλλο η απάντησή σου ήταν πως περιπλέκω απλά πράγματα. Αν όμως κάνεις google "hashing efficiency" θα δεις ότι ο όρος δεν είναι ιδιαίτερα δόκιμος και επιπλέον στην πρώτη σελίδα όλες οι αναφορές είναι ακριβώς για τα πράγματα που ανέφερα: είτε για την ταχύτητα της hash function είτε για τη σταθερά του O(1) των lookups.

 

Κάνε λοιπόν τον κόπο να πεις τι είναι hashing efficiency για σένα (σήμερα είναι η μέρα που πρέπει να τα λέω πολλές φορές), αλλιώς δε νομίζω ότι μπορεί να γίνει συζήτηση πάνω σε οποιοδήποτε θέμα όταν μόνο ο ένας ξέρει ποιό είναι το θέμα.

 

Επίσης δεν απάντησες στην ερώτηση του spoiler.

 

Κατά κανόνα λοιπόν, αν οι πόροι μας επιτρέπουν perfect hashing, το κάνουμε και εχουμε maximum efficiency. Αν όχι, προσπαθούμε να κάνουμε το μέγεθος του πίνακά μας όσο το δυνατόν μεγαλύτερο και προφανώς μικρότερο του sizeof(perfect hashing) συνδυάζοντάς το με μια κατάληλη hash-function.

 

Είσαι σίγουρος ότι ξέρεις τι σημαίνει perfect hashing;

 

Όταν δεν μπορούμε να κάνουμε perfect hashing ποτέ δεν είναι γιατί δεν έχουμε πόρους (αν δεν είχαμε αρκετή μνήμη για perfect hashing τότε κανένας hash table για τον οποίο φτάνει η μνήμη δε θα μπορούσε να χωρέσει τα δεδομένα μας), αλλά γιατί στο perfect hashing πρέπει να ξέρεις από πριν το σύνολο των στοιχείων τα οποία θα κληθείς αργότερα να κάνεις hash. Αν έχεις μια perfect hash function h(x) όπου x ανήκει στο πεπερασμένο σύνολο S και της ταϊσεις κάποιο y εκτός του S τότε δεν ξέρω τι θα αποφασίσει να κάνει η h αλλά το μόνο σίγουρο είναι πως το perfect hashing πήγε περίπατο.

[migf1]

 

I beg to differ. Επίσης θα μπορούσες να μου κάνεις το χατήρι με τις ορολογίες προκειμένου να βγάλουμε συμπέρασμα στην κουβέντα, ακόμα κι αν δεν χρειάζονται όπως λες (χρειάζονταν μόνο μέχρι το σημείο που έχω λάθος στον ορισμό του τι είναι hash function και μετά τις ξεχνάμε? ελπίζω να μη με παρεξηγήσεις, αλλά περίμενα πιο συνεπή αντιμετώπιση).

 

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

 

Η επιλογή όμως της hash function δεν μπορεί να εξαρτάται από το μέγεθος του map. Αυτό λέω από την αρχή και πηγαίνουν τζάμπα τα underline μου.

 

Και σε ξαναρωτάω λοιπόν: η επιλογή της string variable addition hash function εξαρτάται ή όχι από το 256 ως μέγεθος του map;

 

Μόνο που δεν έχεις πει ακόμα τι είναι για σένα το hashing efficiency. Όταν είπα μήπως αυτό μήπως το άλλο η απάντησή σου ήταν πως περιπλέκω απλά πράγματα. Αν όμως κάνεις google "hashing efficiency" θα δεις ότι ο όρος δεν είναι ιδιαίτερα δόκιμος και επιπλέον στην πρώτη σελίδα όλες οι αναφορές είναι ακριβώς για τα πράγματα που ανέφερα: είτε για την ταχύτητα της hash function είτε για τη σταθερά του O(1) των lookups.

 

Κάνε λοιπόν τον κόπο να πεις τι είναι hashing efficiency για σένα (σήμερα είναι η μέρα που πρέπει να τα λέω πολλές φορές), αλλιώς δε νομίζω ότι μπορεί να γίνει συζήτηση πάνω σε οποιοδήποτε θέμα όταν μόνο ο ένας ξέρει ποιό είναι το θέμα.

 

Σαφώς και είπα, στο αμέσως προηγούμενο ποστ: data retrieval (αυτό που εσύ ονομάζεις lookups).

 

Επίσης δεν απάντησες στην ερώτηση του spoiler.

 

Διότι το έβαλες με edit, οπότε δεν υπήρχεί όταν διάβασα το ποστ σου.

 

Η απαντήση είναι: όποιο από τα 2 σε βολέυει καλύτερα. Κατά κανόνα, πολύ απλά έχεις collision , οπότε το χειρίζεσαι ως οποιοδήποτε άλλο collsision... δλδ το α) σου Αν έχεις επιλέξει συνειδητά να μη κάνεις allocate εξαρχής το expected maximum μέγεθος του πίνακα (είτε γιατί δεν το ξέρεις είτε γιατί είναι less probable είτε για οποινδήποτε άλλο λόγο, κάνεις το β) σου. Να σου βάλω κι ένα γ) εγώ, μπορείς ακόμα και να κάνεις rehash όλο το πίνακα, ακόμα και να αλλάξεις και την hash-function.

 

Ότι και να κάνεις όμως, θες δεν θες, το μέγεθος του πινακας σου είτε πριν είτε μετά θα το διαχιερίζεται η hash function σου. Mapping χωρίς γνώση του μεγέθους του map δεν γίνεται (να δω πόσες φορές ακόμα θα το γράψω ).

 

Είσαι σίγουρος ότι ξέρεις τι σημαίνει perfect hashing;

 

Όταν δεν μπορούμε να κάνουμε perfect hashing ποτέ δεν είναι γιατί δεν έχουμε πόρους (αν δεν είχαμε αρκετή μνήμη για perfect hashing τότε κανένας hash table για τον οποίο φτάνει η μνήμη δε θα μπορούσε να χωρέσει τα δεδομένα μας), αλλά γιατί στο perfect hashing πρέπει να ξέρεις από πριν το σύνολο των στοιχείων τα οποία θα κληθείς αργότερα να κάνεις hash. Αν έχεις μια perfect hash function h(x) όπου x ανήκει στο πεπερασμένο σύνολο S και της ταϊσεις κάποιο y εκτός του S τότε δεν ξέρω τι θα αποφασίσει να κάνει η h αλλά το μόνο σίγουρο είναι πως το perfect hashing πήγε περίπατο.

 

Σιγουρότατος! Εσύ; Τι θα πει έχεις μια perfect hash function και την ταίζεις ένα y εκτός εμβέλειας; Αν υπάρχουν y εκτός εμβέλειας με το οποία ενδέχεται να ταϊστεί η pf, πολύ απλά δεν ήταν perfect function εξαρχής.

 

Θα φτιάξεις δηλαδή μια pf για 8 bits και μετά θα αρχίσεις να την ταίζεις με 64bit και 128bit input data και θα πεις πως δεν είναι pf η συνάρτηση; To pf νοείται σε πεπερασμένο data set.

[defacer]

Για τα προηγούμενα δεν έχω διάθεση να συνεχίσουμε να "συζητάμε" (το μέγεθος του πίνακα το διαχειρίζεται η hash function? really? ο πίνακας το ξέρει? για κάποιο λόγο μου δίνεται η εντύπωση ότι όταν λέμε "hashtable" εσύ αντί να φέρεις στο μυαλό σου το abstract data type φέρνεις ένα element_type hashtable[N] και μερικές free functions), οπότε θα αρκεστώ σε αυτό:

 

Θα φτιάξεις δηλαδή μια pf για 8 bits και μετά θα αρχίσεις να την ταίζεις με 64bit και 128bit input data και θα πεις πως δεν είναι pf η συνάρτηση; To pf νοείται σε πεπερασμένο data set.

 

Δεν φτιάχνεις μια pf "για 8 bits". Φτιάχνεις μια pf για το σύνολο κλειδιών { 0x00, 0x01, ... 0xff }, από το οποίο στη γενική περίπτωση κάποια λείπουν. Όπως και δεν φτιάχνεις μια pf "για strings μέχρι 30 χαρακτήρες", αλλά μια pf για τα strings { "public", "private", "protected" }.

 

Σαφώς και το pf νοείται μόνο σε πεπερασμένο data set, αλλά δεν έχει νόημα να μιλάμε για perfect hashing επι π.χ. του συνόλου των 256 8-bit φυσικών αριθμών καθώς εκεί έχουμε ήδη όχι απλά perfect hashing αλλά επιπλέον minimal perfect hashing από τη μάνα του: κάθε αριθμός κάνει hash στον εαυτό του.

 

Εκεί που έχει νόημα το perfect hashing (και αυτό είναι που νομίζω ότι δεν έχεις υπόψη) είναι όταν θέλεις να κάνεις map π.χ. 10000 συγκεκριμένες 32-bit τιμές στα νούμερα [0, 9999] χωρίς κανένα collision. Αν ανάμεσα στις 10000 αυτές τιμές δεν υπάρχει π.χ. η 0xaabbccdd αλλά παρόλα αυτά εσύ την περάσεις στην hash function τότε το αποτέλεσμα αυτής μπορεί να είναι θεωρητικά οποιοδήποτε (undefined behavior σα να λέμε).

[migf1]

Δεν ξέρω για σένα, αλλα εγώ όλα αυτά τα έχω διδαχτεί επίσημα και τα έχω εξασκήσει κι επαγγελματικά στις αρχές. Δεν υποστηρίζω πως θυμάμαι τα πάντα με λεπτομέρειες, αλλά 100% θυμάμαι και ξέρω τα fundamentals, τα οποία προσπαθώ εδώ και 2-3 σελίδες να στα εξηγήσω με απλά λόγια.

 

Δεν θέλεις να τα δεχτείς, με γεια σου και χαρά σου. Δεν θα κάτσω όμως εγώ να σου "φυτέψω στο μυαλό" μέσα σε ένα φόρουμ τα hashing fundamentals.

 

Εφόσον όμως δεν είσαι εντελώς αρχάριος, και σου αρέσουν τα technically correct talks, σου έχω ένα πολύ ωραίο link για να κάτσεις να το ξεκοκκαλίσεις. Εγώ ευχαριστώ δεν θα πάρω (αφενός έχω ήδη πάρει και αφετέρου δεν το χρειάζομαι κιόλας). Δεν είναι από το δικό μου πανεπιστήμιο, είναι από το Carnegie Mellon (ακόμα καλύτερα δηλαδή)

 

Θα έχεις την ευκαιρία να μάθεις αν και πως εξαρτάται το μέγεθος του πίνακα από την hash function και το ανάποδο, όπως και το efficiency, καθώς επίσης και διάφορα άλλα για hash functions, universal & perfect hashing και τις αλληλοεξαρτήσεις τους... πιθανολογώ πως μπορεί να σου πέσει λίγο βαρύ ως ανάγνωσμα, αλλά δες το σαν μια ευκαιρία να πάρεις κάποιες στοιχειώδεις (και μη) βάσεις πάνω στο θέμα. Αν κι εφόσον ενδιαφέρεσαι, νομίζω θα σου είναι πολύ πιο χρήσιμο απο οποιαδήποτε Wikipedia, και .net ObjectGetHashCode methods

 

Καλή ανάγνωση: http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf

[defacer]

Η αλήθεια είναι πως επαγγελματίας χαρακτηρίζεται κάποιος που κινείται μ' αυτό τον τρόπο μόνο στην Ελλάδα όπου ο καθένας ξέρει τα πάντα στον τομέα του και οι υπόλοιποι δε μας ενδιαφέρει τι λένε.

 

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

 

Ευχαριστώ πολύ για την άπλετη γνώση που έχεις διαχύσει στο thread (και όχι μόνο σ' αυτό). Θα ήθελα πολύ να μπορούσα να έδειχνα την εκτίμησή μου έμπρακτα, αλλά εδώ στο forum το μόνο που μπορώ να κάνω είναι να εκχωρήσω την ιδιότητα μέλους στο private club (μόλις 2 μέλη, πιο private πεθαίνεις) που εγκαινίασε ο Star_Light.

 

So long, and thanks for all the fish.

[migf1]

Να 'σαι καλά! Ήρθε επιτέλους ο καιρός να βρεις κάποιον άλλον να πρήζεις, κάνοντας πως δεν καταλαβαίνεις τα αυτονόητα επί καμια 15αριά ποστς κάθε, μα κάθε φορά, μόνο και μόνο επειδή σου είναι αδύνατον να συμμετάχεις σε μια συζήτηση αποδεχομενος πως νομίζεις ότι ξέρεις, ενώ είναι ηλίου φαεινότερο πως δεν ξέρεις (τουλάχιστον όχι όσα νομίζεις ότι ξέρεις, ή θέλεις να δείξεις ότι ξέρεις).

 

Τους χαιρετισμούς μου στα fish.

 

Edit

 

Μιας και βλεπω πως του άρεσε και του imitheoy το ποστ σου, ας απαντήσει όποιος από τους 2 το θεωρεί σκόπιμο... το hashing του 1ου γράμματος ενός string βάση του ASCII code του σε ένα από τα 256 slots ενός hash-table είναι ή δεν είναι perfect hashing σε 8 bits?

 

Προφανώς είναι ρητορικό το ερώτημα. Κάντε εσείς hash το 5098765354 εκεί, και υποστηρίξτε μετά πως φταίει το perfect hashing.

[imitheos]

Εκτός και αν ήμουν εκτός θέματος, εγώ είπα τη γνώμη μου νωρίτερα. Συμφωνώ με τον defacer ότι η hash function αυτή καθεαυτή δεν έχει σχέση με το μέγεθος του πίνακα. Όσο μεγάλο πίνακα και να έχεις, το ίδιο αποτέλεσμα θα σου δώσει η HF απλά μερικές φορές σε βολεύει να το ανάγεις στο μέγεθος του πίνακα. Έτσι θα μπορούσα να πω ότι επηρεάζεται όντως το αποτέλεσμα από το μέγεθος του πίνακα αλλά αυτό δεν έχει σχέση με την ίδια την HF αλλά με το γεγονός ότι επιλέγουμε να χρησιμοποιήσουμε ένα μέρος της "ακρίβειας" της HF λόγω της αναγωγής.

 

Ακόμη περισσότερο συμφωνώ με τον defacer στο θέμα του να παρουσιάζονται "credentials" ως απόδειξη κάποιου επιχειρήματος. Μπορεί εγώ να παίζω μπάλα από το 1980 αλλά δεν με κάνει καλύτερο από τον Μέσι. "Δουλεύω σαν προγραμματιστής από το 1950" είναι χαζομάρα και μόνο στην Ελλάδα χρησιμοποιείται. Ή κάποιος έχει επιχειρήματα οπότε αυτά που λέει μιλάνε από μόνα τους ή δεν έχει επιχειρήματα και όσα credentials και να αναφέρει δεν θα του δώσουν δίκιο, ίσα ίσα τον προσβάλλουν. Ακούμε τέτοιες χαζομάρες από τους πολιτικούς στα παράθυρα. Ας μην τα κάνουμε και εμείς.