我有3组项目(名称)。第1组大约有2.1万项,第2组-大约有7.6k,第3组有大约21k。我需要在这些组中搜索。我需要一个更好的提示。我以为可以全部放到bin树上:
GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
and search like this:
goup = g_tree_lookup(t, (gpointer *)itemName);
还是制作3个字符串数组会更有效:
char g1[2300][14];
char g2[8000][14];
char g3[78000][14];
并像这样搜索(未选中,伪代码):
int isvalueinarray(char val, char *g[][14];, int size){
int i;
for (i=0; i < size; i++) {
if (memcmp(val, g[i], strlenth) == 0)
return true;
}
return false;
}
int i group=0;
if (isvalueinarray(itemName, g2, 7800) ) group = 2;
if (isvalueinarray(itemName, g1, 2300) ) group = 1;
还是有更好的解决方案?
如果您想要一种最渐近有效的方法来查找字符串是否在可以预处理的一组字符串中,则可以考虑使用trie。构造时间是线性的(O(L),其中L是三组中所有字符串长度的总和),查找时间与要查找的字符串的大小呈线性关系(这就是您的情况) ,14)。
二进制搜索树也是一个不错的选择,可以为您提供对数(按字符串集的大小)的性能。这可能会比较慢,但可能更容易实现。请注意,预处理(将三个集合的所有字符串插入树中)需要N * log(N)时间,其中N是集合大小的总和。
不要在数组中使用线性搜索,因为它太慢了。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句