Raft Consensus Algorithm
What is Raft? Raft is a consensus algorithm that is designed to be easy to understand. It's equivalent to Paxos in fault-tolerance and performance. The difference is that it's decomposed into relatively independent subproblems, and it cleanly addresses all major pieces needed for practical systems. We hope Raft will make consensus available to a wider audience, and that this wider audience will be
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
第5章 パーサコンビネータ―小さなパーサを組み合わせて大きなパーサを作る | gihyo.jp
この章では、関数型の至宝であるコンビネータライブラリについて説明します。 コンビネータとは何か？ この章でいうコンビネータとは、ある型の部品と部品を組み合わせて、同じ型のより大きな部品を作るための関数のことです。たとえば、パーサのコンビネータライブラリは、パーサを組み合わせるための各種コンビネータを提供しており、簡単にパーサを作成できます。コンビネータライブラリは、言語内DSL（Domain Specific Language）と表現してもよいでしょう。 関数型では、パーサに加えて、データを文字列でわかりやすく表示するプリティプリンタ、SQL、XML、ハードウェア記述、そしてデリバティブ（金融商品）記述、楽譜記述など多様なコンビネータライブラリが作られ、実際に使われています。この章では、パーサのコンビネータライブラリを取り上げます。 CSVのパーサ たとえ簡潔でも、実用的でないパーサの例だ
Java で最速の乱数生成器を目指す: (3) ガンマ分布に従う乱数
TL;DR: ガンマ分布に従う乱数生成器を Java で実装し、Commons Math の実装と比較して 最大で約 16 倍 (任意の形状パラメータの乱数を生成する場合) の速度効率を達成しましたよ、というお話です。 (Header image: Mundhenk at en.wikipedia) ガンマ分布に従う乱数生成の実装方法Permalink これまで 正規分布に従う乱数生成、指数分布に従う乱数生成 をそれぞれ Java で実装してきましたが、今回はガンマ分布に従う乱数生成を Java で実装してみます。 ガンマ分布 は、形状パラメータ k>0 と スケールパラメータ θ>0 (もしくは形状パラメータ α=k と比率パラメータ β=1/θ) の 2 つのパラメータを持ち、その確率密度関数は次の式で表されます。 f(x)=xk−1e−x/θΓ(k)θk ガンマ分布の形状パラメータ
Henry Robinsonによる優しいPaxosの解説 - minghaiの日記
現在はClouderaの社員であり、ZooKeeperのコミッタでもあるHenry RobinsonによるPaxosの優しい解説。ランポートの"Paxos made simple"に比べてもとても優しいが、何となく"Paxos made simple"を読んでいることを前提としているような省略があり、両方を交互に読むことを訳者としてはお勧めする。訳者はこれだけでは一部理解できなかった。 合意プロトコル： Paxos Henry Robinson / ヘンリー・ロビンソン 今日、誰かのPaxosアルゴリズムについての記述無しに2つの分散システムについてのアーティクルを読むことは不可能だろう。 GoogleはChubbyにそれを使い、Yahooはそれに少し似ているものをZooKeeperに使っている。それはまるで究極の合意アルゴリズムだと考えられているようだ。またそれはとんでもなく理解するのが
赤黒木の本質 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
コーディング面接対策のために解きたいLeetCode 60問
自分がコーディング面接対策のために解いてよかった LeetCode の問題をコンセプトごとにまとめました。カバーするコンセプトは LinkedList Stack Heap, PriorityQueue HashMap Graph, BFS, DFS Tree, BT, BST Sort Dynamic Programming Binary search Recursion Sliding window Greedy + Backtracking です。 これらの問題が 30 分以内に実装できれば面接の準備は整ったと言っていいと思います。Easy と Medium で問題は構成されてます。進捗を管理するためにGoogle Spreadsheetを用意しました。コピペしてご自由にお使いください。 これらの問題は、LeetCode のリスト機能でも公開されています。クローンすれば自分がすでにど
最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 最近では珍しくもなくなった"Quorum"という言葉。Zookeeper, etcd, Serfといったクラスタ中でデータのレプリケーションを行ってくれるようなツールや、Cassandra, Riakといった分散データベース(NoSQL系)のようなツールにおいても、データの複製に一貫性を持たせる仕組みとしてよく聞かれます。 しかしながら、多くのスライドやWebの記事を読んでも、"Quorum"という語が意味するところは要するに「過半数ノードによる多数決」というような説明が多いように感じていました。 にも関わらず、"Quorum"と呼ばれ
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
Lockfree list
3. 挿入処理 A B C D リストの繋ぎ替え処理が一瞬で片付くように工夫して、検索処理の邪魔をしない CompareAndSwap( 以下 CAS) でポインタを差し替える 4. 挿入処理 A B C D リストの繋ぎ替え処理が一瞬で片付くように工夫して、検索処理の邪魔をしない CompareAndSwap( 以下 CAS) でポインタを差し替える CAS
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
Raftを紹介する - obfuscatism
はじめに Raft Consensus Algorithm の論文 “In Search of an Understandable Consensus Algorithm” http://ramcloud.stanford.edu/raft.pdf について簡単に紹介する。 また、論文のついでに読んでおくと理解が捗ると思われる文献（スライド、ウェブサイト）も紹介する。 というのも先日、ふと システム系論文紹介 Advent Calendar 2014 という物を私が立ち上げてしまったので、言い出しっぺの自分が先陣を切らせてもらう。 とはいえ今回の論文紹介にじっくり時間をかけて取り組めなかったため、雑な紹介になってしまう点はご了承いただきたい。 12月6日（土）に開催される 第3回 システム系論文輪読会 – connpass もあるため、輪読の発表会に興味のある方は是非参加いただきたい。 R
視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
短い暗号鍵長「ECC」でパフォーマンスとセキュリティの両立図るベリサイン
SSLサーバ証明書において標準となっているRSAに加え、「ECC（Elliptic Curve Cryptography：楕円曲線暗号）」と「DSA（Digital Signature Algorithm:デジタル署名）」という2つの暗号アルゴリズムの提供を開始したベリサイン。その背景と狙いとは？ 2つのアルゴリズムに対応したSSLサーバ証明書 オンラインショッピングサイトで何かを購入するとき、あるいは新しいWebサービスに会員登録するとき……我々は当たり前のように暗号化技術を利用している。実は、このWebの暗号化技術の裏では、さまざまな暗号アルゴリズムが活用されている。 日本ベリサインは2月14日、これら暗号化通信の基盤であるSSLサーバ証明書の対応アルゴリズムの拡張を発表した。具体的には、「ECC（Elliptic Curve Cryptography：楕円曲線暗号）」と「DSA（Di
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://vldb.org/pvldb/vol17/p3442-hao.pdf
Word2vec implementation in gensim
Bloom filter
Site Under Maintenance
正規表現入門 星の高さを求めて
