Vertical Finger Trees
A finger tree is an elegant persistent data structure which supports O(1) insertion and O(log(n)) query operations for sequence-like data structures. By using the structure with different annotations, one can represent random access, priority queues, interval trees, and key/value stores in finger trees. While finger trees aren't always the fastest way to build any of these structures, their versat
双方向ダイクストラ - tshitaの備忘録Ⅱ
・（追記）2015年11月3日：Mi_Sawaさんとtmaeharaさんのソースコードへのリンクとtmaeharaさんのプログラムとの比較 [概要] 双方向ダイクストラを初めて実装したので備忘録としてまとめておきます． 時間がないのでざっくりとしか書いてません． 双方向ダイクストラ法を知らなかったのでMi_Sawaさんに教えていただきました．有り難うございます． 無向グラフ上で始点sと終点tが与えられたときのsからtへの最短路を求める問題を考えます．この問題は2頂点対最短経路問題と呼ばれています．グラフの上で最短経路を求める問題は一般的に最短経路問題と呼ばれておりいろいろな種類があります． 最短経路問題 - Wikipedia 特にsから各頂点への最短経路を求める問題は単一始点最短経路問題と呼ばれており，その問題を解く有名なアルゴリズムにダイクストラ法（ダイクストラ法 - Wikipedi
Directed graph traversal, orderings and applications to data-flow analysis - Eli Bendersky's website
When traversing trees with DFS, orderings are easy to define: we have pre-order, which visits a node before recursing into its children; in-order, which visits a node in-between recursing into its children; post-order, which visits a node after recursing into its children. However, for directed graphs, these orderings are not as natural and slightly different definitions are used. In this article
Ant colony optimization in Scala
In this post, we’ll walk through a novel method of solving a famous mathematical problem from computer science, and in the process, I’ll describe how it can be implemented effectively in Scala. All the code in this post is available on GitHub. Framing the problem Let’s consider a map of locations, identified by their numerical index for convenience. A salesperson wants to visit each location exact
Introducing Brotli: a new compression algorithm for the internet
The latest news from Google on open source releases, major projects, events, and student outreach programs. At Google, we think that internet users’ time is valuable, and that they shouldn’t have to wait long for a web page to load. Because fast is better than slow, two years ago we published the Zopfli compression algorithm. This received such positive feedback in the industry that it has been in
Of Levenshtein automata implementations
Thanks to Ken Hironaka for kindly taking a lot of time to read and fix countless errors in this blog post! Back to Tokyo It’s been such a long time since my last post, and so much have happened. I moved to Tokyo in November 2014 and started working for Indeed Japan. I’m still kind of foreign to the dev community in Japan, so if you are also in Tokyo and you have some good tips about tech/startup e
Introduction to Monte Carlo Tree Search - Jeff Bradberry
The subject of game AI generally begins with so-called perfect information games. These are turn-based games where the players have no information hidden from each other and there is no element of chance in the game mechanics (such as by rolling dice or drawing cards from a shuffled deck). Tic Tac Toe, Connect 4, Checkers, Reversi, Chess, and Go are all games of this type. Because everything in th
The Welch-Berlekamp Algorithm for Correcting Errors in Data
This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email. In this post we’ll implement Reed-Solomon error-correcting codes and use them to play with codes. In our last post we defined Reed-Solomon codes rigorously, but in this post we’ll focus on intuition and code. As usual the code and data used in this post is available
FP Graph Algorithms
Manipulating graphs has traditionally been seen as a place where imperative programming reigns supreme. Tikhon Jelvis begs to differ, and shows a trick where graph traversal can be expressed by a form of pattern matching. After explaining the approach he simulates how it works on a sample graph. Summary Traditionally graph algorithms are seen as one of the things that are really hard in functional
Paxos Made Moderately Complex
Paxos algorithms are a family of consensus algorithms (or protocols) that are used in distributed systems to achieve consensus in the presence of crash failures. These protocols are infamously difficult to understand, mainly due to the various states that have to be maintained on servers that have varying roles in the execution of the protocol. Paxos consensus protocols are generally used to imple
The Ziggurat Algorithm for Random Gaussian Sampling
The Ziggurat Algorithm for Random Gaussian Sampling ZigguratGaussian.cs (C# source code) The Ziggurat Algorithm is a method for efficient random sampling from a probability distribution such as the Gaussian distribution. The probability distribution function (pdf) for the Gaussian distribution is given by: $$ y = \frac{1}{ \sqrt{(2 \pi \sigma^2}} \, e^{-\frac{(x-\mu^2)}{2 \sigma^2}} $$ Where μ is
近似アルゴリズムデザイン - 共立出版
本書は、近似アルゴリズムデザインの技法とアイデアを系統的かつ明快に解説している。 第1部では、単純な問題を例にとり、これらの技法とアイデアを具体的にわかりやすく解説している。第2部では、これらの技法とアイデアを実際のケースで生じるより高度な問題に適用する際の工夫を具体的に解説している。 本書において系統的な解説を可能にしているのが、線形計画法と整数計画法である。欧米の大学では、本当に実用的なアルゴリズムの研究開発には、これらの分野が極めて重要であることが認識されてきている。したがって、情報科学系でもこれらを講義で取り上げる大学が増加してきていて、本書もそれに後押しされて、その重要性を増してきている。すなわち、これからのアルゴリズム教育には、線形計画法と整数計画法の概念の理解とそれを応用する能力の育成が必要不可欠となると思われるが、本書はそれらも自然に身につくように記述されている。 (Dav
Cache optimizing a priority queue
I must begin with saying that if you found this because you have a performance problem, you should almost certainly look elsewhere. It is highly unlikely that your performance problem is caused by your priority queue. If, however, you are curious, or you have done careful profiling and found out that the cache characteristics of your priority queue are causing your performance problem, and you can
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Memory Layouts for Binary Search
ページ移転のお知らせ
Huffman revisited part 5 : combining multi-streams with multi-symbols
GitHub - csvoss/retroactive: Fun with time travel: Implementing retroactive data structures in Python
CHICKEN internals: data representation | More magic
[PDF] The Design of Approximation Algorithms
:: dibaiee.ir ::
