テキストエディタで使われがちなデータ構造 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++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
確率的データ構造を使って巨大な集合を定数メモリで近似しよう
巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。 本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。
20分でわかるPurely Functional Data Structures (PDF)
20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題：キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・
Basic Data Structures and Algorithms in the Linux Kernel - The Phrygian Cap
Thanks to Vijay D'Silva's brilliant answer in cstheory.stackexchange.com I have been reading some of the famous data structures and algorithms used in the Linux Kernel. And so can you. Linked lists, doubly linked lists, lock-free linked lists.B+ Trees with comments telling you what you can't find in the textbooks.Priority sorted lists used for mutexes, drivers, etc.Red-Black trees are used are use
Lossy Countingを実装してみた - 省メモリな頻度計測 - 唯物是真 @Scaled_Wurm
大規模データで頻度を数えると、欲しいのはよく登場するアイテムの情報なのに、ほとんど出現しないアイテムの種類数が非常に多くて、それらがメモリを大量に必要としてしまうという問題がある これに対してアイテムの種類数の最大値に制限を加えたり、頻度に誤差を許すなどの条件のもとで、省メモリに頻度計測を行う方法がいくつも提案されている これらについては以下の記事が詳しい 大規模データで単語の数を数える - ny23の日記 今回はそういった手法の一つであるLossy Countingを実装した 日本語では上記の記事と以下の記事が詳しい [を] 誤り許容カウント法(lossy count method)のサンプルプログラム [O] イプシロン劣シノプス性を保持した頻度カウント lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」 元論文はこちら。年を見ると結構前なので、現在ではもっと
B+Trees and why I love them, part I - Ayende @ Rahien
One of the things that I enjoy about learning new things is the way it changes the way I look at the stuff that I already knows. Reading the LMDB codebase, and implementing a persistent B+Tree has given me a new depth of understanding about how relational databases (and Esent, too), work. I am going to go back to level zero and assume that you have never heard about this. You probably know what a
Jetty-9 goes fast with Mechanical Sympathy | Webtide Blogs
Since we discovered how to make Jetty-9 avoid parallel slowdown, we’ve been continuing to work with micro benchmarks and consideration of Mechanical Sympathy to further optimise Jetty-9. As we now about to go to release candidate for Jetty-9, I thought I’d give a quick report on the excellent results we’ve had so far. False Sharing in Queues Queuing is a very important operation in servers like J
マルチコア時代の並列プログラミング～ロックとメモリオーダリング～
~ ~ nminoru@nminoru.jp http://www.nminoru.jp/~nminoru/ Java VM GC JIT Java IA-64 Web Binary Hacks Binary Hacks #94 CPU Out-of-order load/store Load ( ) Store (Store buffering) (memory ordering) CPU ( ) Binary Hacks #94 Store Buffer Store Store1 Store2 Store3 Load Store buffer Main memory/cache Register Store Buffer Cache Main memory Binary Hacks #94 Pthread mutex IPC semaphore Cmpxchg Lock-free sy
モテるアルゴリズム講座 第2回 Skip Graphでモテたい｜株式会社 フラッツ
天方です。 それでは、アルゴリズム講座第2回をはじめたいと思います。 おかげさまで、前回の講座では、公開後、たくさんの知り合いの方から声をかけていただきました。 やはりアルゴリズムがモテるということを実感した第1回講座でした。 さて、今日は、最近クラウドのGoogle App Engine(GAE)で利用を検討したアルゴリズムについて紹介したいと思います。 GAEでは、プログラムをする際に、クラウドの特性を意識する必要があるのですが、それは、アルゴリズム、特に並列アルゴリズムの知識を生かすには非常によい環境ともいえます。 はっきりいいます。GAEでアルゴリズムができるとモテます。 この講座を通じて少しでも皆様にモテをおすそ分けできたらと思います。 さて、本日も前回と同様、アルゴリズムとデータ構造に着目しています。 GAEでは、データを格納するストレージとしてRDBMSを使う代わり
Redis And python at pycon_2011
These is the slide deck which I presented in tutorial section at PyCon India in Pune (India) in 2011.
Kicking ass with redis
Paris Redis Meetup IntroductionGregory Boissinot1.7K views•76 slides
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
プログラミングコンテストでのデータ構造 2 ～動的木編～
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757Read less
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～
続き (動的木編) はこちら http://www.slideshare.net/iwiwi/2-12188845Read less
Scott Logic » Sorted Lists in Java
Mark Rhodes, December 22nd, 2010This post goes through an implementation a SortedList in Java which ensures its elements are kept in order and guarantees O(log(n)) run time for all the basic operations: get, contains, remove and add. The source code, javadoc, unit tests and class files for this post are available here: scottlogic-utils-mr-1.4.zip. Sorting is one of the most common operations appli
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.linuxtag.org/2012/fileadmin/www.linuxtag.org/slides/Ulrich%20Drepper%20-%20Fast_%20less-complicated_%20lock-free%20data%20structures.p3.pdf
あなたの知らないハッシュテーブルの世界
Google Code Archive - Long-term storage for Google Code Project Hosting.
Glazed Lists