ざっくり理解するPaxos - 小野マトペの納豆ペペロンチーノ日記
ゴールデンウィーク中、Appleがオープンソースとしてリリースした分散データベース FoundationDB のドキュメントを読んでいました。なかなか面白いデータベースだと思うのでこれについては別途書きたいですが、それはそれとしてFoundationDBでは、分散環境下でACIDトランザクションを実現するために、分散合意プロトコルとして有名なPaxosを採用しているようでした。 PaxosはGoogleのChubbyやCassandraのLight Weight Transactionなどで使われていますが、僕はいまだにPaxosがどのように動作するのかあまりよく分かっていませんでした。良い機会だと思い、FoundationDBの技術を理解するためにも連休の後半でLeslie LamportによるPaxosの論文の一つ Paxos Made Simple を読み、何となくわかった気持ちにな
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
Linux スケジューラーのコア実装とシステムコール - Qiita
はじめに これは Linux Advent Calendar 2016 の第 11 日目の記事です。Linux のタスクスケジューラーのソースコードや関連するドキュメントなどを読んで分かったことをまとめました。とても長いです・・・ はじめにスケジューラーのアーキテクチャと重要な概念を紹介し、その後はスケジューラーコアとシステムコールの実装について分かったことを延々と述べます。調べきれなかったことや分からなかったことは TODO に残したので、コメント欄とかツイッターで教えてもらえると嬉しいです。間違いの指摘も大歓迎です。 ちなみに私が読み始めたきっかけは、スケジューラーのアーキテクチャ、スケジューリングアルゴリズム、スケジューリングアルゴリズムの切り替え方、nice 値やプロセッサアフィニティがスケジューリングに及ぼす影響、プリエンプションの流れ、マルチプロセッサにおけるタスクのロードバラ
オフライン版ダウンロード | Programming Place Plus
申し訳ありません。お探しのページが見つかりません。 ページが削除されているか、将来作成される予定のページに対するリンクを選択されたかもしれません。 以下のリンクから、目的に近いページへ移動されるか、検索窓を使ってページをお探しください。 Programming Place Plus のトップページ Ｃ言語編のトップページ （旧）C++編のトップページ 新C++編のトップページ アルゴリズムとデータ構造編のトップページ 用語集のトップページ 参考書籍のトップページ
GolangのGCを追う
Go1.5とGo1.6でGoのGCのレイテンシが大きく改善された．この変更について「ちゃんと」理解するため，アルゴリズムレベルでGoのGCについて追ってみた． まずGoのGCの現状をパフォーマンス（レイテンシ）の観点からまとめる．次に具体的なアルゴリズムについて，そして最後に実際の現場でのチューニングはどうすれば良いのかについて解説する． GoのGCの今 最初にGoのGCの最近の流れ（2016年5月まで）をまとめる． Go1.4までは単純なStop The World（STW）GCが実装されていたがGo1.5からは新たなGCアルゴリズムが導入された．導入の際に設定された数値目標は大きなヒープサイズにおいてもレイテンシを10ms以下に抑えることであった．Go1.5で新たなアルゴリムが実装されGo1.6で最適化が行われた． 以下は公開されているベンチマーク．まずはGo1.5を見る． Gophe
強固なデータ・インフラストラクチャを構築するためのログの活用（デュアル書き込みがダメな理由）PART 1. | POSTD
これは Craft Conference 2015 で私が行った 講演 を編集して記事にしたものです。その時の 動画 と スライド もご覧頂けます。 あなたのデータベースは、どのようにして確実にデータをディスクに保存しているのでしょう？ ログを使っているのです。 データベースのレプリカは、どのようにして他のレプリカと同期するのでしょう？ ログを使っているのです。 Raft などの分散アルゴリズムはどのようにして合意を取っているのでしょう？ ログを使っているのです。 Apache Kafka などのシステムでは、アクティビティデータはどのように記録されるのでしょう？ ログを使っているのです。 あなたのアプリケーションのデータ・インフラストラクチャはどのように規模相応の堅牢性を保つのでしょうか？ 答えは･･･ ログは至るところにあります。私はプレーンテキストのログファイル（syslogやlog
赤黒木 - Wikipedia
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。 赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nは木の要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。 この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版(Red-black_tree
計算量はコンピュータ性能論の「入り口」にすぎない--専門家が語る、IT屋に知っておいてほしい基礎知識
情報処理における全国のエキスパートが一堂に会したリクルート主催の「春の情報処理祭」。HPC（High Performance Computing）研究分野の専門家である、京都大学の中島浩教授は、HPCの役割や速さの秘密について説明するとともに、HPCがビジネス全体にもたらす影響を語ります。コンピュータの性能を生かすために知っておくべき、HPCの基礎知識とは？（春の情報処理祭in京都より） ハイパフォーマンスコンピューティング(HPC)とは 中島浩氏：（BGM「Let It Be」を流しながら登場）さすがにビートルズの「Let It Be」ぐらいは知っているかな。皆さんが生まれるずいぶん前の歌ですけれども。 『アナ雪（アナと雪の女王）』というのがあって、あっちは「Let It Go」なんですね。こっちは「Let It Be」で、何が違うのか。英語のニュアンスはほとんど同じなんですけれども「L
徹底解剖「G1GC」実装編（β版）
本書はOpenJDK7のG1GCの実装と、それに関連する技術を解説します。 目次 スポンサーのみなさま はじめに 1.準備 2.オブジェクト管理機能 3.アロケータ 4.ヒープ構造 5.オブジェクト構造 6.HotspotVMのスレッド管理 7.スレッドの排他制御 8.GCスレッド（並列編） 9.GCスレッド（並行編） 10.並行マーキング 11.退避 12.予測とスケジューリング 13.正確なGCへの道 14.ライトバリアのコスト さらに勉強したい人へ その他参考文献 以下から（ある時点で）最新のebookをダウンロードできます。 徹底解剖「G1GC」実装編-20120915.epub 徹底解剖「G1GC」実装編-20120914.mobi 徹底解剖「G1GC」実装編-20120914.pdf 謝辞 本書はスポンサーのみなさまの金銭的支援によって執筆されました。 スポンサーのみなさま あ
アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。
Foursquare: 機械学習のアルゴリズムがサービスを磨いてくれる - ワザノバ | wazanova
http://engineering.foursquare.com/2013/12/05/how-we-built-our-model-training-engine/ Foursquareでは、どこにチェックインしてもらうか、レコメンデーション、ディスカウント、プロモーションアップデートなどあらゆる場面で機械学習の手法を応用しています。1日あたり100万件のExplore機能のクエリと600万件のチェックインがあり、それを高速で処理するとともに、その情報は機械学習のモデルに活かされています。同社のエンジニアブログで、Data AnalystのMichael Liが、機械学習のためのModel Training Engine（MTE）の構築について語っています。 多くの機械学習モデルが線形回帰かその類似のアプローチを利用していて、データをすぐに理解するという意味では利便性は高いが、ときに非
IIJ Research Laboratory
ネットワークの計測と解析 インターネットの使われ方やネットワークの挙動を把握する事は、ネットワークを運用し、その技術開発を行う ために欠かせません。しかし、観測で得られるデータ量は膨大ですがノイズが多く、また、観測できるのは極めて限られた部分でしかありません。そこで、膨大なデータから意味のある情報を抽出したり、部分的な観測からより一般的な傾向を推測する事が必要となります。... インターネット基盤技術 速くて、安全で、信頼性が高く、使いやすく、など、インターネットサービスへの要求はますます高まっています。これらの要求に応えるために、インターネットの 基盤技術も日々進歩しています。いまやインターネットはつながるだけのサービスではなく、高度で複雑な機能を備えた社会基盤となりました。IIJ技術研究所は、インターネットの基盤として実現が期待される機能を提供するために、さまざまな技術課題に取り組んで
http://live-e.naist.jp/sensor_overlay/5/doc/yoshida.pdf
2011/10/29-30 5th sensor & overlay workshop Skip List Revisited! （再訪） 吉田 幹 BBR, PIAX Inc. ～探索アルゴリズムと構造化オーバーレイ、 両者の接点について考える～ “Skip listという探索のためのアルゴリズム（+デー タ構造）を通して、構造化オーバーレイに有用な 原理を考える” 5 ここでは、考えの道筋について発表します。 答えには至っていません。 研究にはまだまだ残された領域のあることを知っ てもらうことができたら光栄です。 なぜ、Skip listか （私は）構造化オーバーレイをこう捉えている “探索アルゴリズム” の適用領域が、1台のコンピュータ の内側から広域に拡がるネットワーキングの世界に展開 した形 特に、Pastry, Tapestry (Plaxtonのアルゴリズム), Kadem
Rubyによる関数型プログラミング
古き良き小学校の時代、この行には困惑させられたものだった。 魔術的な x が、加算されたのに等しいままでいる事に。 どういうわけか、プログラミングを始めると、それに構わなくなる。 「やれやれ、それは重大な事柄じゃないし、プログラミングとは現実のビジネス行為なんだから、 数学的な純粋さについてあら探しなんて必要無い (その議論なら、大学にいる狂った髭面野郎どもにさせておけばいい)」と思っていた。 けれども、ただ知らなかっただけで、我々が間違っていて高い代償を支払っていたのは 明らかである。 Wikipedia によれば、「関数型プログラミング(functional programming, FP)とは、 計算を数学的な関数の評価とみなし、 状態や可変データを避けるプログラミングパラダイム」である。 言い換えると、関数型プログラミングは、 副作用が無く変数の値を変化させないコードを推奨する。
[機械学習] A few useful things to know about machine learning - tsubosakaの日記
タイトルの論文はCommunication of the ACM, 2012のレビュー記事 ドラフトバージョンは下のリンクから読める。 http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf 割と面白かったのでいくつか内容を紹介 概要 機械学習システムはデータから自動でタスク(スパムフィルタ、レコメンドなど)をどうやって実行するかを見出すことができます。 しかしながら機械学習システムを成功させるには教科書を読んだだけではなかなか見つけづらいお約束事とかがあって、思うようには行かないことが多い。 本文献では機械学習の研究者および実務に携わる人間が知っておくべきである事柄を12個に要約しています。 一般化が重要 機械学習のゴールは訓練データにはないデータに対しても一般化して推定ができるという点になります。単に訓練データのみ分類できればよ
![[機械学習] A few useful things to know about machine learning - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/16430eca990fc2cf00bd89af3ac4ebbcd2c20217/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124028310%2F1557332411)
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
あなたの知らないハッシュテーブルの世界