Удалить повторяющиеся слова из 2D массив символов


Этот код удаляет повторяющиеся слова из слова массив (в 2D массив char). Я хочу оптимизировать этот максимально возможную скорость.

#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. Как 2 для петли, Для я и Джей выше оптимизированных?

  2. Как вы видите, выше логики в настоящее время выводит к той же входной буфер (в месте обработки). Это может быть оптимизирован еще больше, если мы позволяем второй буфер говорят Чаре out_words[2000][20]?



898
3
задан 17 июля 2011 в 07:07 Источник Поделиться
Комментарии
1 ответ


  1. Ваш алгоритм \$o(п^2)\$. Вы можете уменьшить это до \$О(П)\$ первый вставляя их в закрытой хэш-таблицы (т. е., один с ковшом цепи).

  2. Я бы оптимизировать, а не копировать все элементы, просто скопировать указатели на исходные строки (Если вы не намерены изменять их содержимое позже).

6
ответ дан 17 июля 2011 в 07:07 Источник Поделиться