w.l.o.g.
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
【C++】テキストエディタのバッファ データ構造・アルゴリズム【第３回】 | TECH PROjin
目次 gap_buffer<char> gap_buffer<char> 前章でも言及したように、テキストエディタにおいてはテキストの参照・編集箇所は局所化されている。 この性質を利用し、vector を高速化したものが gap_buffer （ギャップバッファ、gap vector とも呼ばれる）だ。 vector と gap_buffer のデータ構造の違いは少なく、前者がアロケートしたデータ領域の後ろに未使用部分があるのに対して、 後者はデータ領域の途中に未使用部分があるという点だけだ（下図参照）。 この未使用部分を「ギャップ」と呼び、常に編集位置に設定される。 このようにデータ構造を少し変えただけで、なぜ高速化されるのか不思議に思われる方も少なくないだろうが、 高速になる理由は、挿入・削除時に何が起こるかを見てみると納得していただけるはずだ。 編集位置に ‘a’, ‘b’ が挿入さ
テキストエディタを作る
ここの記事を更新するのは約1年ぶり。夏の間は遊んでいたり秋からは仕事が忙しくなったりの近況だった。 コロナウィルスで自宅に閉じ込められてしまったので、プログラミングの練習のためにテキストエディタを作ってみた。 得られた知見などを紹介しよう。 目標としている機能・実装 練習・教材用として十分な小ささ。 記事のネタになる。また、作っていて飽きない。ひと篭もりするプロジェクトとして適切なサイズ。 昔から、プログラマなら作ってみたいものとして、(1)コンパイラ (2)OS (3)エディタ、がよく挙げられる。コンパイラについては以前に書いた。今回はエディタにチャレンジしてみることにした。 テキストエディタを作る場合、GUIツールキットを使って作成することも考えられるが、今回はviのようにターミナル上で動作するタイプのものを作る。時間があれば、次の様な発展的な目標も検討したい。 設定変更機能を持つ（そ
blog dds: 2006-06-26 — Dave Prosser's C Preprocessing Algorithm
For about five years I've been trying to implement a fully conforming C preprocessor for the front end of the CScout refactoring browser. I've found this to be a fiendishly difficult task. Although what I have written can correctly process million-line real-life projects, every once in a while I come across a construct that confuses my implementation. While searching the web for explanations of so
Goで作るテキストエディタ - Sansan Tech Blog
はじめに みなさんこんにちは。Sansan事業部プロダクト開発部のiOSエンジニア荒川です。 以前はRDBMSの記事*1を寄稿し、好評いただいたこともあり、定期的に車輪の再発明系の記事を書いていこうと思います。 さて本日はタイトルの通り、VimやEmacsに代表されるターミナルで動作するインラインテキストエディタをGoで開発してみました。 ソースコードは以下のリポジトリに置いているため、ぜひ参考にしてください。 github.com 完成品 文字だけだとイメージも湧きにくいので、まずは完成品をお見せします。 最低限エディタの動きは出来ている、というレベルの完成度ですね🙏 特徴 1000行インラインエディタ 文字入力/挿入/削除 画面スクロール キーボードショートカット ファイル読み込み/保存 Goのコードハイライト機能 実装の方針 今回はただ開発するだけではなく、いくつかのこだわりポイン
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
Binary search with modern processors
第16回 StringBeginners での発表資料
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I
「Goの父」ロブ・パイクの「プログラミング5カ条」、ネット上で話題に
「UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている」「キャッシュはアーキテクチャではない。単なる最適化だ」などの語録を生んだ「Goの父」とも呼ばれるロブ・パイク氏の「プログラミング5カ条」について、ネット上で話題となっています users.ece.utexas.edu/~adnan/pike.html http://users.ece.utexas.edu/~adnan/pike.html Rob Pike's Rules of Programming (1989) | Hacker News https://news.ycombinator.com/item?id=24135189 パイク氏の「プログラミング5カ条」は以下。 ルール1：プログラムのどこで処理時間がかかるかはわからない。ボトルネックは意外な場所で発生するので、ボトルネックがどこにあるかを証明するまでは、臆測
「不安のアルゴリズム」を実際に開発して走らせることで不安の原因と解決法を探る
日常的に抱いてしまう「不安」をコントロールするにはどうすればいいのか、ということを探るため、2020年1月にサービスが終了した旅行検索エンジン「Hipmunk」の共同創業者であるアダム・ゴールドスタイン氏が、「不安のアルゴリズム」を開発し、実際にシミュレーションを行うことで不安の原因や解決策を説明するという試みを行っています。 The Contagion of Concern — Adam Julian Goldstein https://www.adamjuliangoldstein.com/blog/contagion-of-concern/ ゴールドスタイン氏はHipmunkを運用する中で、「物事がうまくいっている時にいい出来事が起こると気分がよくなるが、物事がうまくいっていない時にいい出来事が起こっても『いいこと』だと見なせない」ことに気づきました。なぜ現実の物事が自分の認知に影響
アルゴリズム図鑑 - Google Play のアプリ
見て分かる、試して分かるたのしいアルゴリズムの図鑑。幅広い分野のアルゴリズムを、アニメーションでやさしく解説。さまざまに試せる実験モードで理解がさらに進みます。暗号化、セキュリティなど身近なアルゴリズムも満載。さあ、アルゴリズムの世界に旅立ちましょう！ 【 カテゴリと掲載項目例 】 《 ソート 》 バブルソート、ヒープソート、クイックソートなど６項目 《 クラスタリング 》 k-means法 《 リスト探索 》 線形探索、２分探索 《 グラフ探索 》 幅優先・深さ優先探索、ダイクストラ法、Ａ＊(エー・スター)など５項目 《 数学 》 ユークリッドの互除法、素数判定法 《 データ圧縮 》 ハフマン符号、ランレングス符号 《 セキュリティ 》 セキュリティ・暗号の基礎、共通鍵・公開鍵暗号方式、デジタル署名・証明書など10項目 《 データ構造 》 リスト・配列、スタック・キュー、２分探索木など７
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
プログラマの実力は経験だけであがらないことがレベル格差につながる - きしだのはてな
プログラマというのは、道具に慣れることが、実力があがることにならないのですよね。だから、勉強せず業務経験だけだとレベルが低いままということになってしまう。 Javaを10年さわり続けて、Strutsを5年さわり続けても、それだけでは、与えられた画面を手際よく作成できるようになるだけで、たとえばStrutsすらよりよく使えるようになるわけではなかったりする。 Javaにしても、「volatileってなんですか？」という問いに、まあ知らないのはしかたないとしても、解説を見ながらですら答えられない可能性がある。 プログラムの反復生産は、プログラミング能力の向上にあまりつながらない。設定や記述に慣れるだけだ。そして、この「慣れ」というのには「難しいからそもそも実装を回避する」というようなものも含まれる。実力の向上は、作業ができるレベルで止まってしまう。 プログラマとしての実力をあげるための勉強が自
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AtCoder Problems
Learn X in Y Minutes: Scenic Programming Language Tours
GitHub - johnmeacham/lzjwm: lzjwm tiny ascii compression algorithm.
Cholesky decomposition - Rosetta Code
https://www.cec.uchile.cl/cinetica/pcordero/MC_libros/NumericalRecipesinC.pdf
プログラムを高速化する話
