Эффективность со структурой

Question

У меня следующая структура

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

И у меня есть функция add, которая строит мою структуру:

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;   
}

У меня есть следующая функция, которая просматривает мою структуру в поисках имени и выдает наивысшую оценку этого имени:

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;
} 

Мне было интересно, смогу ли я запустить функцию maxiscore в O (1) [не нужно сканировать мою структуру]? Я думал о добавлении другого поля в мою структуру, но я должен учитывать, что оно должно меняться в зависимости от конкретного введенного имени. Есть предложения / советы?

Answer 1

Как отметили некоторые комментаторы, это в основном вопрос об алгоритме / организации данных.

Вы можете тратить время на создание «организованных» структур данных, таких как таблица оценок для каждого пользователя, хэши, сбалансированные деревья и т. Д .; или вы можете тратить время на поиск "неорганизованных" структур данных. Существуют даже гибридные подходы: создавайте их «дезорганизованными», а затем организуйте их на лету, по мере необходимости (например, растягивайте деревья).

Если у вас уже есть информация о том, что вы «сделаете больше всего», вы можете оптимизировать сейчас. В противном случае, если вы хотите иметь возможность оптимизировать позже, решите, какую функциональность вам требуется, и предоставьте конкретные функции, чтобы «делать все» (добавить имя с набором баллов - добавить одно имя с одним баллом - найти все баллы для конкретного имени - найти N наивысших баллов - найти N наивысших баллов для конкретного имени - любое / все предыдущие и т. д.). Как только все заработает, используйте профилирование, чтобы узнать, куда идет время, а затем выберите способ организации данных, к которым осуществляется доступ с помощью этих функций.

На самом деле, я думаю, что ваш вопрос начинается с «слишком низкого уровня», т. Е. «У меня уже есть этот конкретный набор гвоздей, поэтому какой молоток мне следует использовать», когда, возможно, болты или клей будут лучше. : -)

Answer 2

Вы можете обернуть набор структур в классе scorelist, содержащем указатель score_entry на первый элемент и наибольшую оценку (и указатель на связанный элемент) среди содержащихся записей.Вы можете обновить счет биггетов на add() и переписать указатель.Вы сможете получить доступ к элементу с наибольшим счетом в O (1).