CODEWITHSUNDEEP
cperformancestructlinked-list
Thatdude1
Thatdude1

Reputation: 903

Efficiency with a Structure

I have the following structure

struct scoreentry_node {
    struct scoreentry_node *next;
    int score;
    int max;
    char name[1];    
}
;
typedef struct scoreentry_node *score_entry;

And i have the function add that builds my structure:

int max(int a, int b) {    
   if (a > b) return a;
   return b;
}

score_entry add(int in, char* n, score_entry en) {      
   score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n))
   if (en == NULL){ r->max = in; }
   else {  r->max = max(in, en->max); }
   r->score = in;
   strcpy(r->name, n);
   r->next = en;  
   return r;   
}

I have the following function, that scans through my structure searching for a name and produces the highest score of that name:

int maxiscore(score_entry a, char* name)
{    
 int highestscore = -1000000000;    
   for (a; a != NULL; a = a->next)
    {
      if (strcmp(a->name, name) == 0 && a->score > highestscore)
        {
          highestscore = a->score;                
       }
     }
 return highestscore;
}

I was wondering if i can make my maxiscore function run in O(1) [doesn't have to scan through my structure]? I was thinking about adding another field to my struct but i have to consider that it need's to vary depending on a specific inputted name. Any Suggestions/ Hints?

Upvotes: 0

Views: 143

Answers (2)

iehrlich
iehrlich

Reputation: 3592

You can wrap a set of the structures in a scorelist class containing score_entry pointer to the first element and biggest score (and a pointer to related element) among contained entries. You can update the biggets score on add() and rewrite the pointer. You will be able to access an element with biggest score in O(1).

Upvotes: 0

torek
torek

Reputation: 489498

As some commenters noted this is basically an algorithm / data-organization question.

You can spend time creating "organized" data structures, such as a per-user score table, hashes, balanced trees, and so on; or you can spend time searching "disorganized" data structures. There are even hybrid approaches: create them "disorganized" and then organize them on the fly, as needed (e.g., splay trees).

If you already have information about what you will "do the most", you can optimize now. Otherwise, if you want to be able to optimize later, decide what sort of functionality you require, and provide specific functions to "do each thing" (add a name with a set of scores? add one name with one score? find all scores for a particular name? find the N highest scores? find the N highest scores for a particular name? any/all of the preceding? etc). Once it's all working, use profiling to find out where the time goes, and then choose how to organize the data accessed via those function(s).

As it is, I think your question starts a little "too low level", i.e., "I already have this particular set of nails, so which hammer should I use" when maybe screws or glue would be better. :-)

Upvotes: 1

Related Questions