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

alkisg · 1 Ιουνίου 2007

Είτε στον καίσαρα είτε στην random πρέπει να κρατήσεις μια πληροφορία:

1) Στον καίσαρα, πρέπει να κρατήσεις το Ν (πόσα γράμματα δεξιά...)

2) Στην random, πρέπει να κρατήσεις το randseed.

Στη γενική περίπτωση (όταν μιλάμε για permutation-based κρυπτογράφηση), πρέπει να κρατήσεις τον πίνακα table, δηλαδή 256 byte.

Και όταν λέμε "κρατάω", φυσικά μπορεί να είναι και hardcoded, δηλαδή

randseed = 1234;

...create encryption_table

...σε άλλη εκτέλεση...

randseed = 1234;

...create_encryption_table()...

...decryption_table = invert_encryption_table()...

alkisg · 1 Ιουνίου 2007

Υ.Γ.#1 αν ρωτάς για το πώς θα πάρω το decryption_table από το encryption_table:

for (int i = 0; i <= 255; i ++)

decryption_table[encryption_table] = i;

Υ.Γ.#2 επειδή το encyrption_table προήρθε από swap, είναι 1-1.

FarCry · 1 Ιουνίου 2007

2) Στην random, πρέπει να κρατήσεις το randseed.

nai ok etsi mporeis na kaneis apokriptografisi. alla se mia theoritika random katastasi de tha mporouses na to kaneis an den itan pseudorandom diladi alla hardware based.

jsmith6 · 12 Ιουνίου 2007

Δεν κάνω ακριβώς την κρυπτογράφιση του Καίσαρα, αλλά μοιάζει.

Μου πήρε λίγο, αλλά τελικά βρήκα τρόπο να το κάνω με index. Αν είχα δει βέβαια αυτό το post θα το είχα κάνει πιο γρήγορα, αλλά ήθελα να το παιδέψω:

Υ.Γ.#1 αν ρωτάς για το πώς θα πάρω το decryption_table από το encryption_table:

for (int i = 0; i <= 255; i ++)

decryption_table[encryption_table] = i;

Υ.Γ.#2 επειδή το encyrption_table προήρθε από swap, είναι 1-1.

Να και ένα benchmark, θα γράψει τα αποτελέσματα στο αρχείο output.txt. Το πρόβλημα με το index όπως το έχω υλοποιήσει είναι οτι αν υπάρχει παραπάνω από μια φορά ένας χαρακτήρας τότε θα μου αποθηκεύσει μόνο την θέση του τελευταίου (αυτού που βρήκε πιο μετέπειτα). Δεν είναι πρόβλημα στο δικό μου πρόγραμμα διότι ο κάθε χαρακτηρας υπάρχει μόνο μία φορά μέσα στο alphabet[], αλλά θα ήθελα να ξέρω αν γίνεται να αποθηκεύει και dublicate χαρακτήρες.

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

Ας κοιτάξουμε το benchmark:

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

// standard constants
#define COUNTER 100000000

// techiqnues constants
#define alphabetlength 97

int main(void)
{
// standard vars
clock_t ticks;
register int regint;
FILE *output;

// techniques vars
char *alphabetptr,alphabet[alphabetlength],ch;
short int i,letterindex[256],alphabetlocation=0;

output = fopen("./output.txt", "wt");

// create the alphabet, not quite as random (check out "qwerty") but suits the need for now
alphabet[0] = 10;
alphabet[1] = 9;
strcat(alphabet, " `1234567890-=qwertyuiop[]asdfghjkl;'\\zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}ASDFGHJKL:\"|ZXCVBNM<>?");

// which character would you like me to locate?
ch = 'E';

// my first attempt
ticks = clock();
for(regint = 0; regint < COUNTER; regint++)
{
	for (i=0; i<alphabetlength; i++) 
	{
		if (ch==alphabet[i]) alphabetlocation = i;
	}
}
ticks = clock() - ticks;
fprintf(output,"\nlocation is %d and it took %ld ticks for my first attempt", alphabetlocation,ticks);

alphabetlocation = 0;

// godlike solution
ticks = clock();
for(regint = 0; regint < COUNTER; regint++)
{
	for (i=0; i<alphabetlength; i++) 
	{
		if (ch==alphabet[i])
		{
			alphabetlocation = i;
			break;
		}
	}
}
ticks = clock() - ticks;
fprintf(output,"\nlocation is %d and it took %ld ticks for godlike solution", alphabetlocation,ticks);

alphabetlocation = 0;

// chiossif1 solution
alphabetptr = alphabet; // preliminary
ticks = clock();
for (regint=0; regint<COUNTER; regint++)
{
	for (alphabetlocation = 0; *alphabetptr && *alphabetptr++ - ch; alphabetlocation++);
}
ticks = clock() - ticks;
fprintf(output,"\nlocation is %d and it took %ld ticks for chiossif1 solution", alphabetlocation,ticks);

alphabetlocation = 0;

// chiossif2 solution
alphabetptr = alphabet; // preliminary
ticks = clock();
for (regint=0; regint<COUNTER; regint++)
{
		for (alphabetptr = alphabet; *alphabetptr++ - ch;);
		alphabetlocation = alphabetptr - alphabet - 1;
}
ticks = clock() - ticks;
fprintf(output,"\nlocation is %d and it took %ld ticks for chiossif2 solution", alphabetlocation,ticks);

alphabetlocation = 0;

//
// My second attempt, the index solution. The problem with this
// is that it keeps only the last position of a given character.
// This is not a problem since in this case, each character only
// exists once inside the array
//

// these are preliminary preparations, there is no need to enter them
// into the benchmark because they only get executed once during the
// whole program
for (i=0; i<256; i++)
{
	letterindex[i] = -1;
}

for (i=0; i<=alphabetlength-1; i++)
{
	letterindex[alphabet[i]] = i;
}

ticks = clock();
for(regint = 0; regint < COUNTER; regint++)
{
	alphabetlocation = letterindex[ch];
}
ticks = clock() - ticks;
fprintf(output,"\nlocation is %d and it took %ld ticks for my second attempt", alphabetlocation,ticks);

return 0;
}

Αν και η λύση με τον index σ'αυτό το benchmark φένεται πιο γρήγορη, στην πράξη, μέσα στο πρόγραμμα, η πρώτη λύση του chiossif είναι πιο γρήγορη. Περνόντας ένα αρχείο μεγέθους 1415211 χαρακτήρων πήρα τα ακόλουθα αποτελέσματα:

(forward είναι η κρυπρογράφηση, και backwards είναι η αποκρυπτογραφηση, επίσης, οι αριθμοί είναι τα δευερόλεπτα που χρειάστηκαν για την διαδικασία)

Η πρώτη μου προσέγγηση:

- forward: 14

- backwards: 14

Η λύση του godlike:

- forward: 10

- backwards: 9

Η πρώτη λύση του chiossif:

- forward: 5

- backwards: 6

Η δεύτερη λύση του chiossif:

- forward: 10

- backwards: 9

Η λύση με το index:

- forward: 6

- backwards: 5

Αν καταλάβαινα την λύση του chiossif θα έβαζα αυτήν. Με την ευκαιρία,

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

Όταν θα μάθω για τους pointers αρκετά, θα επιστρέψω σ'αυτό. Για την ώρα δεν καταλαβάινω γρι.

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

Έχω ένα βιβλίο του Herbert Schildt. Τι γνώμη έχεις για αυτό το βιβλίο;

system · 12 Ιουνίου 2007

Interpolation search ξέρει κανείς?

chiossif · 12 Ιουνίου 2007

Αυτό:

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

σε απλά λόγια λέει:

Κάνε τον wordptr να δείχνει στην αρχή του word. [wordptr=word]

Όσο, [for]

αν από αυτό που δείχνει το wordptr αφαιρεθεί το ch και το αποτέλεσμα δεν είναι 0 (=False)

αύξησε το wordptr κατά ένα. (και άρα δείχνει στον επόμενο χαρακτήρα)[*wordptr++-ch;]

Όταν τελειώσει το Όσο με μια αφαίρεση βρίσκουμε την θέση του χαρακτήρα. [location=wordptr-word;]

Τώρα επειδή για λόγους ταχύτητας (ένας έλεγχος λιγότερος) δεν ελέγχουμε την ολοκλήρωση του word, έχει προηγηθεί μια τοποθέτηση μέσα του μετά την τελευταία θέση του χαρακτήρα ώστε το Όσο να σταματήσει σίγουρα. Αν δώσει σαν θέση την τελευταία τότε ΔΕΝ ΥΠΗΡΧΕ ΟΥΣΙΑΣΤΙΚΑ μέσα στο word.

Ότι έχω γράψει στο συζήτηση αυτή υπάρχει

τόσο ως θεωρία όσο και σε παραδείγματα

-και αναφέρομαι στο εκπληκτικό while (*s++=*t++); της παραγράφου 5.5 του 5ου κεφαλαίου-

στο βιβλίο

The C Programming Language,

Second Edition by Brian W. Kernighan and Dennis M. Ritchie.

Prentice Hall, Inc., 1988.

[ http://cm.bell-labs.com/cm/cs/cbook/index.html ]

Καλό διάβασμα !

alkisg · 12 Ιουνίου 2007

Στην chiosif1 υπάρχει bug, το

alphabetptr = alphabet; // preliminary

έπρεπε να είναι μέσα στο loop της χρονομέτρησης. Τώρα το βρίσκει με την πρώτη και μετά δεν το ξαναψάχνει.

Αποτελέσματα στο pc μου:

location is 64 and it took 5127 ticks for my first attempt

location is 64 and it took 2974 ticks for godlike solution

location is 64 and it took 4677 ticks for chiossif1 solution

location is 64 and it took 4286 ticks for chiossif2 solution

location is 64 and it took 40 ticks for my second attempt

Προφανώς το index θα μείνει σταθερό για μεγαλύτερο sample, ενώ οι άλλες θα αυξηθούν ακόμα περισσότερο.

alkisg · 12 Ιουνίου 2007

Το πρόβλημα με το index όπως το έχω υλοποιήσει είναι οτι αν υπάρχει παραπάνω από μια φορά ένας χαρακτήρας τότε θα μου αποθηκεύσει μόνο την θέση του τελευταίου (αυτού που βρήκε πιο μετέπειτα). Δεν είναι πρόβλημα στο δικό μου πρόγραμμα διότι ο κάθε χαρακτηρας υπάρχει μόνο μία φορά μέσα στο alphabet[], αλλά θα ήθελα να ξέρω αν γίνεται να αποθηκεύει και dublicate χαρακτήρες.

Με ποιο σκεπτικό θα ήθελες μετά να διαλέξεις τον duplicate χαρακτήρα;

Δηλαδή, έστω ότι ψάχνεις για 'Ε', και υπάρχει στις θέσεις 21, 34, 45, 56, 78.

Ποιον από όλους θα ήθελες να σου επιστρέψει και με ποιο σκεπτικό θα τον διάλεγε;

Αν ήθελες π.χ. να σου επιστρέφει όλες τις ευρέσεις σε ένα πινακάκι, τότε αρκεί στην προετοιμασία να έφτιαχνες αυτό το πινακάκι με τις θέσεις, και αντί να κρατάς char στον πίνακα ευρετηρίου, να κρατούσες pointer στο πινακάκι με τις θέσεις.

smilefreeware · 15 Ιουνίου 2007

Με ένα XOR νομίζω θα είχε κάτι απλό.

Σύνδεση

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

Προτεινόμενες αναρτήσεις

alkisg

alkisg

FarCry

jsmith6

system

chiossif

alkisg

alkisg

smilefreeware

Αρχειοθετημένο

Σύνδεση