私はstd :: stringsを使って簡単なテキストエディタを作りたいと思っています。テキストが500,000文字で、253,000文字目の文字を挿入または削除したい場合、これは遅くなるか、または文字数が10文字の場合と同じくらい速くなりますか?そうでなければ私は私がリンクリストを使用しますが、その後の読み取りが遅く、それは車輪の再発明の一種でなければ(それを修正するためにやるのかわからないんだけど。std :: stringsはランダム挿入/ランダム消去で良好ですか?
おかげ
私はstd :: stringsを使って簡単なテキストエディタを作りたいと思っています。テキストが500,000文字で、253,000文字目の文字を挿入または削除したい場合、これは遅くなるか、または文字数が10文字の場合と同じくらい速くなりますか?そうでなければ私は私がリンクリストを使用しますが、その後の読み取りが遅く、それは車輪の再発明の一種でなければ(それを修正するためにやるのかわからないんだけど。std :: stringsはランダム挿入/ランダム消去で良好ですか?
おかげ
私はそれを自分自身使ったことがないが、私は、これはropeが何のためにあるのかと考えています。
それは可能性が高いので、遅くなりますそれはメモリをコピーすることがある。それは、オペレーティングシステム/プロセッサとメモリ操作の内部実装に依存します。
問題が発生するほど遅いかどうかはテストする必要がありますが、遅い可能性があります。代替の実装では、1行のテキストにつき1つの文字列のリストを使用します。
これは間違ったタイプです。
std :: stringの(最後ではなく)挿入は、O(n)の複雑さを持ちます。
O(1)の挿入/削除/変更に平均的な複雑さを持つ構造が必要です。
ie。挿入コストはデータのサイズに関係してはならない。
O(n)は、何らかの因数Kに対して、演算がK * nを要することを意味します。これは、Kが小さい場合、ナノ秒のように小さくなります。 –
@Bo Persson:そうではありません。これは単にあなたが問題を遅らせることを意味します。 –
/sのメモリ帯域幅はGBで与えられていることを考えると
http://en.wikipedia.org/wiki/DDR3_SDRAM
どのくらいあなたがコピー256Kがかかるだろう見積もるでしょうか?
非常に安価な操作であっても、頻繁に実行するとパフォーマンスのボトルネックが深刻化する可能性があります。何百万回も操作を行い、2つの実装間の速度差にも100万を乗じます。 ;) – Mephane
@Mephane - 誰でもテキストエディタに1文字ずつ100万文字を挿入することは考えられません。 :-)そして、テキストエディタで他の問題を開始する前に**これを心配することは間違いなく時期尚早の最適化です。 –
実際には、おそらく「十分に速い」でしょう。しかし、私は でもEditBufferクラスを作成し、カプセル化して、 にこの新しいクラスに私のアプリケーションに合わせたインターフェイスを与えます。そうすれば、 私はstd :: stringを使用していて、何か他のものではないという事実は、 のEditBufferの実装の詳細になります。 はいつでも変更できます。 (あなたはstd :: vector も試したがっているかもしれません.1つの一般的な最適化では、 にカーソルを置いています:カーソルの後のテキストは バッファの最後にあります。 通常は一定時間内に挿入されます)。
テキストを1つの大きな文字列ではなく個々の行として保存することを真剣に考えています。 std::list<std::string>
またはstd::vector<std::string>
が適切と思われます。そのようなアプローチは、大きな文字列を複数の小さな文字列に効果的に配布し、変更後の再割り当ては、個々の行またはそれ自身の行の配列に対してのみ発生します。あなたが選択しなければならない唯一のトレードオフは、std :: vectorとstd :: listの間ですが、私はstd :: listを好む傾向があります。
また、ファイルを読むときに、std::getline
で1行ずつ簡単に読むことができ、自分でバッファを読み上げる必要はありません。
"シンプルなテキストエディタ"で作業しているときに、あなたが "ホイールを再発明する"ことを嫌っているのはかなり面白いと思います。 –
@Luc:それは、 "ホイールを再発明する"と "より良いマウストラップを作る"の間の重要な違いです! –