２次元配列

質問

HTMLの置換を行う時、置換の定義を
だった。,でした。
んだよ。,のです。
ままだ。ままです。
のようにテキストファイルで作ったてあるとします。
置換は行末が対象です。
置換したいHTMLは普通のHTMLではなく、普通のテキストであり、サイズは大きいもので8MBあります。
置換の定義は1つだけ定義して、この定義て5～6個ぐらいのHTMLファイルを置換します。
元データは中途半端な位置に改行が入っていることはありません。
元データは１行が長くても70文字ぐらいです。
置換方法は２種類考えました。
１つは、まず最初に8MBのテキストを１行ごとに配列に入れてからメインループ処理に入ります。
「だった。」だけに注目してHTMLの置換を行って、置換されていない列に対して「んだよ。」で置換を行い、それでも置換されていない列に対して「ままだ。」で置換を行う、というのを繰り返す方法です。
２つ目の方法は、HTMLの１行について、「だった。」「んだよ。」「ままだ。」などを順に検索して置換し、置換したならその要素、例えば「ままだ。」をaの先頭へ持って来てHTMLの２行目を同様に置換、という方法です。
試していないのですが、２つ目の方法の方が速いと思います。
、「だった。」「んだよ。」「ままだ。」などの定義が異常に多ければ１つ目の方法が速いのですが、50ぐらいの定義数です。
それで２つ目の方法にすると思うのですが、aの１次元目のアクセスは２次元目のアクセスに比べて反比例的に多いです。
このような場合、aとbという２つの１次元配列にした方がよいですか？こうすると、aの要祖を入れ替え、例えば「ままだ。」をaの先頭へ持って来る場合、bも同様の処理が必要になります。
ですが、この方法が一番速そうだと思いましたが、この方法をどう思われますか？
意見や考えなど聞かせて下さい。

回答No.2

sadakazuw

eresisyさんのやりたいことをやるには、
置換の出来るテキストエディタを使って、「全て置換」を行うのが
最も早いと思います。対象ファイルも5～6ということなので、
かえってCで行うとトラブルが起きやすいように思います。
Linuxとかなら簡単なシェルスクリプトとsedで一瞬です。
もしくはPerl等の文字列処理を簡単に行える言語を使う方が遙かに
楽です。

もし、どうしてもCで実装しなければならない理由があるなら
とめはしません。その場合は文字コードに気をつけてください。
置換の定義ファイルと置換対象ファイルの文字コードが違うと検索に
引っかからなくなります。また、行を読み込むときに入れる配列の長さは
十分大きくとらないと不正なメモリアクセスが起こる可能性があります。

2次元配列という題目に対する解答からはかなりずれましたが、
C言語で文字列操作のライブラリを使わずに文字列操作をするのは、
とても面倒でバグが発生しやすいのでなるべくやめた方がいいと思います。

回答No.1

osamuy

えーと、そもそもどういったデータ構造で2次元配列なのかがちゃんと説明されてないので、そちらを補足した方が回答がつきやすいかと。

置換の定義をいれてるのが2次元配列だとしたら、
struct {char p[]; char r[]; } a[]
みたいな構造体の一次元配列にした方が、プログラミングの見通しが良くなりますよ。
ただ、
＞置換したならその要素、例えば「ままだ。」をaの先頭へ持って来てHTMLの２行目を同様に置換
――が何を意図してるのかが理解できてないので外してるかもしれませんが。文脈的にはaが2次元配列と思われますが、説明無く突然出てくるので。

計算量として検索のマッチを基準に考えれば、
・出現頻度pのパターンがn個。
・pがパターンによらず一定なら平均(n+1)/2回の検索でみつかる。
・m行のテキストに(n+1)/2回の検索を実施。
――ゆえにO(mn)。
一つのパターンを全行繰り返しにしても、1行に対して複数検索しても、理論的には変わらないかと。
只後者だと1行ずつしか処理しない分ワークセットが小さくCPUキャッシュに収まる可能性があるので、それが性能差になることが期待できるかも。
また「だった。」が一番たくさん書かれているのが自明なので事前にそれを先に検索するようにすれば、検索回数の削減が期待できるといった小細工が考えられます。ほかにハッシュやトライ（trie）をつかって、処理する手も考えられます。

個人的な意見としては、たかだか8MBのテキストを5～6個処理するくらいのものだったら、PerlやVBScriptでスクリプトかけば良いかと思います。多分その方が手っ取り早いです。