C++を用いて、文字列検索などの実装を学習。より実践的な内容で、C++をスキルアップ！
2020.11.18
Developer Lv3
目次 Undo/Redo おわりに Undo/Redo 現実世界の行動に Undo は効かないが、多くのアプリケーションには Undo 機能があり、行った操作を取り消すことができる。 手が滑って大事なテキストの一部を消してしまったとき、アプリの Undo 機能に救われた人も少なくないと思う。 さらに …More Read
2020.11.18
Developer Lv3
目次 gap_buffer<char> + 行管理 gap_buffer<char> + 行管理 gap_buffer<char> は1次元的で、文字位置を0オリジンの数値で指定するが、テキストエディタではテキストを行単位で表示するので、行番号と行先頭 …More Read
2020.11.16
Developer Lv3
目次 gap_buffer<char> gap_buffer<char> 前章でも言及したように、テキストエディタにおいてはテキストの参照・編集箇所は局所化されている。 この性質を利用し、vector を高速化したものが gap_buffer （ギャップバッファ、ga …More Read
2020.11.16
Developer Lv3
目次 list<string> list<string> ＋ 行番号キャッシュ list<string> 前章で取り上げたテキスト全体を単に１次元に並べたデータ構造では、 先頭付近での挿入・削除の繰り返しが O(N*N) と低速で、実用上問題があること …More Read
2020.11.16
Developer Lv3
目次 はじめに バッファとは vector<char> はじめに 最近、筆者はオープンソース版 ViVi テキストエディタの開発を行っていて （参照：https://github.com/vivisuke/openViVi）、その実装には様々な種類の実装技術を利用している。 実は前回 …More Read
2020.11.13
Developer Lv3
目次 bitap – 大文字小文字同一視 – パフォーマンス計測 おわりに 前回は長い検索パターンで特に高速になるBMH法について解説した。 BM系やKM系は、文字比較を行った結果の情報を有効に使うことで高速化したが、 今回は、筆者の大好きなビット演算を用いて、パイプライン的 …More Read
2020.11.13
Developer Lv3
目次 BMH – 大文字小文字同一視 – パフォーマンス計測 前回は力まかせ（ブルートフォース）探索について解説した。 今回は、それを高速化したアルゴリズムのひとつであるBMH法について解説する。 BMH（Boyer–Moore–Horspool）アルゴリズム 本章では、前章 …More Read
2020.11.12
Developer Lv3
目次 はじめに 力まかせ（ブルートフォース）検索アルゴリズム – BF (strstr) – strchr + BF (strchrstr) – strcasestr – パフォーマンス計測 はじめに これまではパズル系アルゴリズムについて解説してきた …More Read
