Optimism in the Face of Uncertainty: the UCB1 Algorithm
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. startupsThe software world is always atwitter with predictions on the next big piece of technology. And a lot of chatter focuses on what venture capitalists express interest in. As an investor, how do you pick a good company to invest in? Do you notice quirky names
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
Efficiently Computing Kendall's Tau - adereth
Typically when people talk about correlation they are referring to the Pearson’s product-moment coefficient: $$\rho_{X,Y}={E[(X-\mu_X)(Y-\mu_Y)] \over \sigma_X\sigma_Y}$$ The Pearson coefficient is 1 if the datasets have a perfectly positive linear relationship and -1 if they have a perfectly negative linear relationship. But what if our data has a clear positive relationship, but it’s not linear?
Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms
It is well known that since the sort/shuffle stage in MapReduce is costly, local aggregation is one important principle to designing efficient algorithms. This short paper represents an attempt to more clearly articulate this design principle in terms of monoids, which generalizes the use of combiners and the in-mapper combining pattern.
極大2部クリーク
グラフ $G = (V = V_1 \cup V_2, A)$ の任意の枝が$V_1$と$V_2$の頂点を結ぶ枝であるとき，$G$は2部グラフとよばれる．$G$の頂点部分集合 $H\subseteq V_1$, $K\subseteq V_2$ に対して，$H$の任意の頂点と$K$の任意の頂点の間に枝があるとき，$H$と$K$を合わせた頂点集合を2部クリークとよぶ．$K=\emptyset$, $H=V_1$ である場合，あるいはその逆である場合も2部クリークである．ある2部クリークが他の2部クリークに含まれないとき，その2部クリークを極大2部クリークとよぶ (via 宇野 毅明, 有村 博紀, 浅井 達哉, 極大2部クリークの高速列挙法とデータマイニングへの応用, 夏のLAシンポジウム, 2003年7月) (v0,v1,v2,v5,v6), (v2,v5,v6,v8), (v2,v3,v
Understanding Clojure's Persistent Vectors, pt. 2
In the previous post about Clojure’s persistent vectors (read it, if you haven’t already), we kind-of understood how insertion, updates and popping elements in a vector worked. We did not really understand how to get to the right element, and I will cover that along with how lookup works in this post. To understand how we pick the right branch, I think it’s good to give the proper name of the stru
Sorting Networks using Higher-Order Functions of JavaScript Array · ariya.io
Sorting Networks using Higher-Order Functions of JavaScript Array Oct 16, 2013 5 min read #coding #javascript #tip An implementation of a sorting algorithm usually uses one or more iterating loops in the form of for/while statement. With JavaScript and its powerful Array object, these loops can be avoided since Array’s higher-order functions are enough for iterating the array. One candidate for th
Visualizing min-heap algorithms with D3.js
I haven’t done any real work on learning Javascript and D3.js since my last attempt a couple months back. To keep at it, I thought I’d try using D3.js to visualize a simple algorithm: finding the largest couple of items in a list. This problem comes up all the time when doing search and recommendation type tasks. Every time you query a search engine, it has to find the couple best scored results i
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
Simhashing (hopefully) made simple
Why Simhash? When it comes to figuring out how similar various pieces of data are from one another (and which is the closest matching one in a large group of candidates), simhashing is one of my favourite algorithms. It's somewhat simple, brilliant in its approach, but still not obvious enough for most people (myself included) to come up with it on their own. Readers may be familiar with hashing a
Understanding Clojure's Persistent Vectors, pt. 1
★ Understanding Clojure's Persistent Vectors, pt. 1 posted 25 Sep 2013 You may or may not heard about Clojure’s persistent vectors. It is a data structure invented by Rich Hickey (influenced by Phil Bagwell’s paper on Ideal Hash Trees) for Clojure, which gives practically O(1) runtime for appends, updates, lookups and subvec. As they are persistent, every modification creates a new vector instead
The Trie Data Structure: A Neglected Gem | Toptal®
From the very first days in our lives as programmers, we’ve all dealt with data structures: Arrays, linked lists, trees, sets, stacks and queues are our everyday companions, and the experienced programmer knows when and why to use them. In this article we’ll see how an oft-neglected data structure, the trie, really shines in application domains with specific features, like word games. Word Games a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SPSC IV - A look at BQueue
Raft: The Understandable Distributed Consensus Protocol
http://raftconsensus.github.io/
Adversarial Bandits and the Exp3 Algorithm
Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time
https://izbicki.me/public/papers/icml2013-algebraic-classifiers.pdf
Shortest non intersecting path for a graph embedded in a euclidean plane (2D)
高速な逆数平方根の近似計算 - melancholic afternoon