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
2020.09.01
Developer Lv3
前編より引き続き、ナンバーリンクソルバーの具体的なコードの解説を行う。 バックトラッキング関数 bool BoardK::doSolveBT(int ix) // ix の状態を決める { if( ix > xyToIndex(m_width, m_height) ) { // 全てのセルを無 …More Read
2020.09.01
Developer Lv3
目次 はじめに ナンバーリンク ソルバー L データ構造 L ブルートフォース L バックトラッキング はじめに ナンバーリンク ナンバーリンクとは WxH の矩形盤面に１～Nまでの数字をそれぞれ２個ずつ配置し、 全部のセルを埋めて、縦横方向だけ（斜め線不可）で同じ数字をつなげるというパズルだ。 下 …More Read
2020.06.16
Developer Lv3
ビット演算（ビットマップ）による高速化 前章では配列の配置フラグを使用することで高速化を達成したが、本章ではビット演算によりさらに高速化してみよう。 int cols の各ビットが、各カラムにクイーンを配置可能かどうかを表すものとする。 最初は全てのカラムに配置可能なので、初期値は全ビットが立ってい …More Read
