4
\$\begingroup\$

This code removes repeated words from a word array (2D char array). I want to optimize this as much possible for speed.

#include "stdio.h"
#include "string.h"

main()
{
    char words[2000][20];

   /*This array is populated by some other module. possible example of this array is given below, but in reality it would far more elements.
        char words[6][20] = 
    {
        {"barrack"},        
        {"david"},
        {"John"},
        {"david"},
        {"benjamin"},
        {"barrack"}

    };*/


    int names_found = 10;
    char out_words[6][20];
    int i,j;
    int act_names=0;

    for (i = 0; i < names_found; i ++)
    {
        j = i + 1;
        while (j < names_found)
        {
            if (strcmp(words[i], words[j]) == 0)
            {
                memmove(words + j, words + (names_found - 1), sizeof(words[0]));

                -- names_found;             
            }
            else
                ++ j;
        }
    }
    for(i=0;i<names_found;i++)
    {
        printf("%s\n",words[i]);
    }


}
  1. How can the 2 for loops for i and j above be optimized?

  2. As you see, the above logic currently outputs to same input buffer (in-place processing). Can it be optimized further if we allow a second buffer say char out_words[2000][20]?

\$\endgroup\$
7
\$\begingroup\$
  1. Your algorithm is \$O(n^2)\$. You can reduce this to \$O(n)\$ by first inserting them into a closed hash table (i.e., one with bucket chains).

  2. I'd optimise is rather than copying the whole items, just copy pointers to the original strings (unless you intend to alter their contents later on).

\$\endgroup\$
2
  • \$\begingroup\$ Thanks. Could you point to more details about your first point of closed hash table. \$\endgroup\$ – goldenmean Jul 17 '11 at 11:00
  • \$\begingroup\$ Sorry, that was probably too fine a detail. With a closed hash table, insertion is trivial (you don't have to do multiple probes) and it gathers all items with the same hash in the same bucket chain (hopefully your hash function will not map too many different strings to the same number). \$\endgroup\$ – Rafe Jul 17 '11 at 21:49
2
\$\begingroup\$
  • The #includes should use <> since these are libraries. You should only use "" for your own header files.

  • Consider splitting this program into separate functions. You could have two: one for doing the modifications and another for doing the displaying. You could then have main() call these functions, one at a time.

  • The display loop looks unsafe:

    for(i=0;i<names_found;i++)
    {
        printf("%s\n",words[i]);
    }
    

    Before entering this loop, you should make sure that names_found is not too large, otherwise the loop will access the array go out-of-bounds.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.