Geek asks and answers

Which of the best search algorithms?

I have 3 groups of elements (names). Group 1 has about 2.1 thousand units, group 2 has about 7.6 thousand, and group 3 has about 21 thousand people. I need to search in these groups. I need a hint which is better. I thought I needed to put everything in the basket tree:

 GTree* t = g_tree_new((GCompareFunc)g_ascii_strcasecmp);
 and search like this:
 goup =  g_tree_lookup(t, (gpointer *)itemName);

Or it would be more efficient to create 3 array of strings:

char g1[2300][14];
char g2[8000][14];
char g3[78000][14];

And do a search like this (not verified, pseudocode):

    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;

Or is there a better solution to this?

+3
source share
2 answers

, , trie. (O (L), L - ), , ( , 14).

, ( ) . , , , . , ( ) N * log (N), N - .

, .

+2

O (logN). Log (3N) , 3 * Log (N). (N - )

, , . , , O (N), O (logN).

+4

More articles:


All Articles