Δημιουργία hash function πολλαπλών τύπων

[gon1332]

Θα ήθελα να βγάλω μία hash value λαμβάνοντας υπόψιν τρία πεδία διαφορετικού τύπου μεταξύ τους:

• char (ή char *)
• 2 integers (pointers)

Σα μία γρήγορη σκέψη σκέφτηκα να τα κάνω όλα ένα string και να δουλέψω πάνω σε αυτό. Δε ξέρω όμως κατά πόσο θα με ωφελήσει αυτό για το λόγο που χρειάζομαι το hash table.

 

Αυτό που θέλω να κάνω είναι να υλοποιήσω τη λειτουργικότητα ενός DAG με hash table. Πιο συγκεκριμένα, το χρειάζομαι για την παράγωγή ενδιάμεσου κώδικα για compiler (είπα να μη χρησιμοποιήσω ένα απλό bin tree..θέλω να είμαι πιο κοντά στις βελτιστοποιήσεις).

 

Το πεδίο char (ή char *) θα περιέχει τον operator κάποιας έκφρασης, ενώ οι 2 pointers (προς κάποιο άλλο κόμβο) θα είναι το αριστερό και δεξί παιδί του operator (οι operands δηλαδή). Δε θέλω να έχω όλους τους κόμβους μαζεμένους σε λίγα buckets.

 

Πως θα μπορούσα να εκμεταλλευτώ όσο το δυνατόν περισσότερο τη δύναμη που δίνει ένα hash table;

 

Ό,τι βρήκα στο google είχε σχέση με ένα string ή κάποια αριθμητική τιμή, τα οποία είναι τετριμμένη γνώση.

(Δεν έχω εντρυφήσει στο θέμα του hashing, οπότε ευκαιρία να μάθω νέα πράγματα)

[defacer]

Τι εννοείς να υλοποιήσεις DAG με hashtable (και γιατί το λες DAG αφού είναι binary tree, και γιατί λες ότι δε θέλεις binary tree αφού ήδη έχεις binary tree)? Δεν καταλαβαίνω ποιός ο λόγος να βάλεις τα vertices μέσα σε ένα HT -- εφόσον ήδη έχεις ένα unique key για το κάθε vertex (το pointer σ' αυτό) το μόνο πράγμα που θα έκανε ένα HT θα ήταν να σου επιτρέψει να βρίσκεις "όμοιους" vertices που είναι όμως διαφορετικά instances. Αλλά αυτό δεν είναι δυνατόν να συμβαίνει γιατί τα vertices σου έχουν pointer σε άλλα, οπότε δε μπορούν ποτέ να είναι όμοια όντας διαφορετικά instances εκτός αν έχεις όντως DAG αντί για tree (δε φαίνεται να ισχύει αυτό, αν ίσχυε τότε πώς ξέρεις ότι είναι όντως DAG και δεν έχει cycles?) ή αν ο έλεγχος ομοιότητας είναι recursive και κάνει follow pointers -- περίπτωση η οποία είναι καθαρά θεωρητική και μη εφαρμόσιμη στην πράξη.

 

Am I missing something?

[DeltaLover]

Εδω μπορεις να βρει; μια αριστη περιγραφη του hashing.

 

 

 

Επισης μην σκεφτεις να ασχοληθεις με compilers αν δεν μελετησεις αυτο:

 

 

Δες κι αυτα:

http://www.diku.dk/~torbenm/Basics/basics_lulu2.pdf

 

http://www.bayfronttechnologies.com/metacompilers1.pdf

 

Online course απο το Stanford, αρχιζει στις 17 Μαρτη:

 

https://www.coursera.org/course/compilers

 

 

 

Επισης μην ξεχνας ποτε την παρακατω μεγαλη αρχη:

 

Premature optimization is the root of all evil

 

ΑΝ θελεις πες μας λιγο παραπανω για το project σου.  Τι ειναι αυτο που σε κανει να θελεις να γραψεις εναν compiler? Αν ειναι homework το καταλαβαινω, αλλιως δεν νομιζω ειναι καλη ιδεα

Επεξ/σία 5 Μαρτίου 2014 από DeltaLover

[gon1332]

Τι εννοείς να υλοποιήσεις DAG με hashtable (και γιατί το λες DAG αφού είναι binary tree, και γιατί λες ότι δε θέλεις binary tree αφού ήδη έχεις binary tree)? Δεν καταλαβαίνω ποιός ο λόγος να βάλεις τα vertices μέσα σε ένα HT -- εφόσον ήδη έχεις ένα unique key για το κάθε vertex (το pointer σ' αυτό) το μόνο πράγμα που θα έκανε ένα HT θα ήταν να σου επιτρέψει να βρίσκεις "όμοιους" vertices που είναι όμως διαφορετικά instances. Αλλά αυτό δεν είναι δυνατόν να συμβαίνει γιατί τα vertices σου έχουν pointer σε άλλα, οπότε δε μπορούν ποτέ να είναι όμοια όντας διαφορετικά instances εκτός αν έχεις όντως DAG αντί για tree (δε φαίνεται να ισχύει αυτό, αν ίσχυε τότε πώς ξέρεις ότι είναι όντως DAG και δεν έχει cycles?) ή αν ο έλεγχος ομοιότητας είναι recursive και κάνει follow pointers -- περίπτωση η οποία είναι καθαρά θεωρητική και μη εφαρμόσιμη στην πράξη.

 

Am I missing something?

 

Γιατί DAG και όχι binary tree (το DAG είναι ας πούμε ένα συμπυκνωμένο binary tree):

Έχουμε την έκφραση: i = i + 10

binary tree:        DAG:

       =             =
      / \           / \
     /   +         (   +
    i   / \         \ / \
       i  10         i  10

όπως βλέπεις με τα DAGs ένα κόμβος μπορεί να έχει πολλούς πατέρες.

 

Το search στο hash table θα γίνεται αρχικά με βάση το hash(<char *, pointer, pointer>), και αφού βρεθεί το bucket, θα ψάχνω με βάση μία αριθμητική τιμή που θα έχει λάβει κατά την εισαγωγή ο κάθε κόμβος. Η διασφάλιση από κύκλος θα γίνεται κατά την εισαγωγή κόμβων: addNode(<char *, pointer, pointer>).

Σημείωση: Οι pointers που λέω θα μπορούσαν να είναι οι αντίστοιχες αριθμητικές τιμές άλλων κόμβων. Δεν κολλάμε εκεί.

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

 

Γιατί hash table: Φαντάσου ένα πρόγραμμα πολλών γραμμών να είναι αποθηκευμένο στη μνήμη σα δένδρο. Για να ψάξω κάποιο φύλλο θα έπρεπε να ψάξω βαθιά. Επίσης τα πράγματα χειροτερεύουν σε μη-ισοζυγισμένα δένδρα. Αντιθέτως, σε ένα hash table, η πληροφορία κατανέμεται δίκαια, όποτε κάθε λίστα (bucket) περιέχει το ίδιο περίπου αριθμό κόμβων. Επίσης αν δε βρω κάποιο κόμβο σε ένα bucket, τότε για κανένα λόγο δε θα βρίσκεται σε κάποιο άλλο.

 

Επίσης ένας γνωστός τρόπος αναπαράστασης γραφημάτων είναι οι adjacency lists, οι οποίες μοιάζουν με τη δομή των hash tables. Οπότε ορίστε ένα άλλο κίνητρο.

 

Επισης μην σκεφτεις να ασχοληθεις με compilers αν δεν μελετησεις αυτο: ΜΕΤΑΓΛΩΤΤΙΣΤΕΣ: Αρχές, Τεχνικές & Εργαλεία

 

Αυτό χρησιμοποιώ σε συνδυασμό με αυτό των Σκορδαλάκη και Παπασπύρου. Λίγο μπέρδεμα η ελληνική έκδοση αλλά τελος πάντων.

 

Αυτό μάλιστα προτείνει DAGs με hash tables.

 

Γενικά δεν κολλάω στην υλοποίηση της όλης δομής. Στο hash function κολλάω (είναι όλη η δομή ). Θέλω να μάθω πως να κάνω hashing με τέτοιο τρόπο ώστε να μη μου τυναχτεί η δομή στον αέρα.

 

Εργασία είναι. Δε μας ζητά να τα κάνουμε έτσι, απλά είναι ένας τομέας που με ενδιαφέρει σοβαρά και προσπαθώ να λάβω όση περισσότερη γνώση μπορώ από αυτή.

 

 

EDIT:

Έχουμε την έκφραση: i = i + 10

binary tree:        DAG:            DAG με πίνακα (Λόγω χώρου και χρόνου προτιμούμε HTs):
                            αριθμητική τιμή| op :l_c:r_c|
                            ---------------+----+---+---+
       =             =                    1| id :   ------> pointer to i
      / \           / \                   2| num:  10   |
     /   +         (   +                  3|  + : 1 : 2 |
    i   / \         \ / \                 4|  = : 1 : 3 |
       i  10         i  10                5|     ...    |

[defacer]

όπως βλέπεις με τα DAGs ένα κόμβος μπορεί να έχει πολλούς πατέρες.

 

Πέρασε απαρατήρητο πριν εκεί που λες για compiler, τώρα κατάλαβα τι παίζει...

 

Το search στο hash table θα γίνεται αρχικά με βάση το hash(<char *, pointer, pointer>), και αφού βρεθεί το bucket, θα ψάχνω με βάση μία αριθμητική τιμή που θα έχει λάβει κατά την εισαγωγή ο κάθε κόμβος.

Γιατί τότε pointer, pointer αντί για id, id αφού ήδη θα έχεις ids? (άκυρο, το λες παρακάτω, "δεν κολλάμε εκεί").

 

Επίσης όταν λες char* για το είδος του node, εξυπακούγεται πως αυτοί οι char* θα δείχνουν σε κάποιου είδους interned strings (αφού διαφορετικά μπορεί τα strings να είναι ίδια αλλά οι char* να διαφέρουν). Αλλά αν τα strings είναι interned τότε το καθένα θα μπορούσε να αναπαρασταθεί με ένα μοναδικό id σαν enum ας πούμε. Επομένως γιατί όχι some-other-id κι εκεί αντί να μπερδεύεσαι με char*?

 

Επομένως αν τελικά καταλήξουμε σε 3 ints για το tuple σου μια απλή και ΟΚ λύση είναι η εξής:

1. Επιλέγεις τον πρώτο αριθμό (some-other-id) έτσι ώστε οι τιμές του να μην είναι όλες μικρές (1, 2, 3, 4, 5). Αφού μιλάμε για node type έχεις την ευχέρεια να τις επιλέξεις όπως θες.
2. Επιλέγεις έναν πρώτο P που να μην είναι πολύ μικρός, κάτι με 3-5 ψηφία θα είναι ΟΚ.
3. hash = (((a * P) ^ b ) * P) ^ c όπου ^ είναι xor, πρόκειται στην ουσία για πολύ κλασικό αλγόριθμο (π.χ. μια παραλλαγή χρησιμοποιείται στα strings της java με P = 31 και πρόσθεση αντί για xor)

Όπως και να 'χει μπορείς να κάνεις instrument το hash table σου για να ξέρει ποιό είναι το average και max bucket size, οπότε μπορείς να βάλεις ένα check ότι αν το max γίνει π.χ. μεγαλύτερο του max(2, load factor = average) * 3 ίσως κάτι πάει στραβά με το hash σου και θα πρέπει να το ξαναδείς (average * 3 έχει επιλεχθεί ως "μη-παράλογο" και 2 * 3 = 6 ως ανάξιο λόγου μήκος για sequential search).

[gon1332]

Ευχαριστώ για τις ιδέες! Το enum φαίνεται καλή λύση.

 

(Απλά θα πέσει χαμαλοδουλειά για τη μεταφορά όλων των operations σε enum. Έχουμε και high/low case υποστήριξη ) ------> πετάω κοτσάνες νυχτιάτικα!! Πάω για ύπνο.

 

Επίσης ευχαριστώ για το hash function. Θα ξεκινήσω δουλειά από αύριο!

[geomagas]

ΑΝ θελεις πες μας λιγο παραπανω για το project σου.  Τι ειναι αυτο που σε κανει να θελεις να γραψεις εναν compiler? Αν ειναι homework το καταλαβαινω, αλλιως δεν νομιζω ειναι καλη ιδεα

Γιατι;;;

[DeltaLover]

Γιατι;;;

 

Γιατ το βλεπω κομματακι δυσκολο...  Εσυ γραφεις συχνα compilers?

[geomagas]

Όχι πολύ συχνά...

Αλλά από το "δύσκολο" μέχρι το "δεν είναι καλή ιδέα", υπάρχει τεράστια απόσταση.

Στο κάτω-κάτω, μερικές από τις καλύτερες ιδέες όλων των εποχών αφορούσαν "δύσκολα πράγματα"...

[Erevis]

Δε το καταλαβαίνω αυτό το "κομματάκι δύσκολο". Δε νομίζω ότι ο καθένας που ξεκινάει να ασχολείται με τους compilers κάνει κατευθείαν contribute στον gcc, οπότε αν θέλει κάποιος να ασχοληθεί με αυτό από κάπου πρέπει να ξεκινήσει.

[DeltaLover]

Δε το καταλαβαίνω αυτό το "κομματάκι δύσκολο". Δε νομίζω ότι κανένας ξεκινάει να ασχολείται με τους compilers κάνοντας κατευθείαν contribute στον gcc, οπότε αν θέλει κάποιος να ασχοληθεί με αυτό από κάπου πρέπει να ξεκινήσει.

 

Περαν απο του να δεις πως γραφεται, για εκπαιδευτικους κυριως λογους, η κατασκευη ενος commersial quality compiler απαιτει πολυ εξεζητημενες γνωσεις σε επιπεδο PHD, καθως και την συνεργασια ομαδας ειδικων που να συνδιαζουν αρκετες επιμερους ειδικοτητες.

 

Δεν λεω οτι ειναι αδυνατο να τον γραψει καποιος μονος του, και χωρις τα απαιτουμενα skills, απλα αυτο που θα καταφερει θα ειναι κατα πολυ κατωτερο απο τους υπαρχοντες επαγγελματικους compilers. 

 

Για τον ιδιο ακριβως λογο  δεν γραφουμε δικα μας λειτουργικα συστηματα, relational databases, nosql db κλπ αλλα χρησιμοποιουμε λυσεις που συμπυκνωνουν εμπειρια και δουλεια χιλιαδων engineer years...

 

Περαν αυτου, βεβαια βλεπω απολυτα χρησιμη και εφικτη την δημιουργια DSLs τα οποια θα χτιστουν πανω σε  εργαλεια οπως c++, ruby, haskell η κατι αλλο παρομοιο...

[Erevis]

No shit Sherlock...

 

Δε καταλαβαίνεις πως για να ξεκινήσει κάποιος να μαθαίνει κάτι πρέπει συνήθως να ξεκινήσει από χαμηλά? Προφανώς και αυτό που θα φτίαξει δε θα το πουλήσει 100.000.000.000$ στο DoD. 

 

Το να λες σε κάποιον που θέλει να ασχοληθεί με compilers να το αφήσει καλύτερα γιατί δε θα φτιάξει τον gcc ή τον clang ξερω γω, είναι σαν να λες στον υποψήφιο web developer να μην φτιάξει εκπαιδευτικά μια sample σελίδα επείδη δε θα είναι το Facebook.

[gon1332]

 

Το να λες σε κάποιον που θέλει να ασχοληθεί με compilers να το αφήσει καλύτερα γιατί δε θα φτιάξει τον gcc ή τον clang ξερω γω, είναι σαν να λες στον υποψήφιο web developer να μην φτιάξει εκπαιδευτικά μια sample σελίδα επείδη δε θα είναι το Facebook.

 

Oι βελτιστοποιήσεις σε LLVM είναι project-άκι για αυτό το εξάμηνο σε άλλο μάθημα Compilers.

[DeltaLover]

No shit Sherlock...

 

Δε καταλαβαίνεις πως για να ξεκινήσει κάποιος να μαθαίνει κάτι πρέπει συνήθως να ξεκινήσει από χαμηλά? Προφανώς και αυτό που θα φτίαξει δε θα το πουλήσει 100.000.000.000$ στο DoD. 

 

Το να λες σε κάποιον που θέλει να ασχοληθεί με compilers να το αφήσει καλύτερα γιατί δε θα φτιάξει τον gcc ή τον clang ξερω γω, είναι σαν να λες στον υποψήφιο web developer να μην φτιάξει εκπαιδευτικά μια sample σελίδα επείδη δε θα είναι το Facebook.

 

Φυσικα ετσι ειναι.

 

Για αυτο το ξεκαθαρισα απ την αρχη..  Αν ειναι για εκπαιδευτικους λογους, ασφαλως και ειναι χρησιμο να καταλαβεις πως γραφεται ενας compiler. Αν ομως προσπαθεις να δωσεις μια επαγγελματικη λυση, νομιζω θα πρεπει να το ξανασκεφτεις...

[gon1332]

Αν ομως προσπαθεις να δωσεις μια επαγγελματικη λυση, νομιζω θα πρεπει να το ξανασκεφτεις...

 

Δε χρειάζεται να κάνεις κάτι μόνο για να ανταγωνιστείς τα ήδη υπάρχοντα εργαλεία (compilers εδώ).

 

Έστω ότι θέλεις να σχεδιάσεις το δικό σου σύστημα που θα τρέχει σε fpga, embedded κλπ, και δε θέλεις να το παρακάνεις με τις αρχιτεκτονικές που υπάρχουν, οπότε φτιάχνεις μία πιο μικρή efficient αρχιτεκτονική και πάνω σε αυτή χτίζεις το δικό σου ISA και μετά τη δική σου μικρή γλώσσα. Έτσι πλέον μπορείς να φτιάξεις το δικό σου mini λειτουργικό σύστημα και τις εφαρμογές με τη νέα αυτή γλώσσα. Και όλο αυτό θα είναι ένας υπολογιστής σε μέγεθος μεγάλου κινητού τηλεφώνου...

 

Μπορείς να βρεις πολλές εφαρμογές...