C 代码 - 从 2D 字符数组中删除重复字的逻辑

Question

您好，有一个 C 代码，其中有一个 2D 字符数组 -

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

该数组由一些带有名称的逻辑填充。我在变量名称_found 中跟踪实际找到的名称总数（可能少于 100 个名称）。

现在我想删除可能存在的重复名称。我打算做的是类似的事情。

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?

     }

}
我正在做的这种重复词删除的逻辑在功能上正确吗？

我怎样才能优化它的速度。

任何更好/更快的解决方案。

Answer 1

这是一个简单的方法。它假设名称的顺序并不重要：

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;
    }
}

Answer 2

有很多方法可以更快地做到这一点，但不一定适用于这么小的集合。此外，删除名称的逻辑可能会比您想象的要花费更长的时间，因为它要么会导致您必须解决的数组中存在空白，要么您需要 memmove() 您的答案来填补空白。

即时的 Boyer-Moore 类型搜索可能会加快速度，但根据 strcmp 函数的速度，由于设置查找等方面的开销，您可能不会从中获得任何好处。如果设置正确，您可能可以使用 strstr() 来代替搜索，这可能确实使用更高级的搜索算法。

基本上，您的集合非常小，因此优化可能有点不成熟。

Answer 3

逻辑上是可以的：对于每个数组元素，查找后面的元素是否存在其他相等的，如果有，则将其删除；但你需要动态改变数组大小；例如，如果删除第一个元素的 3 个重复项，则剩余元素的数量小于 names_found，因此您需要相应地更新它。

如果对数组进行排序（使用快速排序算法，但这可能取决于数据的大小），然后重复项全部“并排”，则可以使其速度更快。使用目标数组会更快，因为如果找到 N 个重复项，则不需要将所有其他数组元素向后移动 N 个位置（在最坏的情况下，您需要一个与源数组大小相同的数组）。

另一种方法是使用哈希容器；在这种情况下，您需要一个库（例如，glib 有一个哈希表“对象”），并且您的代码看起来会有所不同（例如，当您填充哈希表时，您可以“跳过”重复项）。