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

[jsmith6]

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

 

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

int main(void)
{
unsigned short int i,location;
unsigned char word[11],ch;

strcpy(word, "hello world");

ch = 'e';

for (i=1; i<=10; i++)
{
	if (word[i-1]==ch) location = i;
}

printf("character '%c' is located on position %d\n\n", ch,location);

return 0;
}

 

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

 

Και μόνο κάποια λέξη-κλειδί για να το ψάξω είναι αρκετό, αλλά φυσικά μια εξήγηση ή πηγαίος κώδικας είναι καλύτερα.

[godlike]

καταρχήν στο for ξεκίνα από 0 ως <10 για να μην κάνει την αφαίρεση i-1. Το δεύτερο που μπορείς να κάνεις είναι αφού έχεις βρει τον char να βγαίνει από το for. Δεν υπάρχει νόημα να μένει.Άρα...

 

>int main(void)
{
unsigned short int i,location;
unsigned char word[11],ch;

strcpy(word, "hello world");

ch = 'e';

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

printf("character '%c' is located on position %d\n\n", ch,location);

return 0;
}

[parsifal]

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

 

Εγώ θα ξεκινούσα από εδώ:

...επειδή καλώ μία τέτοια συνάρτηση αρκετές εκατοντάδες φορές, η διαφορά είναι αισθητή.

 

Μήπως με ριζικά διαφορετική προσέγγιση θα μπορούσες να το γλυτώσεις...;

[chiossif]

Γειά και χαρά.

 

Κάπως έτσι θα το έκανα:

 

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

#define COUNTER 100000000

int main(void) {
   unsigned short int i,location;
   unsigned char word[11],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);

   return 0;
}

 

Η χρονομέτρηση με clock δεν είναι αξιόπιστη,

η διαφορά αν υπάρχει αξίζει άραγε τον κόπο;

 

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

 

Και τώρα ένα μικρό quiz. Με μια απλή σκέψη αυτό που έγραψα βελτιώνεται κι' άλλο.

Καμιά ιδέα;

 

Φυσικά "όπως πάντα" υπάρχει bug. Καλοδεχούμενη κάθε διόρθωση.

Ευχαριστώ.

 

Και για του λόγου το αληθές:

>
character 'e' is located on position 2
at 1960000 ticks.
character 'e' is located on position 2
at 370000 ticks.
character 'e' is located on position 2
at 230000 ticks.

Προφανώς η 3η έκδοση είναι το quiz.

[parsifal]

>
   /* 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,[b](*wordptr-ch)?-1:location[/b], ticks);

   return 0;
}

 

Αυτό εννοείς ως bug;

[chiossif]

Ναι.

 

Το bug είναι σε κώδικά μου αφού οφείλει ως λύση να ακολουθήσει τις αρχικές δηλώσεις.

 

Βοήθησα;

[parsifal]

Θα σκάσω, μαρτύρα το!

[FarCry]

Giati de dimiourgeis ena index me ta stoixeia xaraktiron pou exeis. opote kaneis fibonacci search sto index kai katharises.

 

[chiossif]

Ποιό το quiz ή το bug;

Για το δεύτερο ξέχνα το, δεν το ξέρω,

για το πρώτο θα δώσω ευκαιρία και σε κανένα άλλο φίλο να το παλέψει.

( 48 ώρες είναι καλά; Είναι αρκετά πιο εύκολο απο παλαιώτερα quiz.

βλ. http://www.insomnia.gr/vb3/showpost.php?p=1458466&postcount=68 )

 

Όποιος βρίσκει κάτι ας στείλει τα ticks του.

ή εναλλακτικά αποτελέσματα δικής του χρονομέτρησης.

 

Φίλε parsifal, μην σκας. Just sleep with it...

[parsifal]

***EDIT: Άκυρη η λύση με iteration βάσει του pointer μόνο...

[parsifal]

Περιττός έλεγχος στη συνθήκη που ελέγχει την έξοδο από το for loop. Έτσι βγήκε πιο γρήγορο:

 

 

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

#define COUNTER 100000000

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

strcpy(word, "hello world");
ch = 'r';

/* 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 at: %ld ticks.\n", ch, location, ticks);

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

return 0;
}

 

 

character 'r' is located on position 9 at: 5531 ticks.

character 'r' is located on position 9 at: 3750 ticks.

[Directx]

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

Η ταχύτητα εύρεσης αποτελέσματος με bsearch θα είναι θαυμάσια.

[FarCry]

I fibonacci search einai pio grigori apo ti bsearch giati sxetizetai me to golden ratio .

 

kai qsort me random pivot allios Heapsort

 

[paulogiann]

Hash tables-direct addressing

Insert-Search-Delete σε O(1).

[chiossif]

Φίλοι,

αν κατάλαβα καλά, το πρόβλημα αφορά ένα (1) sting -το οποίο ΔΕΝ είναι τεράστιο- στην C και ένα χαρακτήρα. Είμαι περίεργος να "δω" υλοποιημένες τις λύσεις που προτείνετε σε αυτό το πρόβλημα.

 

@parsifal:

 

Σωστά έβγαλες κάτι αλλά μήπως έπρεπε να προσθέσεις κάτι κάπου αλλού; Για ψάξε για τον χαρακτήρα 'x' που δεν υπάρχει; Πρέπει και αυτό να το αντιμετωπίζουμε... (με άλλα λόγια: Καλή η αρχή αλλά κάνε και το σωστό φινίρισμα).