0

こんにちは、私は2D char配列を持っている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?

     }

重複した単語を削除するこのロジック
は、機能的に正しいですか?

速度を最適化するにはどうすればよいですか。

より良い/より高速なソリューション。

4

3 に答える 3

1

これをより速く行う方法と方法はありますが、必ずしもそのような小さなセットには必要ありません。また、名前を削除するためのロジックは、回避する必要がある配列にギャップが発生するか、ギャップを埋めるために回答を memmove() する必要があるため、おそらく思ったよりも時間がかかります。

Boyer-Moore タイプの検索をオフにすると速度が向上する可能性がありますが、strcmp 関数の速度によっては、ルックアップの設定などのオーバーヘッドが原因で、これによるメリットが得られない場合があります。正しく設定すれば、代わりに strstr() を検索に使用できる可能性があります。これは、より高度な検索アルゴリズムを使用する可能性があります。

基本的に、セットは非常に小さいため、ここでの最適化は少し時期尚早かもしれません。

于 2011-07-16T22:45:03.093 に答える
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;
    }
}
于 2011-07-16T23:35:58.697 に答える
0

論理的には問題ありません。配列要素ごとに、次の要素に等しいものが他にあるかどうかを検索し、そうである場合はそれらを削除します。ただし、配列のサイズを動的に変更する必要があります。たとえば、最初の要素の 3 つの重複を削除すると、残りの要素数は よりも少なくなるnames_foundため、それに応じて更新する必要があります。

配列を並べ替えると（高速並べ替えアルゴリズムを使用しますが、データのサイズに依存する場合があります）、重複がすべて「並べて」表示されると、高速化できます。N個の重複を見つけた場合、他のすべての配列要素をN個の位置だけ戻す必要がないため、宛先配列を使用すると高速になります(最悪の場合、ソース配列と同じサイズの配列が必要です)。

もう 1 つのアプローチは、ハッシュ コンテナーを使用することです。この場合、ライブラリが必要になり (たとえば、glib にはハッシュテーブルの「オブジェクト」があります)、コードは異なって見えます (たとえば、ハッシュテーブルに入力するときに重複を「スキップ」できます)。

于 2011-07-16T22:52:32.337 に答える