Код C - логика для удаления повторяющихся слов из двумерного массива символов - PullRequest
Новая
       6

Код C - логика для удаления повторяющихся слов из двумерного массива символов

0 голосов
/ 17 июля 2011

Привет, у меня есть код C, в котором у меня есть массив двумерных символов как - 

names[100][20] //Currently maximum 100 names, each of 19 characters supported

Этот массив заполняется некоторой логикой с именами. Я отслеживаю общее количество найденных имен (может быть меньше 100 имен) в переменной names_found.

Теперь я хочу удалить дубликаты имен, которые могут присутствовать. То, что я планирую сделать, это что-то вроде. 

for(i=0;i<names_found;i++)
{
    for(j=i+1;j<names_found;j++)
    {
       //Then compare(strcmp) each string/name with every other.
       //e.g. if there were 4 names the comparisons done would be
       //{name[0],name[1]},{name[0],name[2]},{name[0],name[3]}
       //{name[1],name[2]} , {name[1],name[3]}
       //& {name[2],name[3]}
       //And then some more logic to remove duplicate based on result of strcmp    results. Don't know what this logic would look like to store the result in place, in same 2D character buffer?

     }

}
Эта логика удаления повторяющихся слов, что я делаю правильно, функционально?

Как я могу оптимизировать его по скорости.

Любое лучшее / быстрое решение.

Ответы [ 3 ]

1 голос
/ 17 июля 2011

Это простой подход. Предполагается, что порядок имен не важен: 

for (i = 0; i < names_found; i ++)
{
    j = i + 1;
    while (j < names_found)
    {
        if (strcmp(names[i], names[j]) == 0)
        {
            memmove(names + j, names + (names_found - 1), sizeof(names[0]));
            -- names_found;
        }
        else
            ++ j;
    }
}
1 голос
/ 17 июля 2011

Есть способы и способы сделать это быстрее, но не обязательно для такого маленького набора. Кроме того, ваша логика удаления имен, вероятно, займет больше времени, чем вы думаете, потому что это либо вызовет пробелы в массиве, с которыми вам придется работать, либо вам потребуется memmove () вернуть ответы обратно, чтобы заполнить пробел.

Необязательно поиск типа Бойера-Мура может ускорить процесс, но в зависимости от того, насколько быстро работает функция strcmp, вы можете не получить никакой выгоды от этого из-за накладных расходов при настройке поисков и тому подобного. Если вы все настроите правильно, вы можете использовать вместо этого strstr () для поиска, который, вероятно, использует более продвинутый алгоритм поиска.

По сути, ваш набор настолько мал, что оптимизации могут быть немного преждевременными.

0 голосов
/ 17 июля 2011

Это логически нормально: для каждого элемента массива ищите, есть ли другие равные в следующих элементах, и, если это так, удалите их; но вам нужно динамически изменять размер массива; например если вы удалите 3 дубликата первого элемента, то оставшееся количество элементов будет меньше names_found, поэтому вам необходимо соответствующим образом обновить его.

Вы можете сделать это быстрее, если вы сортируете массив (с быстрым алгоритмом сортировки, но это может зависеть от размера данных), а затем дубликаты все «рядом». Использование массива назначения будет быстрее, поскольку, если вы найдете N дубликатов, вам не нужно перемещать все остальные элементы массива назад на N позиций (в худшем случае вам нужен массив того же размера, что и исходный массив).

Другой подход заключается в использовании хеш-контейнера; в этом случае вам нужна библиотека (например, у glib есть хеш-таблица «объект»), и ваш код будет выглядеть иначе (например, вы можете «пропустить» дубликаты при заполнении хеш-таблицы).

...