0

配列内の文字列の比較を行う必要があるこのプログラムがあります。最初に考えられるのは、もちろんstrcmp、配列内の 2 つの文字列が同じかどうかを確認するために使用することです。ここで、ポインターを文字列と比較するだけでよいというオプションを考えてみましょう。これには、文字通り同じである各要素をメモリ内の同じ場所にマップするための準備が必要です。

で準備することで、これをすべて実行しましたがstrcmp、今ではstrstr（の方が速いと思います）。しかし、すべての文字列をチェックして最初に出現する文字列にマッピングする必要があるため、準備に非常に長い時間がかかります。この配列は数 MB の大きさであることに注意してください。

これが私がやりたいことの例です：

[0x0: "I", 0x1: "am", 0x2: "done", 0x3: "here.", 0x4: "I", 0x5: "have", 0x6: "done", 0x7: "everything!"]

[0x10: 0x0, 0x11: 0x1, 0x12: 0x2, 0x13: 0x3, »0x14: 0x0«, 0x15: 0x5, »0x16: 0x2«, 0x17: 0x07]

それでは、質問に移ります。この種のマッピングを、私が既に行っているよりも高速に行う別の方法はありますか?

4

1 に答える 1

1

重複が存在するかどうかを確認するだけの場合...qsort()文字列の配列に対して a を実行し、並べ替え関数が重複を見つけた場合は、早期に救済できます。または、重複を削除する必要がある場合は、並べ替えを完了させ、リストの一番下から直線的に反復し、見つかったときにそれらを引き出します (すべての重複が互いに隣り合っているため)。

文字列が比較的異なる場合、strcmp()現実的には、一致の失敗を回避する前に、最初の一握りの文字をチェックするだけで済みます。だから、思ったほど悪くないかもしれません。

確かに、これを簡単に実行できるかどうかは、文字列が実際にどのようにメモリに格納されているかによって異なります。

アップデート：

わかりました、あなたの更新に基づいて...ハッシュテーブルのマットの提案はおそらく最もうまくいくでしょう:

  • リストを 1 つずつ繰り返します
  • 文字列をハッシュする
  • テーブルにすでに存在するかどうかを確認します
  • そうでない場合は、テーブルに追加して続行します
  • その場合は、テーブルの既存のインデックスを使用します
  • ...そして次に進みます。

全体として、比較的まともなパフォーマンスが得られるはずだと思います。

于 2013-08-08T04:03:16.917 に答える