我有以下结构
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) 中运行[不需要扫描我的结构]?我正在考虑向我的结构添加另一个字段,但我必须考虑它需要根据特定输入的名称而变化。有什么建议/提示吗?
最佳答案
正如一些评论者指出的那样,这基本上是一个算法/数据组织问题。
您可以花时间创建“有组织的”数据结构,例如每个用户的分数表、散列、平衡树等;或者您可以花时间搜索“无组织”的数据结构。甚至还有混合方法:将它们创建为“无组织”,然后根据需要动态组织它们(例如,伸展树(Splay Tree))。
如果您已经了解了自己将“最常做的事情”,那么您现在就可以进行优化。否则,如果您希望以后能够进行优化,请决定您需要什么类型的功能,并提供特定的函数来“做每件事”(添加带有一组分数的名称?添加带有一个分数的一个名称?查找所有分数对于特定名称?找到 N 个最高分数?找到特定名称的 N 个最高分数?前面的任何/所有?等等)。一旦一切正常,使用分析来找出时间都花在哪里,然后选择如何组织通过这些函数访问的数据。
事实上,我认为你的问题开始有点“太低级”,即“我已经有了这套特殊的钉子,所以我应该使用哪把锤子”,而螺丝或胶水可能会更好。 :-)关于c - 结构效率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9960186/