ANSI C: γρήγορη εύρεση ενός στοιχείου μονοδιάστατου πίνακα

[FarCry]

Με Binary Search γίνεται σε log(n) χρόνο, αλλά προϋποθέτει ταξινομημένα στοιχεία, που σε πίνακα χαρακτήρων δεν έχει και ιδιαίτερο νόημα

 

 

afou re o kathe xaraktiras exei antistoixo ASCII equivalent. mia xara kanei kai sort kai search. giati kolises sto xaraktira?

[alkisg]

Binary search:

 

Έστω ότι ο πίνακάς σου λέγεται word.

 

1) Φτιάχνεις έναν παράλληλο πίνακα ακεραίων index, που σε κάθε θέση του περιέχει τους αριθμούς 1, 2, 3, ..., n, δηλαδή

index = i.

2) Ταξινομείς τον word αλλά παράλληλα πειράζεις και τον index, π.χ. σε bubblesort οι εντολές μέσα στα for της ταξινόμησης είναι

if (word[j] < word[j-1]) {

swap(word[j], word[j-1]);

swap(index[j], index[j-1]);

}

3) Για την εύρεση, κάνεις binary search στο ταξινομημένο word. Αυτό είναι το βασικό κομμάτι της λύσης, και όπως είπαν τα παιδιά παραπάνω χρειάζεται Ο(logn), δηλαδή απειροελάχιστο χρόνο. Με 33 επαναλήψεις μπορείς να βρεις έναν χαρακτήρα σε πίνακα 6 δισεκατομυρίων θέσεων (ή αλλιώς, ένα όνομα στον τηλεφωνικό κατάλογο όλου του πλανήτη).

4) Το index σου δείχνει την θέση του στοιχείου στον αρχικό πίνακα word.

5) Αν θες να βρεις τον πρώτο χαρακτήρα του word που ταιριάζει (αν ταιριάζουν πολλοί, η binary search δεν βρίσκει υποχρεωτικά τον πρώτο), τότε αφού τελειώσει η binary search θα πρέπει να μετακινηθείς "αριστερά" στον πίνακα word:

while (j >= 0 && word[j] == key)

j--;

j++;

[alkisg]

Xωρίς search, με lookup table:

 

Τα πιθανά στοιχεία αναζήτησης σου είναι πεπερασμένα (το πολύ 256 χαρακτήρες), οπότε μπορείς να κάνεις το εξής:

1) Έχεις έναν πίνακα ακεραίων με 256 θέσεις. Τους αρχικοποιείς όλους σε -1.

2) Κάθε φορά που αναζητείς κάτι, ψάχνεις τον πίνακα κανονικά όπως κάνεις και τώρα, χωρίς να τον ταξινομήσεις.

3) Όμως, αποθηκεύεις το αποτέλεσμα κάθε αναζήτησης στον πίνακα ακεραίων. Δηλαδή αν έψαξες για 'c', και το βρήκες στην 123456 θέση, κάνεις

πίνακας_θέσεων['c'] = 123456;

4) Έτσι, σε επόμενο ξαναψάξιμο, αρκεί να κοιτάς τον πίνακας_θέσεων[key], και αν δεν είναι -1, ξέρεις αμέσως (σε O[1]) την απάντηση.

 

Αν ο πίνακας word έχει περισσότερους από 256 χαρακτήρες, αυτό είναι πιο γρήγορο από ταξινόμηση + binary search, ενώ δεν έχει μεγάλο αρχικό overhead.

 

Αν ο πίνακας word είναι πολύ μικρός, τότε μπορείς (αν θες να το κάνεις όσο optimize γίνεται) να ψάξεις αρχικά για κάθε στοιχείο του word, όχι για κάθε στοιχείο του αλφαβήτου. Έτσι πάλι βγαίνει πιο γρήγορο από ταξινόμηση + binary search.

[chiossif]

Όλα είδον !

 

Π Υ Ρ !

 

[parsifal]

afou re o kathe xaraktiras exei antistoixo ASCII equivalent. mia xara kanei kai sort kai search. giati kolises sto xaraktira?

 

Γιατί, στο συγκεκριμένο παράδειγμα, το string "Hello world" γίνεται " Hdellloorw" και έχει χάσει την εννοιολογική αξία του...;

[FarCry]

Γιατί, στο συγκεκριμένο παράδειγμα, το string "Hello world" γίνεται " Hdellloorw" και έχει χάσει την εννοιολογική αξία του...;

 

nai alla gia auto eipa na kanei index. o index tha krataei tis arxikes theseis ton grammaton opote no problem meta tin taksinomisi

 

PS: to sosto einai "dehllloorw". ksexasame kai tin aggliki alfabito?

[parsifal]

nai alla gia auto eipa na kanei index. o index tha krataei tis arxikes theseis ton grammaton opote no problem meta tin taksinomisi

 

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

 

[offtopic]

 

 

 

PS: to sosto einai "dehllloorw". ksexasame kai tin aggliki alfabito?

 

Στον ASCII Table, οι κεφαλαίοι χαρακτήρες προηγούνται των πεζών και ο χαρακτήρας space των κεφαλαίων...

 

 

 

[/offtopic]

[chiossif]

Η απάντηση στο quiz (λίγο καθυστερημένη):

 

>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define COUNTER 100000000

int main(void) {
   unsigned short int i, location;
   unsigned char word[12], ch, *wordptr;
   clock_t ticks;
   register int regint;

   strcpy(word, "hello world");
   ch = 'e';
   /* Your version */
   ticks=clock();
   for (regint=0;regint<COUNTER;regint++) {
       for (i=1; i<=10; i++) {
           if (word[i-1]==ch) location = i;
       }
   }
   ticks=clock()-ticks;
   printf("character '%c' is located on position %d\nat %ld ticks.\n", ch,location, ticks);

   /* My version */
   ticks=clock();
   for (regint=0;regint<COUNTER;regint++) {
       wordptr=word;
       for (location=1;*wordptr&&*wordptr++-ch;location++);
   }
   ticks=clock()-ticks;
   printf("character '%c' is located on position %d\nat %ld ticks.\n", ch,location, ticks);

   /* My BEST SHOT version */
   sprintf(word,"%s%c/0","hello world",ch);
   ticks=clock();
   for (regint=0;regint<COUNTER;regint++) {

       for (wordptr=word;*wordptr++-ch;);
       location=wordptr-word;

   }
   ticks=clock()-ticks;
   printf("character '%c' is located on position %d\nat %ld ticks.\n", ch,location, ticks);

   return 0;
}

 

Σε κάθε περίπτωση προσπάθησα να κρατήσω την χρήση των μεταβλητών όπως πρωτοδηλώθηκαν.

Αν θεωρήσουμε μια μέση αναζήτηση -ενός χαρακτήρα στην μέση -1 ή +1- αναρωτιέμαι από ποιό μέγεθος και πάνω θα είναι αποδοτικότερες οι άλλες μέθοδοι που αναφέρθηκαν;

[FarCry]

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

 

nai an kai den einai teleios sigouro auto. sto wikipedia anaferei ti leksi may

 

Binary search can interact poorly with the memory hierarchy (i.e. caching), because of its random-access nature. For in-memory searching, if the interval to be searched is small, a linear search may have superior performance simply because it exhibits better locality of reference

 

tora gia to allo me to hash table de ksero giati exei best 1, average 1 kai worst N eno to binary search exei best 1, average log(N) kai worst log(N)

Episis prepei na ilopoiiseis kai algorithmo gia tin apofigi ton collisions.

 

+oti fibonacci search einai kalitero apo to binary search.

 

The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. This method is faster than traditional binary search algorithms

 

To sorting einai efapaks xronos giati ginetai mono mia fora stin arxi nlog(N). opote de to lambano ipopsi me dedomeno oti tha kanei ekatontades anazitiseis o epipleon sorting xronos theoreitai ameliteos

 

PS: iparxei kai i radix sort me O(N)

PPS: dikio exeis gia tous ASCII. ego to pira teleios xima

[alkisg]

> nai an kai den einai teleios sigouro auto. sto wikipedia anaferei ti leksi may

Άλλο indexing, που έχει πάντα Ο(1) και είναι το τέλειο σε αναζήτηση (αν εξαιρέσουμε την κατασκευή του και τις απαιτήσεις του σε μνήμη), και άλλο linear search (ή ελληνιστί σειριακή αναζήτηση).

 

> PPS: dikio exeis gia tous ASCII. ego to pira teleios xima

Εγώ πάλι εξακολουθώ να συμφωνώ μαζί σου, ότι οι χαρακτήρες δεν έχουν διαφορά από τους αριθμούς... Δηλαδή αν ανακατέψεις τους βαθμούς των πανελληνίων είναι καλύτερο από το να ανακατέψεις το "Hello world"? Και οι βαθμοί έχουν νοηματική σειρά, αντιστοιχούν σε κάποιον μαθητή... Πάντα αν χρειάζεσαι αναφορά στον αρχικό πίνακα, κρατάς παράλληλο πίνακα με τις αρχικές θέσεις των χαρακτήρων/αριθμών/whatever.

 

> Αν θεωρήσουμε μια μέση αναζήτηση -ενός χαρακτήρα στην μέση -1 ή +1- αναρωτιέμαι από ποιό μέγεθος και πάνω θα είναι αποδοτικότερες οι άλλες μέθοδοι που αναφέρθηκαν;

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

Π.χ. αν ο πίνακας word έχει 1.000.000 χαρακτήρες, τότε το κλασσικό bubblesort θέλει 1.000.000.000.000 (τρις) επαναλήψεις.

Αν οι αναζητήσεις που είναι να γίνουν είναι π.χ. μόνο 1.000, τότε φυσικά η ταξινόμηση είναι out of the question...

 

Αλλά μ' αρέσει που εμείς παιδευόμαστε να βρούμε τον καλύτερο τρόπο και ο original poster δεν ασχολείται καν!

[jsmith6]

Αλλά μ' αρέσει που εμείς παιδευόμαστε να βρούμε τον καλύτερο τρόπο και ο original poster δεν ασχολείται καν!

 

Με τα post να πεύτουν βροχή, ο original poster παλέυει να καταλάβει τι γίνεται!

 

Κατ'αρχήν σας ευχαριστώ για το ενδιαφέρον και τις απαντήσεις σας. Όλους.

 

Έπρεπε να είμουν πιο σαφής στην διατύπωση του προβλήματος. Στο παράδειγμα που δουλεύω μόνος μου, ο μονοδιάστατος πίνακας έχει 97 θέσεις. Σε κάθε μία από τις οποίες "κατοικεί" ένας χαρακτήρας. Ο ίδιος χαρακτήρας δεν μπορεί να υπάρχει σε 2 θέσεις. Ουσιαστικά στον πίνακα υπάρχουν όλοι οι χαρακτήρες του πληκτρολογίου, σην τον EOLN και ΤΑΒ. Τα στοιχεία του πίνακα δεν πρέπει να αλάξουν θέση, η σειρά των χαρακτήρων πρέπει να παραμείνει ως έχει. Όμως το να φτιάξω έναν άλλο πίνακα που να έχει πληροφορίες οι οποίες θα βοηθήσουν στην ανεύρεση ένος στοιχείου είναι φυσικά αποδεκτό. Βασικά ένας άλλος array που θα βοηθήσει είναι και αυτό που σκεύτικα εξ'αρχής, ή ίσως να φτίαξω έναν δισ-διάστατο πίνακα. Όμως τελικά έφτασα σε αδιέξοδο.

 

Αυτό που προσπαθώ να κάνω είναι μία απλή (επαναλαμβάνω απλή), αυτοσχέδια κρυπτογράφηση. Είναι το έιδος της κρυπτογράφησης που θα εμποδίσει την μικρή αδερφή μου από το να διαβάσει τα αρχεία Δεν ήθελα να ρίξω όλο τον κώδικα μαζί με περιγραφή του τι κάνει σε ένα post και να πω "τι βελτιώσεις μπορώ να του κάνω;" ή "ποιά είναι τα ανορθόδοξα πράγματα;". Θέλω να αναλύσω ένα-προς-ένα τα προβλήματα που συναντάω και να τον τελειοποιήσω σιγά-σιγά με τον καιρό, σαν φινίρισμα.

 

Για να κάνω benchmark το πόσο γρήγορο είναι αυτό το κομάτο κώδικα, απλά βάζω τον αλγόριθμο να επεξεργαστεί ένα αρχείο γύρω στα 450K και γράφω ένα log που μου λέει σε δευτερόλεπτα πόσο χρόνο του πήρε. Σαν benchmark μάλλον δεν είναι ακριβές αλλά ήταν πρακτικό και το μόνο που μπορούσα να σκευτώ σαν αρχάριος.

 

Από όλες τις προτάσεις η μόνη που κατάλαβα πλήρως ήταν του godlike. Δηλαδή:

 

>for (i=0; i<10; i++)
{
if (word[i]==ch)
{
	location = i;
	break;
}
}

 

Ήξερα οτί μπορώ να χρησιμοποιήσω το break αλλά δεν το σκεύτικα. Με την δική μου, απλή προσέγκιση, ο χρόνος που χρειαζόταν το πρόγραμμα (για να περάσει το αρχείο των 450Κ) ήταν 5 δευτερόλεπτα. Με την πρόταση του godlike μειώθηκε στα 3. Σημαντική βελτίωση, αν και δεν μπόρεσα να απαλαγώ ακόμα από τα "i-1. Ίσως αν το καταφέρω και αυτό να γίνει ακόμα πιο γρήγορο.

 

Στην συνέχεια κοίταξα το παράδειγμα του chiossif και μου πήρε κάποια ώρα να ξεχωρίσω ποιό κομμάτι του κώδικα είναι το "ζουμί". Αυτό εδώ δηλαδή:

 

>wordptir=word;
for (location=1;*wordptr&&*wordptr++-ch;location++);

 

Μπορώ να πω οτι δεν καταλαβαίνω τι κάνει (δεν έχω καταλάβει ακόμα τους pointers), αλλά ό,τι κι'αν κάνει, είναι πιο γρήγορο! Από τα 3 δευτερόλεπτα πέσαμε στα 2.

 

Μετά είδα την αλαγή που έκανε ο parsifal:

 

>for(location = 1; *wordptr++ - ch; location++);

 

Με το benchmark των registers βγήκε πιο αργό (παράξενο), και όταν το έβαλα μέσα στο όλο πρόγραμμα o compiler μου έβγαλε αυτό το ακαταβήστικο error:

 

>/bin/bash: line 1: 1359 Segmentation fault    ./a.out

shell returned 139

 

Μετά διάβασα για την binary και fibonacci search και ακόμα ψάχνομαι με αυτές. Όταν είδα το post του alkisg θυμύθηκα αυτό που έιχα σκευτεί εξ'αρχής. Δεν ήθελα να αλάξουν θέση τα στοιχεία του πίνακα για να ξέρω που βρήσόντουσαν, αλλά τελικά αύτο δεν είναι πρόβλημα αν σε έναν άλλο πίνακα μπορώ να αποθηκεύσω τις αρχικές θέσεις τους. Έπρεπε να είχα πιο ευέλικτο τρόπο σκέψης. Τώρα θέλω να το παλέψω μόνο και μόνο επειδή παράτησα αυτήν την λύση πολύ νωρίς.

 

Έπειτα υπάρχει και αυτό:

 

>for (wordptr=word;*wordptr++-ch;);
location=wordptr-word;

 

Το οποίο θα το δοκιμάσω, αλλά πριν το ενσωματόσω θα πρέπει να το καταλαβάινω πλήρως.

 

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

[chiossif]

Καλά έκανες και έγραψες γιατί είχαμε αρχίσει να ανησυχούμε

 

Η απάντηση σου με έπεισε. Λοιπόν:

 

Πράγματι αυτό εδώ είναι το ζουμί:

>
for (wordptr=word;*wordptr++-ch;);
location=wordptr-word;

...και δουλεύει ΚΑΛΑ ΜΟΝΟ στην περίπτωση που είσαι πάντα σίγουρος ότι ο ch περιέχεται μέσα στο word. Αν όχι -δεν είσαι σίγουρος ότι περιέχεται ΠΑΝΤΑ- τότε βάζεις σαν τελευταίο χαρακτήρα στο word τον ch και αν η location "δείχνει" πριν από τον τελευταίο χαρακτήρα τον βρήκες -σύστημα με το ζόρι παντριά αλλά δουλεύει και μάλιστα σφαίρα-.

 

Στο πρόγραμμα αυτό το κάνω με την εντολή

>
sprintf(word,"%s%c/0","hello world",ch);

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

 

Τελειώνω με τις ακόλουθες συμβουλές:

- Συνέχισε (ή και άρχισε αν δεν το έχεις κάνει ήδη) το διάβασμα και την εκμάθηση της C απο ένα καλό βιβλίο.

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

- Στο δίκτυο θα βρεις ΕΤΟΙΜΕΣ απαντήσεις σχεδόν σε κάθε σου ερώτηση.

 

Καλό ταξείδι και αναμένουμε, τουλάχιστον δείγμα κώδικα, όταν φτάσεις Ιθάκη.

[FarCry]

Με τα post να πεύτουν βροχή, ο original poster παλέυει να καταλάβει τι γίνεται!

 

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

 

E tote pigaine kai diabase gia tin kriptografisi tou kaisara kai telos. Ti mas paideueis?

 

http://en.wikipedia.org/wiki/Caesar_cipher

 

apli kai katanoiti. poli eukoli stin ilopoiisi kai i aderfi sou apokleietai na tin katalabei.

[alkisg]

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

 

Φαντάσου το ως εξής:

1) Βάζεις σε έναν πίνακα όλους τους χαρακτήρες, από 0 μέχρι 255.

Δεν έχει νόημα να έχεις μόνο τους 97. Τους υπόλοιπους γιατί να μην τους έχεις;

Κώδικας γι' αυτό το κομμάτι:

>
for (int i = 0; i <= 255; i++)
 table[i] = i;

2) Τους ανακατεύεις σαν τράπουλα, αντιμεταθέτοντας κάποιον από αυτούς με κάποιον άλλον, ώστε τελικά η κρυπτογράφηση που θα κάνεις να είναι εντελώς τυχαία:

>
for (int i = 0; i <= 255; i++)
 swap(table[i], table[random(256)]);

3) Έτσι, αν θέλεις να κρυπτογραφήσεις έναν χαρακτήρα c, αρκεί να πάρεις τον αντίστοιχο χαρακτήρα που σου λέει το table, δηλαδή

>
char Encrypt(char c)
{
 return table[c];
}

 

Αυτή είναι η μαγεία του index, ούτε αναζητήσεις ούτε τίποτα. Σε Ο(1) έχεις την απάντηση, και έτσι θα δεις τεράστια επιτάχυνση στον κώδικά σου.

 

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

>
for (int i = 0; i <= 255; i++)
 table[i] = (i + N) % 256;

όπου Ν το πόσα γράμματα μετακινείς δεξιά το κάθε γράμμα, σύμφωνα με την κρυπτογράφηση του Καίσαρα.

[FarCry]

Nomizo sto random iparxei problima apokriptografisis giati den einai 1 pros 1. gia na iparksei kai apokriptografisi tha prepei to gramma pou antikathistate na brisketai stin antistoixi thesi tou allou.

 

gia paradeigma an sti thesi 100 tou table exei mpei tixaia to gramma E kai pas na kriptografiseis to gramma B pou o ascii tou einai to 100, opote kaneis swap to B me to E tha prepei kai sti thesi tou ASCII arithmou E sto table na brisketai to gramma B. Eno me ton kaisara kaneis kanonika kai apokriptografisi