hash - インタビュー : 文字列内の文字の最初の出現を効率的に検索する方法は?

Question

私のインタビュアーは、文字列内の文字の最初の出現を効率的に検索する方法を私に尋ねました。

私はハッシングを使用すると言いましたが、彼はそれを処理するためのメモリ効率の良い方法を望んでいました。インデックスが失われるため、文字列を並べ替えてバイナリ検索を実行することは問題外です。

インタビュアーは私の答えに満足していないようだった. 他に何か言えることはありますか？

Answer 1

ポインターを使用して最初に出現したものを検索してみませんか。これが最も効率的な検索方法です (4 バイトまたは 8 バイトのデータが必要です)。

unsigned long findIndex(char ch){
  char *str = "some really long; string; here";
  char *ptr = str;
  while(*ptr != ch || *ptr != '\0'){
     ptr++;
  }
  return (unsigned long)(ptr - str)
}

計算科学の基本法則: スペースを最適化するか、実行時間を最適化できます。

ソフトウェア エンジニアリングの基本法則: 「コンピューター科学者」の言うことをよく聞いて、最適な中間点を見つけてください。