Glidesort - FOSDEM 2023
Glide. Vultur gryphus, Hugo Pédel CC BY-SA 3.0 Glidesort Orson Peters Research done at CWI Database Architectures group Efficient In-Memory Adaptive Stable Sorting on Modern Hardware What is glidesort? ● General purpose stable comparison sort. ● A hybrid of mergesort, quicksort and block insertion sort. ● Robustly adaptive to pre-sorted and low-cardinality inputs. ● Reference implementation in (unsa
Levelsモナドを使った幅優先探索の仕組み
Haskellは関数型プログラミング言語と呼ばれますが、関数だけでなく型も重要な役割を担っています。アルゴリズムを考える時、手続きの最適化だけでなく、正しいデータ型を選択することがシンプルなアルゴリズムを導き、実装をコンパクトにできるというのはよくある話です。今回は非常に単純な型でありながら幅優先探索というアルゴリズムのエッセンスを詰め込んだ Levelsというデータ型 について紹介したいと思います。 ピタゴラス数を列挙する ピタゴラス数とはピタゴラスの定理における関係式 a^2 + b^2 = c^2 を満たす自然数の三つ組です。 Haskellのリストは遅延評価なので 全ての自然数の三つ組を列挙する 列挙した自然数の中から関係式を満たすものだけ抽出する という手順でピタゴラス数を列挙することを考えてみましょう。 実際この方法は有限な探索範囲ではうまく機能します。 pyth :: [(I
クラスタリングの不可能性定理について - Qiita
背景 機械学習の手法のひとつであるクラスタリングは、データの特徴により分類を行います。クラスタリングには様々な手法がありますが、その多くは距離関数を利用して有限個の点を分類します。 昨今、IT業界で機械学習がブームになっていますが、クラスタリング手法の能力について、理論的な視点からあまり言及されていないのではないかと思います(あくまでも、IT業界内の話)。利用している手法で「できること」だけでなく、「できないこと」をハッキリさせるのも重要なことだと思います。実際、Kleinbergさんの論文1などで、クラスタリングの能力・定式化について研究されています。 Kleinbergさんの論文1では、クラスタリングの特徴の中からスケール不変性、豊富性、一貫性を取り上げ、3種すべてを満たすクラスタリングは存在しない、という定理が示されています。これをクラスタリングの不可能性定理(Impossibili
how-a-kalman-filter-works-in-pictures
I have to tell you about the Kalman filter, because what it does is pretty damn amazing. Surprisingly few software engineers and scientists seem to know about it, and that makes me sad because it is such a general and powerful tool for combining information in the presence of uncertainty. At times its ability to extract accurate information seems almost magical— and if it sounds like I’m talking t
Okasaki's Lazy Queues - LiquidHaskell
The “Hello World!” example for fancy type systems is probably the sized vector or list append function (“The output has size equal to the sum of the inputs!”). One the one hand, it is perfect: simple enough to explain without pages of code, yet complex enough to show off whats cool about dependency. On the other hand, like the sweater I’m sporting right now, it’s a bit well-worn and worse, was nev
【随時追記予定】読書メモ：関数プログラミング 珠玉のアルゴリズムデザイン - claustrophobia
「関数プログラミング 珠玉のアルゴリズムデザイン」を買いました。 「関数プログラミング 珠玉のアルゴリズムデザイン」買った。二章まで読んだけど読み応えあってよい感じ。 pic.twitter.com/tGSm0ceW0E— xenophobia (@xenophobia__) 2014, 11月 14 読みながらツイートしてたら 珠玉のアルゴリズムデザイン、おれが買う頃には @xenophobia__ さんがわかりにくいと思ったところを記事にまとめてくれてて、それを見ればスムーズに読み進められるんだろうなー！— とむらっきー (@masquerade0324) 2014, 11月 14 というフリを受けたので、理解を深めるためにもメモを書くことにします。 随時更新していきますが、とりあえず3章まで。 （11/19追記）サポートサイトがあるようです。なんとこの記事にリンクを貼っていただきまし
エラー率わずか0.00000625％、驚異のインド式昼食配達システム「ダッバーワーラー」
日本の物流システムのものすごさはよく知られたところ。徹底的なコンピューター化による管理と、そして日本の道路・通信インフラの優秀さによって高速かつ精密な輸送を可能にしているわけですが、これにまさるとも劣らないシステムがインドにもありました。社会的なインフラがまだまだ未整備なのにも関わらず、伝票もPOS端末も携帯電話も一切なんにも使わずに毎日20万食の昼食を時間通りに届ける「ダッバワーラー」という驚異のシステムが存在しているのです。一体どんな人達なのでしょうか。 目次 ダッバーワーラーとは ミスは1600万回に1回、驚異の低エラー率 超複雑なネットワークを人力で運営するダッバーワーラー達 なぜダッバーワーラーは超低料金で超優良サービスを提供できるのか？ ダッバーワーラーと組織の社会貢献 ダッバーワーラーとは インドの人達には、3食きちんと調理した温かい物を食べる、という食文化があります。これは
翻訳：Paxos Made Simple - minghaiの日記
Paxos made simple (PDF) Leslie Lamport 01 Nov 2001 簡単にしたPaxos レスリー・ランポート 2001年11月1日 注：誤訳、誤字、その他ご指摘歓迎。翻訳者は誤訳に関して一切の責任を取りません:-) Abstract The Paxos algorithm, when presented in plain English, is very simple. 要約 Paxosアルゴリズムは、普通の言葉で語ればとても簡単だ。 1 Introduction The Paxos algorithm for implementing a fault-tolerant distributed system has been regarded as difficult to understand, perhaps because the original
Merkle tree - Wikipedia
An example of a binary hash tree. Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation of hashes 0-0 and 0-1. In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" node is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner nod
Raft - The Understandable Distributed Protocol
Sustainable Security Requirements with the ASVS Josh Grossman provides a brief overview of what the ASVS is, but takes a closer look at balancing trade-offs and prioritizing different security requirements. Josh shares how to make the process repeatable and how to implement it as part of your own organization's requirements process.
Consistent Hashingをためす - Tomorrow is always fresh with no mistake in it.＠備忘録
最近ネットをみていたら、「Consistent Hasing を Ruby で試す」にて、rubyを使ってConsistent Hashingをためしていた。そのプログラムは、もともと「Consistent Hashing を試す」にあるperlのプログラムをrubyにしたそうで、私もJavaで作成してみました。 Perl版、Ruby版と同じく、まずは引数で指定されたノード名（複数）のハッシュ値をmd5で求めます。次に'A'〜'Z'のハッシュ値をmd5で求め、それと等しいか、それより大きいがもっとも近いハッシュ値をもつノードを処理させるノードに決定します。 'A'〜'Z'の値は、クライアントが利用するサーバを決定するための情報の例として使っています。実際のシステムでは、ユーザ毎に利用するサーバを振り分けるなら、ログインIDなどが該当すると思います。 public class Main {
Zab vs. Paxos - Apache ZooKeeper - Apache Software Foundation
Is Zab just a special implementation of Paxos?No, Zab is a different protocol than Paxos, although it shares with it some key aspects, as for example: A leader proposes values to the followersLeaders wait for acknowledgements from a quorum of followers before considering a proposal committed (learned)Proposals include epoch numbers, which are similar to ballot numbers in PaxosThe main conceptual d
Cache oblivious array operations
I must confess that secretly the article I wrote last time (in which I introduced ndarrays) was just a pretext to introduce the stuff that I am going to write about today: which is the cwise library for array operations in JavaScript. Array operations Briefly, array operations are component-wise operations that can be applied across multiple multidimensional arrays simultaneously. Array operation
ビザンチン将軍問題 - Wikipedia
ビザンチン将軍問題（ビザンチンしょうぐんもんだい、英語: Byzantine Generals Problem）とは、相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である[1]。フォールトトレラントシステムでの多数決の妥当性や分散コンピューティングの処理の妥当性に関わる問題と言え、二人の将軍問題を一般化したものと言える。 ビザンチン将軍問題に帰結される故障や障害をビザンチン故障（Byzantine Failure、あるいはビザンチン障害）と呼ぶ。また、ビザンチン将軍問題が発生しても全体として正しく動作するシステムをビザンチン・フォールトトレラント性（Byzantine Fault Tolerance）があるという。 問題[編集] ビザンチン将軍問題は、東ロ
http://dspace.info.gscc.osaka-cu.ac.jp/~fujita/RESEARCH/KANSAIP2P/chubby.txt
The Chubby lock service for loosely-coupled distributed systems ○ 背景 ・Chubby の概要 - 高信頼ストレージから構成される疎結合型分散システム - 荒い粒度 (coarse-grained) のロッキングを提供する - 設計上の課題はパフォーマンスを阻害する有効性と信頼度 ・ロック・サービスの目的 → クライアントのアクティビティを同期し環境に関わる情報を一致させる ・Chubby の目標 - 多くのクライアントに信頼性を有効性を提供する - 分かり易いセマンティックスに基づく - スループットと記憶容量は２次的な目標 ・Chubby のクライアントインターフェース → シンプルなファイルシステム・インタフェースと似ている - ファイル全体に対するリード・ライト - アドバイザリ・ロック - イベント通知（ファイル更
Hilbert curve - Wikipedia
First six iterations of the Hilbert curve The Hilbert curve (also known as the Hilbert space-filling curve) is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891,[1] as a variant of the space-filling Peano curves discovered by Giuseppe Peano in 1890.[2] Because it is space-filling, its Hausdorff dimension is 2 (precisely, its image is the uni
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set. The base data structure of a Bloom filter is a Bit Vector. Here's a small one we'll use to
手続き脳によるHaskell -- Sorting Algorithms
このページは手続き脳から脱却でいない筆者が、Haskell による各種 ソートティングアルゴリズムを実装してみた結果を紹介するページです。ソート はアルゴリズムの基本ですから、これで Haskell を攻略しようというわけ です。 ところで、Haskell に関するWebページを巡回していると、高階関数やモナド などを複雑に使ったアクロバチックでアブノーマルなコードに出会うことが しばしばあります。書いている超頭の良い人達は自らの変態さ加減が披露出来て 快感なのかもしれませんが、頭の悪い私にはそんなコードは理解できません... orz。 そこで私のページでは次のスローガンでプログラミングを行います 普通にやれ、普通に！ そんなわけで「モナドを理解したい」とか常人には不可能な無理難題を期待 している人は他のページを当たってください。筆者自身が分かってないので解説 できません。ごめんなさい。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
VMware Tanzu Blog | VMware Tanzu
GitHub - agl/critbit: Critbit trees in C