- 【初心者歓迎】C/C++室 Ver.97【環境依存OK】 [転載禁止]©2ch.net
30 ：デフォルトの名無しさん[sage]：2015/11/28(土) 10:32:03.28 ID:tW/rjk30 - >>27
部分一致検索をするには大きく分けて
・検索される側の文字列を変換して検索に特化させる
・検索する側の文字列を変換して検索に特化させる
・検索される側・する側どちらも何ら変換しない
の3通りの方法がある。
最初のはは例えば接尾辞配列を作ってそれを保持するって方法で、
これは検索される側の文字列長をnとした時にO(n log n)償却時間で変換する方法や
O(n log^2 n)最悪時間で変換する方法なんかが知られている。
検索時間は検索する側の文字列の長さに依らずO(log n)平均時間
次のは例えば正規表現を有限状態オートマトンに変換する方法で、
その正規表現の長さをm、検索される側の文字列の長さをnとする時にO(m^3)平均時間、
O(m^2 * 2^m)最悪時間で構築してO(n)時間で検索できる方法が知られている。
データベースに何でもかんでもぶち込むだけが方法じゃない。
データの総量が増えないなら前者の方法で準線形時間掛けて初期化しておけば対数時間で検索できるし、
データが追加されうるならとりあえず何らかのファイルに1行につき1エントリの形式で書き込んでおいて
後者の方法を使えば線形時間で検索できる。
特に、後者の場合は(1行につき1エントリという形式にしておけば)Unixのgrepコマンドが使える。
|
- 【初心者歓迎】C/C++室 Ver.97【環境依存OK】 [転載禁止]©2ch.net
31 ：デフォルトの名無しさん[sage]：2015/11/28(土) 10:41:03.68 ID:tW/rjk30 - ごめん
> 検索時間は検索する側の文字列の長さに依らずO(log n)平均時間
って書いたけどより正確にはO(m + log n)とかそんな感じ
|
- C言語なら俺に聞け（入門編）Part 131 [転載禁止]©2ch.net
106 ：デフォルトの名無しさん[sage]：2015/11/28(土) 10:45:24.44 ID:tW/rjk30 - >>105
sprintfして、
for (i = strlen(s) - 1; i > 0; i--) {
if (s[i] == '0') {
s[i] = '\0';
} else {
break;
}
}
とかじゃ駄目なの？
というか物理工学の分野だと最後の0にも意味があるから(誤差やら不確かさやらがどうたら)
省略してはいけない筈。
|
- P2P型の完全匿名掲示板はまだ出来ないの？その5
182 ：170[sage]：2015/11/28(土) 17:57:30.82 ID:tW/rjk30 - 具体化しつつ色々考えてたら長くなりすぎたのでgistに書くことにしたよ
https://gist.github.com/pixie-grasper/35a43d0c15d9fe49814b
まぁ新しい所は荒らしの判定ににもっと計算量の小さい簡単な方法が使えるんじゃね？
って事くらいだけど。
簡単に言うと、
今まではユーザーIDとメッセージから同じメッセージIDが作れるか？って問題で解決してて
ちょっと重かったんだけど、ブルームフィルタの考え方を応用したら
もっと簡単に検出出来ることに思い至ったって話。
|