B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
分散ロックという名の過ち - Software Transactional Memo
 TL;DR; 「分散ロック」が分散システムの設計図に登場した時 だいたいその設計は間違っていて本当に必要なものはトランザクションだ 並行システムを実装する際にロックを用いるのはとても自然なことだ。 僕も普段はロックフリー系のアルゴリズムに詳しいと言われがちだが知識量でいったら実はロック系の方が多く蓄えているかも知れない。 分散システムは並行システムであることが多いので、その中にロックが登場するのはとても自然な発想である。 よく「分散」「並行」「並列」の言葉の定義がごっちゃになっているケースがあり、この記事の主題にしたいわけではないので深くは言及しないが、分散システムは環境などの要因で突如として参加者が音信不通になったり復活したりする点で並行システムと大きく異なる。 並行システムと同じノリで分散システムを設計しようとした際に陥る頻出の過ちが「分散ロック」である。そのアイデアはとても簡単で
Radix Tree - Linuxカーネルメモ
1. 概要 Tree検索を行うRadix TreeのLinuxでの実装メモ。 Radix Treeの機能はlib/radix-tree.cで提供される。実際の使用例としては、ページキャッシュのページを管理するのにRadix Treeを使っている。 2. データ構造 LinuxでのRadixツリーの構造を図1に示す。 2.1 Treeの管理データ Radix Treeの管理の大元のデータとしてstruct radix_tree_rootがある。このデータはRadix Tree関連関数でどのTreeに対して操作を行うのか指定するのに使われる。 このデータのrnodeがルートノード(Treeトップのノード)を指している。heightはTreeの高さを表しており、例えばheight=1だと、ルートノードのみの1段のTreeであることを意味する。 2.2 Treeのノード Treeの各ノードはstr
「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama
自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの
分散システムについて語らせてくれ
ATF(ARM Trusted Firmware)は、ARMv8では重要なソフトウェア。 全体を利用するのではなく、その一部を利用可能。 この資料では、BL31(EL3 Runtime Firmware)を単体で使う場合、どうすればいいのかを、Xilinx社のZynq UltraScale+ MPSoCを例に説明しています。 ATF (ARM Trusted Firmware) is an important software in ARMv8. Instead of using the whole, part of it is available. This document explains how to do when using BL31 (EL3 Runtime Firmware) alone, for example, with Xilinx's Zynq UltraScale
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
How Uber Engineering Evaluated JSON Encoding and Compression Algorithms to Put the Squeeze on Trip Data
For compression, we put three lossless and widely accepted libraries to the test: Snappy zlib Bzip2 (BZ2) Snappy aims to provide high speeds and reasonable compression. BZ2 trades speed for better compression, and zlib falls somewhere between them. Testing Our goal was to find the combination of encoding protocol and compression algorithm with the most compact result at the highest speed. We teste
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
ScalaでHListを使ったコンパイル時クイックソート 〜 (前編) - だいたいよくわからないブログ
Typelevel quicksort in Scalaで、 型レベル自然数リストのコンパイル時クイックソートなるものが紹介されているので、 おもしろそうだなと思って実装してみました。 こちらの記事ではshapelessのHList実装を参考に作られているのですが、 今回は、色々な型の値をいくつでも入れられる型安全な“HList”を実装する - Qiitaで紹介されている HListの実装をベースに作成したものを使用しました。 細かい動作の説明を入れたり、REPLの実行例を入れたりしてたら、だいぶ長くなりそうなので分割２クールにしました。 コードはこちら( ⁰⊖⁰) GitHub - matsu-chara/HListQuickSort: コンパイル時クイックソート 目次 この記事 前準備 型レベル自然数 型レベル自然数の比較 次の記事 HList HListの分割 QuickSort 前
赤黒木 - 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
アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。
計算機プログラムの構造と解釈 第二版
[ 目次, 前節, 次節, 索引 ] 2014-03-06 更新 [ 目次, 前節, 次節, 索引 ]
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）の構築について語っています。 多くの機械学習モデルが線形回帰かその類似のアプローチを利用していて、データをすぐに理解するという意味では利便性は高いが、ときに非
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
Scala Expressiveness
At its heart, Mathematica has deep support for functional programming. As a computer algebra system, the functional programming support in Mathematica is unmatched in similar products, specifically, when it comes to pattern matching and rule based programming. This post is a walk through the differences and similarities between the approaches that can be taken to solve a problem using both Scala a
Coin change
The Coin Change problem is the problem of finding the number of ways of making changes for a particular amount of cents, , using a given set of denominations . It is a general case of Integer Partition, and can be solved with dynamic programming. (The Min-Coin Change is a common variation of this problem.) Overview[edit] The problem is typically asked as: If we want to make change for cents, and w
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.golangprograms.com/
https://www.ideserve.co.in/learn/dynamic-programming-interview-questions
サービス終了のお知らせ
GitHub - pi8027/typeinfer: Type inference in OCaml
