CODEWITHSUNDEEP
carraysalgorithmsearchcoding-style
musicmatze
musicmatze

Reputation: 4288

Looping through array, what is better, faster, etc?

I want to implement a Hash or PHP-like Array. What is better, option a) or option b) to find a element by its key?

(All variables are set and initialized and so on!)

a)

for( i = 0; i < ary->element_cnt && found == NULL; i++ ) {
    current_element = &(ary->elements[i]);
    if( 0 == memcmp(current_element->key, search_key, keysize) ) {
        found = current_element;
    }
}

b) 

for( i = 0, current_element = &(ary->elements[i]) ; 
        i < ary->element_cnt &&  
        0 != memcmp(current_element->key, searchkey, keysize); 
        i++, current_element = &(ary->elements[i]) );
/*found = current_element;*/

Is the first one better because it is much more readable/maintainable? Will the second one be faster?

Is it "bad style" to do everything in one big loop?

I know, there are much better search algos out there, but that's not my problem here!

Upvotes: 0

Views: 161

Answers (2)

Charles Salvia
Charles Salvia

Reputation: 53289

Both of these are O(N) algorithms - they both simply loop over an array and call memcmp for each element - so they should perform similarly. Subjectively, I think the first one is better because it is easier to read.

However, the best way to implement lookup by key is not with a linear search like this, but with a specialized data structure like a hash table or balanced binary tree. Scripting languages like PHP generally use hash tables to implement lookup like this.

Upvotes: 5

unwind
unwind

Reputation: 399833

All matters of style are of course highly subjective. This is the type of thing that is sometimes "regulated" by local code style guides.

Personally I think the call to memcmp() is a bit too "heavy", I would write it as:

for( i = 0; i < ary->element_cnt; ++i ) {
    current_element = &ary->elements[i];
    if( memcmp(current_element->key, search_key, keysize) == 0 )
        break;
}

This cuts out the found check in the loop header, since that is effectively checking the same thing twice which I dislike.

If I really wanted to use found, I would write it as:

for( i = 0; i < ary->element_cnt && !found; ++i ) {
    current_element = &ary->elements[i];
    found = memcmp(current_element->key, search_key, keysize) == 0;
}

This removes the pointless if and just assigns the Boolean directly which I think is nice.

Upvotes: 3

Related Questions