Binary Interpolation Searching ( δυαδική αναζήτηση παρεμβολής)

[loserman]

Binary Interpolation Searching υλοποιηση σε γλωσσα C

bis.pdf

[AlexHello]

Καλή τύχη με την άσκηση σου

[Alithinos]

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

 

Τι περιμένετε, χαμάλη να σας λύσει την εργασία ?

[M2000]

Σε php είναι εδώ αλλά το άρθρο είναι ωραίο!

http://www.stoimen.com/blog/2012/01/02/computer-algorithms-interpolation-search/

[nilosgr]

35€

[moukoublen]

Πραγματικά... Ούτε να γράψει κάτι στο post έτσι για το καλό.

 

Δηλαδή οκ. Ξέρω οτι υπάρχουν πάρα πολλοί φοιτητές στην Ελλάδα που αν κάποιος τους έλεγε 

"Να σου δώσω το πτυχίο έτσι;" θα ήταν υπέρ-ευτυχείς.

 

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

Πάμε σε κάτι πολύ πιο βασικό] 

 

Απλά δε μπορώ να καταλάβω τι σκέφτεται ο τύπος;

 

"Θα πετάξω την εκφώνηση στο insomnia και θα μου γράψουν τη λύση. Έτσι. Χωρίς πολλά πολλά".

 

Δηλαδή στο κέντρο λογικής του μυαλού τους δεν τους δημιουργείται η απορία

"Γιατί να μου δώσεις κάποιος τη λύση έτσι απλά?"

"Πόσο μάλλον επειδή απλά πετάω μια εκφώνηση στο post χωρίς να λέω τίποτα!"

 

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

 

[sorry για το off-topic ανθρωπολογικό προβληματισμό μου]

[gon1332]

 

Τι φάση; Glory hole;

 

[Kercyn]

Δεν τους νοιάζει. Σου πάω στοίχημα ότι ακριβώς το ίδιο post υπάρχει σε καμιά δεκαριά forums προγραμματισμού ακόμα. Σου λέει το ρίχνω παντού και άμα μου το λύσει κανείς έχει καλώς, αλλιώς δε με πολυνοιάζει κιόλας.

[moukoublen]

Δεν τους νοιάζει. Σου πάω στοίχημα ότι ακριβώς το ίδιο post υπάρχει σε καμιά δεκαριά forums προγραμματισμού ακόμα. Σου λέει το ρίχνω παντού και άμα μου το λύσει κανείς έχει καλώς, αλλιώς δε με πολυνοιάζει κιόλας.

 

Σωστό. Απλά είναι εντυπωσιακά θλιβερό. 

 

Δεν προσπαθεί έτσι κι αλλιώς για το αντικείμενο και την άσκηση 

και δεν προσπαθεί ούτε στο ελάχιστο για να την "κλέψει" (/να του την κάνουν/ να την αντιγράψει/ κτλ κτλ).

 

Μια καθολική παραίτηση ας πούμε. 

 

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

 

[όχι μόνο αυτός φυσικά. Κατα καιρούς υπάρχουν πολλοί αντίστοιχοι.]

[the other one]

δε πειράζει λιγότερος ανταγωνισμός για τους υπόλοιπους

[kaliakman]

Και το θέμα είναι ότι αν όση ώρα έκανε να φτιάξει λογαριασμό πάταγε στο γουγλη την εκφώνηση άνοιγε το πρώτο λινκ έβρισκε την λύση..

 

https://en.m.wikipedia.org/wiki/Interpolation_search

[M2000]

Βαρύ αλλά κάνει για reference σε πτυχιακή: http://www.ijcte.org/papers/575-A280.pdf

[Επισκέπτης]

δε πειράζει λιγότερος ανταγωνισμός για τους υπόλοιπους

 

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

[imitheos]

Binary Interpolation Searching υλοποιηση σε γλωσσα C

int BIS(int *k, int l, int q) {
    uint32_t b=0,a=9,d=q-1;

    while (b[k]<=l&&d[k]>=l) {
        a=b+((l-b[k])*(d-b)/(d[k]-b[k]));
        if (k[a]<l) b=a+1;
        else if (k[a]>l) d=a-1;
        else return a;
    }
    return (*(k+==l)?b:-1;
}

Proof of Concept:
% cc -Wall tmp.c 
% cat file|./a.out 11
Read 631625 entries
Searching for 11
Found at file position 6

% cat file|./a.out 115
Read 631625 entries
Searching for 115
Found at file position 69

% cat file|./a.out 1151
Read 631625 entries
Searching for 1151
Found at file position 715

% cat file|./a.out 11515
Read 631625 entries
Searching for 11515
Found at file position 7260

% cat file|./a.out 115156
Read 631625 entries
Searching for 115156
Found at file position 72902

% sed -n "7p;70p;716p;7261p;72903p" file    
11
115
1151
11515
115156

[Ψιτ]

Γιατί;