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

[migf1]

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

 

Μπορείς να δώσεις μερικά παραδείγματα που η hash-function δεν αναγάγει το key σε μέγεθος πίνακα; Αυτή η "ακρίβεια" στην οποία αναφέρεσαι τι ακριβώς έχει ως σημείο αναφοράς (δηλαδή είναι περισσότερο ή λιγότερο "ακριβής" σε σχέση με τι; )

 

 

 

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

 

Όταν επί 10 ποστς (και επί καμια δεκαριά νήματα ανεξαρτήτως θέματος) εξηγείς με όλους τους πιθανούς κι απίθανους, τρόπους, με ή χωρίς links (σχεδόν πάντα με) με ή χωρίς κώδικα (50-50) πως η αλφάβητος ξεκινάει από το Α και έχεις απέναντί σου μονίμως τον ίδιο άνθρωπο να προσπαθεί να σε βγάλει "τρελό" (discredit των πηγών, technically incorrect και άλλα τέτοια όμορφα, υπονοώντας σαφως πως αυτά που λέει εκείνος είναι -και καλά- ανωτέρου επίπεδου), τότε τα ορια προσβολής και υποτίμησης της νοημοσύνης έχουν ξεπεραστεί προ πολλού.

 

 

Επεξ/σία 10 Δεκεμβρίου 2012 από migf1

[imitheos]

 

 

Μπορείς να δώσεις μερικά παραδείγματα που η hash-function δεν αναγάγει το key σε μέγεθος πίνακα; Αυτή η "ακρίβεια" στην οποία αναφέρεσαι τι ακριβώς έχει ως σημείο αναφοράς (δηλαδή είναι περισσότερο ή λιγότερο "ακριβής" σε σχέση με τι; )

 

 

 

 

 

Όταν επί 10 ποστς (και επί καμια δεκαριά νήματα ανεξαρτήτως θέματος) εξηγείς με όλους τους πιθανούς κι απίθανους, τρόπους, με ή χωρίς links (σχεδόν πάντα με) με ή χωρίς κώδικα (50-50) πως η αλφάβητος ξεκινάει από το Α και έχεις απέναντί σου μονίμως τον ίδιο άνθρωπο να προσπαθεί να σε βγάλει "τρελό" (discredit των πηγών, technically incorrect και άλλα τέτοια όμορφα, υπονοώντας σαφως πως αυτά που λέει εκείνος είναι -και καλά- ανωτέρου επίπεδου), τότε τα ορια προσβολής και υποτίμησης της νοημοσύνης έχουν ξεπεραστεί προ πολλού.

 

 

 

>
   unsigned long
   hash(unsigned char *str)
   {
       unsigned long hash = 5381;
       int c;

       while (c = *str++)
           hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

       return hash;
   }

 

Ορίστε η κλασική του Bernstein ως παράδειγμα. Στο προηγούμενο μήνυμά μου ανέφερα την ακόμη πιο χαζή έκδοση που απλά προσθέτει τους χαρακτήρες χωρίς να δίνει σημασία στη σειρά τους και είπα ότι θα δίνει αποτέλεσμα 500 για το string "Hello". Η djb2 που αναφέρω τώρα θα δώσει ακόμη πιο τεράστιο αριθμό. Εσύ λοιπόν δεν μπορείς και δεν θέλεις να εκχωρήσεις μνήμη για ένα τόσο τεράστιο αριθμό καταχωρήσεων οπότε εκχωρείς μέγεθος πχ το 256 που αναφέρθηκε και μετά ανάγεις την τιμή της HF στο 256. Αυτό εννοώ ότι μειώνεις την ακρίβειά της. Το γεγονός όμως ότι εσύ επιλέγεις να ανάγεις την τιμή σε ένα μικρότερο εύρος δεν σημαίνει ότι η ίδια η HF εξαρτάται από το μέγεθος του hash table.

[migf1]

 

 

 

>
   unsigned long
   hash(unsigned char *str)
   {
       unsigned long hash = 5381;
       int c;

       while (c = *str++)
           hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

       return hash;
   }

 

 

 

Ορίστε η κλασική του Bernstein ως παράδειγμα. Στο προηγούμενο μήνυμά μου ανέφερα την ακόμη πιο χαζή έκδοση που απλά προσθέτει τους χαρακτήρες χωρίς να δίνει σημασία στη σειρά τους και είπα ότι θα δίνει αποτέλεσμα 500 για το string "Hello". Η djb2 που αναφέρω τώρα θα δώσει ακόμη πιο τεράστιο αριθμό. Εσύ λοιπόν δεν μπορείς και δεν θέλεις να εκχωρήσεις μνήμη για ένα τόσο τεράστιο αριθμό καταχωρήσεων οπότε εκχωρείς μέγεθος πχ το 256 που αναφέρθηκε και μετά ανάγεις την τιμή της HF στο 256. Αυτό εννοώ ότι μειώνεις την ακρίβειά της. Το γεγονός όμως ότι εσύ επιλέγεις να ανάγεις την τιμή σε ένα μικρότερο εύρος δεν σημαίνει ότι η ίδια η HF εξαρτάται από το μέγεθος του hash table.

 

Tο 33 και το << 5 γιατί υπάρχουν, γνωριζεις;

 

Θα δώσω link και πάλι, ελπίζω να μην προσβληθείτε... απλώς δεν έχω το κουράγιο να γράφω πάλι τα ίδια:

 

http://www.strchr.com/hash_functions

 

Όταν έχεις όρεξη και χρόνο ρίξε του μια ματιά. Αναλύει και την Bernstein (η οποία κατά κανόνα κάνει map το str σε 32 bits... αυτό είναι το μέγεθος του πίνακα).

 

Το αν εσύ θα το αναγάγεις εκ νέου σε άλλον πίνακα, δεν σημαίνει σε καμία περίπτωση πως η hash-function δεν κάνει πρωτογενή αναγωγή του key σε κάποιο μέγεθος.

[migf1]

 

 

 

Βάζω αυτό το ποστ σε spoiler γιατί είναι off-topic. Το δημοσιεύω με αφορμή τη δική σου παράθεση, αλλά αναφέρομαι κυρίως στον defacer. Και το κάνω συνειδητά με αφορμή τη δική σου παράθεση, αφενός επειδή απάντησες σε δική μου ερώτηση, αλλά κυρίως επειδή σχεδόν πάντα "πατρονάρεις" τον defacer όταν παίρνεις θέση σε διαμάχες μεταξύ εμένα και του defacer.

 

...

Ή κάποιος έχει επιχειρήματα οπότε αυτά που λέει μιλάνε από μόνα τους ή δεν έχει επιχειρήματα και όσα credentials και να αναφέρει δεν θα του δώσουν δίκιο, ίσα ίσα τον προσβάλλουν. Ακούμε τέτοιες χαζομάρες από τους πολιτικούς στα παράθυρα. Ας μην τα κάνουμε και εμείς.

...

 

Ελπίζω μετά από το τελευταίο ποστ, σχετικά με την Bernstein (αλλά όχι μόνο) να έχεις αναθεωρήσει το παραπάνω, αναφορικά δηλαδή με το ποιανού τα επιχειρήματα στέκουν και μιλάνε από μόνα τους, ποιανού δεν στέκουν, ποιανού τα επιχειρήματα προσβάλλουν, καθώς και ποιον, πότε και ποιους προσβάλλουν οι αναφορές σε "credentials", κλπ.

 

Για να σου "μιλήσουν" από μόνα τους τα επιχειρήματα (με ή χωρίς credentials) πρέπει να έχεις ήδη μια στοιχειώδη εξοικείωση με τις βασικές αρχές που τα διέπουν ώστε να είσαι σε θέση να αξιολογήσεις τα επιχειρήματα που διαβάζεις (και κρίνεις/κατακρίνεις). Το να αρνείσαι να δεχτείς τις βασικές αρχές από κάποιον που τις ξέρει και προσπαθεί να στις μεταφέρει, το να αρνείσαι να τις μάθεις μόνος σου αν δεν τις ξέρεις, το να αρνείσαι να παραδεχτείς πως δεν τις ξέρεις, κλπ, οδηγεί με μαθηματική ακρίβεια σε γραφικές καταστάσεις. Το να προσπαθείς μάλιστα με υφάκι, ειρωνία και αφελή επιχειρήματα & αερολογίες τύπου "η τάδε μέθοδος του .net δεν ζητάει ως όρισμα το map, άρα δεν ξέρεις τι λες" για να καλύψεις την αμάθειά σου (ή έστω την ημιμάθειά σου) προκειμένου να δείξεις περισπούδαστος, ξεπερνάει ακόμα και τα όρια της γραφικότητας. Προφανώς αναφέρομαι κυρίως στον defacer.

 

Επίσης, ελπίζω να έγινε λίγο πιο κατανοήτό (έστω και τόσο καθυστερημένα, μιας και αυτή ιστορία επαναλαμβάνεται εκνευριστικά) γιατί πλέον αναγκάστηκα να καταφύγω ΚΑΙ σε "credentials" στο τέλος του νήματος.

 

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

 

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

 

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

 

Τα credentials μπορεί εσένα να σε χαλάνε (ούτε εγώ είμαι κάνας τρελός fan τους) δεν παύουν όμως να αποτελούν μια στοιχειώδη οριοθέτηση ενός αρχικού πλαισίου αξιολογησης (προφανώς μέχρι αποδείξεως του αντιθέτου), για μια μεγάλη μερίδα ανθρώπων, θα έλεγα την μεγαλύτερη, ιδιαίτερα στον επαγελματικό τομέα.

 

Πολυσελιδες παπαρολογίες στα φόρουμ, παραθέσεις links του συρμού, αναφορές σε... bullets της Wikipedia και λοιπά τετριμμένα μπορούν να τα κάνουν όλοι, ακόμα και μαθητές λυκείου. Φυσικά και είναι χρήσιμα, όσο όμως παρουσιάζονται στην πραγματική τους διάσταση, δηλαδή την τετριμμένη.

 

Τα μη τετριμμένα, καλώς ή κακώς (κατά τη γνώμη μου καλώς) προϋποθέτουν στέρεες βάσεις για να μπορεί κανείς να τα διαπραγματευτεί, έστω και σε μικρό βαθμό, και ακόμα περισσότερο για να μπορέσει τα αντιληφθεί πριν αρχίσει να τα διαπραγματεύεται. Και κυρίως προϋποθέτουν εξειδίκευση, η οποία επίσης καλώς ή κακώς (ξανά καλώς κατά τη γνώμη μου) αποκτάται με εμπειρική εξάσκηση. Όσες Wikipedies, όσα links, όσα βιβλία, όσα πτυχία και να έχει κανείς, τα πράγματα που πραγματικά ξέρει, που τα έχει κάνει κτήμα του, και άρα κατά κανόνα ξέρει για τι πράγμα μιλάει όταν μιλάει (και όταν επιμένει) είναι αυτά τα οποία τα έχει δουλέψει στην πράξη.

 

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

 

 

 

[imitheos]

Βάζω αυτό το ποστ σε spoiler γιατί είναι off-topic. Το δημοσιεύω με αφορμή τη δική σου παράθεση, αλλά αναφέρομαι κυρίως στον defacer. Και το κάνω συνειδητά με αφορμή τη δική σου παράθεση, αφενός επειδή απάντησες σε δική μου ερώτηση, αλλά κυρίως επειδή σχεδόν πάντα "πατρονάρεις" τον defacer όταν παίρνεις θέση σε διαμάχες μεταξύ εμένα και του defacer.

Δεν πατρονάρω κανέναν. Υποστηρίζω αυτό που πιστεύω σωστό. Έχει τύχει να συμφωνήσω και με σένα σε "διαμάχες" σας. Δέχομαι ότι στο 90% των περιπτώσεων συμφώνησα με τον defacer αλλά κατά τη γνώμη μου αυτός είχε δίκιο. Δεν ήξερα ότι έπρεπε με το ζόρι να συμφωνήσω μαζί σου.

 

Ελπίζω μετά από το τελευταίο ποστ, σχετικά με την Bernstein (αλλά όχι μόνο) να έχεις αναθεωρήσει το παραπάνω, αναφορικά δηλαδή με το ποιανού τα επιχειρήματα στέκουν και μιλάνε από μόνα τους, ποιανού δεν στέκουν, ποιανού τα επιχειρήματα προσβάλλουν, καθώς και ποιον, πότε και ποιους προσβάλλουν οι αναφορές σε "credentials", κλπ.

Όχι δεν πείστηκα απλά το άφησα γιατί δεν βλέπω φως. Σε ποιο σημείο το άρθρο που έδωσες υποστηρίζει τα επιχειρήματά σου ?

 

Επίσης, ελπίζω να έγινε λίγο πιο κατανοήτό (έστω και τόσο καθυστερημένα, μιας και αυτή ιστορία επαναλαμβάνεται εκνευριστικά) γιατί πλέον αναγκάστηκα να καταφύγω ΚΑΙ σε "credentials" στο τέλος του νήματος.

Και στο adslgr είχες πει ότι το ίδιο ότι περίμενες πολυ πριν αναγκαστείς να καταφύγεις σε credentials. Αυτό δεν σε δικαιολογεί καθόλου. Είτε αναφέρεις τα προσόντα σου στο 1ο μήνυμα κάποιου νήματος είτε περιμένεις μέρες το ίδιο είναι. Τα προσόντα δεν δίνουν κύρος σε επιχειρήματα. Αν έρθεις και πεις "το νερό βράζει στους 100 βαθμούς" είτε είσαι τσομπάνης είτε είσαι 40 χρόνια χημικός έχει την ίδια αξία.

 

Τα credentials μπορεί εσένα να σε χαλάνε (ούτε εγώ είμαι κάνας τρελός fan τους) δεν παύουν όμως να αποτελούν μια στοιχειώδη οριοθέτηση ενός αρχικού πλαισίου αξιολογησης (προφανώς μέχρι αποδείξεως του αντιθέτου), για μια μεγάλη μερίδα ανθρώπων, θα έλεγα την μεγαλύτερη, ιδιαίτερα στον επαγελματικό τομέα.

Ίσως να είναι έτσι και να έχεις δίκιο. Η δική μου εμπειρία λέει ότι τα credentials συνήθως λέγονται όταν κάποιος _δεν_ έχει επιχειρήματα και δεν θέλει να παραδεχτεί κάποιο λάθος. Όπως ο Κυρ-Τάσος που θα έρθει να σου φτιάξει τα υδραυλικά, και ενώ τον βλέπεις ότι πάει να κάνει κάποια χαζή πατέντα για να γλυτώσει κόπο, προσπαθεί να στο παρουσιάσει ότι αυτή είναι η σωστή μέθοδος γιατί αυτός κάνει χρόνια αυτή τη δουλειά. Αν έχεις επιχειρήματα δεν χρειάζεσαι credentials.

 

Δεν έχω χρόνο αυτές τις μέρες για χαζομάρες οπότε θα κάνω like στα δικά σου μηνύματα να μην έχουμε μανούρες.

[migf1]

 

 

...

Δεν έχω χρόνο αυτές τις μέρες για χαζομάρες οπότε θα κάνω like στα δικά σου μηνύματα να μην έχουμε μανούρες.

 

Ούτε σε υπέδειξα ούτε θα σου υποδείξω εγώ σε ποια μηνύματα θα κάνεις like, ούτε θα σου υποδείξω εγώ με ποιον θα συμφωνείς. Το "ελπίζω" διαφέρει από το "επιβάλλω", ή τουλάχιστον έτσι ξέρω. Έχω το δικαίωμα να απαντάω όταν και όπως κρίνω εγώ σε μηνύματα που μου απευθύνονται προσωπικά.

 

Όσο για το...

 

>
Σε ποιο σημείο το άρθρο που έδωσες υποστηρίζει τα επιχειρήματά σου ?

 

Ήλπιζα πως θα μπορούσες αυτονόητα να συνδέσεις το ότι "η Benstein κάνει map σε 32 bits" του άρθρου, με το δικό μου "η hash function είναι εξ'ορισμού mapping function, και άρα βρίσκεται σε άμεση εξάρτηση με το μέγεθος του map". Το άκρως αντίθετο δηλαδή από αυτό για το οποίο την έφερες ως παραδειγμα, όταν σε ρώτησα αν μπορείς να παραθέσεις κάποια hash-function που δεν κάνει αναγωγή σε κάποιο map.

 

Προφανώς ήλπιζα λανθασμένα. No prob, it's not my problem anyway.

 

 

[imitheos]

Ήλπιζα πως θα μπορούσες αυτονόητα να συνδέσεις το ότι "η Benstein κάνει map σε 32 bits" του άρθρου, με το δικό μου "η hash function είναι εξ'ορισμού mapping function, και άρα βρίσκεται σε άμεση εξάρτηση με το μέγεθος του map". Το άκρως αντίθετο δηλαδή από αυτό για το οποίο την έφερες ως παραδειγμα, όταν σε ρώτησα αν μπορείς να παραθέσεις κάποια hash-function που δεν κάνει αναγωγή σε κάποιο map.

 

Αν αλλάξεις το unsigned long σε πχ unsigned short θα κάνει map σε 32 bits ?

[migf1]

Μπορείς να την αλλάξεις και να κάνει map και σε 64bits αν θέλεις: http://stackoverflow.com/questions/8334836/convert-djb-hash-to-64-bit

 

Το μόνο σίγουρο είναι πως σε κάποιο συγκεκριμένο πλήθος bits θα κάνει map (και προφανώς να προσαρμόσεις και τους κώδικές σου να το εκμεταλλεύονται).

[imitheos]

Άρα δεν είναι ο τάδε τύπος που χρησιμοποιούμε αυτός που δημιουργεί το "map σε τάδε bits" ? και η Hash Function αυτή-καθεαυτή είναι ανεξάρτητη από το μέγεθος ?

[migf1]

Άρα δεν είναι ο τάδε τύπος που χρησιμοποιούμε αυτός που δημιουργεί το "map σε τάδε bits" ? και η Hash Function αυτή-καθεαυτή είναι ανεξάρτητη από το μέγεθος ?

 

Είσαι ελεύθερος να χρησιμοποιήσεις/φτιάξεις όποια HF θέλεις, καθως επίσης και να την αναγάγεις δευτερογενώς, τριτοτγενώς, κλπ σε όσα δικά σου maps επιθυμείς, ανάλογα τις ανάγκες του project σου. Ακόμα και να χρησιμοποιήσεις το πρωτογενές της map απευθείας, αν αυτό αρκεί.

 

Έτσι κι αλλιώς στις περισσότερες περιπτώσεις η δημιουργία μιας HF μοιάζει με περιπέτεια σε αχαρτογράφητες περιοχές. Εννοώ δεν υπάρχουν μπούσουλες για HF που να λειτουργούν εξίσου καλά σε όλες τις περιπτώσεις. Για αυτόν ακριβώς το λόγο, παίζει ρόλο στο hashing efficiency σου πως θα γράψεις την HF και με ποιον τρόπο θα την συνδέσεις με το map και με τι μέγεθος map.

 

Υπάρχουν έτοιμες, δοκιμασμένες HF που είναι περισσότερο efficient για τις τάδες περιπτώσεις και λιγότερo για τις δείνα περιπτώσεις. Έχω ήδη αναφέρει πολλές φορές στο νήμα ως παράδειγμα, πως η string variable addition HF χρησιμοποιείται με map 256 θέσεων. Δεν σε εμποδίζει κανείς να τη χρησιμοποιήσεις με 128 θέσεις εσύ, αφού πρώτα εξασφαλίσεις πως θα προσαρμόσεις αντίστοιχα και τα υπόλοιπα σχετικά μέρη του κώδικά σου (αν χρειάζεται).

 

Αυτή η αλλαγή σίγουρα θα επηρεάσει το hashing efficiency σου, κι αν γίνει χωρίς να έχεις μελετήσει πρώτα το αν όντως σε συμφέρει να την αλλάξεις σε 128 θέσεις και γιατί, τότε θα καταλήξεις σε inefficient hashing συγκρτικά με την original version της.

[nik324]

Για να μην ανοιγω αλλο thread θα γραψω εδω...

 

 

Εστω οτι θελουμε να ενώσουμε δυο δυαδικα δέντρα...Θελω να βρω τον πιο αποτελεσματικό αλγόριθμο...

 

Αυτο που έχω σκευτεί είναι το εξής

 

Αν r1 και r2 οι ριζες των δέντρων τότε διατρέχουμε το r1 και για κάθε ενα απο τους κόμβους του, καλούμε την συνάρτηση εισαγωγης σε δυαδικό δέντρο περνώντας ως όρισμα την r2 και σαν value την τιμή του κόμβου του r1.... Στο τέλος το r2 θα εχει και τις τιμές του r1...

 

Aυτο έχω σκευτει μέχρι στιγμής... Υπάρχει κάτι καλύτερο?

[migf1]

http://www.google.com/webhp?hl=en#hl=en&tbo=d&biw=1280&bih=567&sclient=psy-ab&q=algorithm+merge+binary+trees&oq=algorithm+merge+binary+trees&gs_l=hp.3..0i8i30l2.12471888.12481677.0.12481945.35.29.3.2.2.0.223.4649.0j24j5.29.0.les%3B..0.0...1c.1.A23ZPI55VNE&pbx=1&bav=on.2,or.r_gc.r_pw.r_qf.&bvm=bv.1355534169,d.Yms&fp=8389ae1529bdf0dc&bpcl=40096503

[nik324]

Ερωτηση...

Εχουμε δυο λιστες ταξινομημενες..Μια κατα αυξουσα σειρα και μια κατα φθινουσα...Μπορουμε να δημιουργησουμε μια τριτη λιστα η οποια να ειναι κατα φθινουσα διαταξη και να περιεχει τα στοιχεια των αλλων δυο λιστων και ολα αυτα σε χρονο Ο(ν1+ν2) οπου το ν1,ν2 το μηκος καθε μιας απο τις αρχικες λιστες..?

 

 

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

[migf1]

Βασικά αυτό που ρωτάς αν δεν ήθελες 3η λίστα γίνεται τετριμμένα σε O(n) όπου n = το πλήθος στοιχείων της λίστας που είναι σε αύξουσα σειρά (δηλαδή ν1 στο παράδειγμά σου). Πιάνεις την αύξουσα από το τέλος της και κάνεις append ένα-ένα τα στοιχεία της στο τέλος της φθίνουσας.

 

Ομοίως ως λογική, με 3η λίστα γίνεται σε O(ν1+ν2)... αντιγράφεις πρώτα την φθίνουσα από αρχή έως τέλος και κατόπιν την αύξουσα από τέλος έως αρχή.

 

ΥΓ. Ίσως δεν έχω καταλάβει κάτι καλά, γιατί μου φαίνεται πολύ απλό, και για να το ρωτάς μάλλον κάτι διαφορετικό πρέπει να εννοείς, ε;

 

EDIT: http://www.insomnia.gr/topic/467655-%CE%B1%CE%BB%CE%B3%CE%BF%CF%81%CE%B9%CE%B8%CE%BC%CE%B9%CE%BA%CE%AE-%CE%B5%CF%81%CF%8E%CF%84%CE%B7%CF%83%CE%B7/page-4?do=findComment&comment=52263956

Επεξ/σία 30 Μαρτίου 2013 από migf1

[imitheos]

Βασικά αυτό που ρωτάς αν δεν ήθελες 3η λίστα γίνεται τετριμμένα σε O(n) όπου n = το πλήθος στοιχείων της λίστας που είναι σε αύξουσα σειρά (δηλαδή ν1 στο παράδειγμά σου). Πιάνεις την αύξουσα από το τέλος της και κάνεις append ένα-ένα τα στοιχεία της στο τέλος της φθίνουσας.

 

Ομοίως ως λογική, με 3η λίστα γίνεται σε O(ν1+ν2)... αντιγράφεις πρώτα την φθίνουσα από αρχή έως τέλος και κατόπιν την αύξουσα από τέλος έως αρχή.

 

ΥΓ. Ίσως δεν έχω καταλάβει κάτι καλά, γιατί μου φαίνεται πολύ απλό, και για να το ρωτάς μάλλον κάτι διαφορετικό πρέπει να εννοείς, ε;

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

 

Αν για παράδειγμα έχουμε 9 7 5 1 και 2 3 8 έτσι που το λες θα γυρίσουμε την μία λίστα σε 8->3->2 και θα την κολλήσουμε στο τέλος της φθίνουσας δηλαδή θα γίνει 9->7->5->1->8->3->2 που δεν θα είναι ταξινομημένη.

Ερωτηση...

Εχουμε δυο λιστες ταξινομημενες..Μια κατα αυξουσα σειρα και μια κατα φθινουσα...Μπορουμε να δημιουργησουμε μια τριτη λιστα η οποια να ειναι κατα φθινουσα διαταξη και να περιεχει τα στοιχεια των αλλων δυο λιστων και ολα αυτα σε χρονο Ο(ν1+ν2) οπου το ν1,ν2 το μηκος καθε μιας απο τις αρχικες λιστες..?

 

 

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

Τι λίστες έχεις ? Είναι διπλά συνδεδεμένες ? Έχεις δείκτη head και tail ? Αν ναι τότε ξεκινώντας από τον tail της αύξουσας και διατρέχοντας τον prev δείκτη έχεις ουσιαστικά την φθίνουσα μορφή ολόκληρη της λίστας οπότε θέλεις ένα απλό merge που διατρέχει τις δύο φθίνουσες λίστες άρα χρόνο ν1 + ν2.

 

Αν δεν έχεις prev δείκτη, τότε μπορείς σε χρόνο ν1 να αντιστρέψεις (πχ με στοίβα) την αύξουσα λίστα και μετά ν1+ν2 για να κάνεις το merge οπότε 2*ν1+ν2 οπότε ν1+ν2.

 

Σημειωτέον ότι έχω πολύ πονοκέφαλο και επίσης ποτέ δεν χώνεψα το O notation και την πολυπλοκότητα οπότε 99% έγραψα μπούρδες.