論文｜snmalloc: A Message Passing Allocator (ISMM 2019)
「snmalloc: A Message Passing Allocator」という論文を読んだのでその紹介です。本論文は ISMM (International Symposium on Memory Management) 2019 に採択されており、論文とソースコードは GitHub (microsoft/snmalloc) で公開されています。リポジトリ名から分かる通り、著者の多くが Microsoft Research に所属しています。 免責 読み間違えている可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue や Twitter へお願いします。 更新履歴 2019/07/08 bump pointer と free list の next entry pointer を判定する方法について追記 2019/0
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
文字列アルゴリズム - Qiita Advent Calendar 2017 - Qiita
文字列の性質やアルゴリズムなど、文字列に関する話題なら何でもOKです。 木や配列など、データ構造とアルゴリズムに関することでも全然OKです。 今年は完走目指しましょう！ 参考： 文字列アルゴリズム Advent Calendar 2016 - Qiita
SIMD / GPU Friendly Branchless Binary Search
The other day I was thinking about how you might do a binary search branchlessly. I came up with a way, and I’m pretty sure I’m not the first to come up with it, but it was fun to think about and I wanted to share my solution. All code in this post is public domain. Here it is searching a list of 8 items in 3 steps: size_t BinarySearch8 (size_t needle, const size_t haystack[8]) { size_t ret = (hay
カルマンフィルタってなに？ - Qiita
はじめに この記事について そもそもカルマンフィルタってなに？なんのためにあるの？ 何を受け取って，何を出力しているの？ どういう原理で動いているの？ 最適カルマンゲインってなに？ というところを解説していきます． わかりやすさの向上のため，わかりにくいところや気づいたことがあれば気軽にコメントしてください． 書かれていないこと この記事ではカルマンフィルタの考え方を知っていただきたいので，最適カルマンゲインの導出方法やその先のことは書かれていません． \newcommand{\Xtrue}{\mathbf{x}^{true}} \newcommand{\Xest}{\mathbf{x}^{est}} \newcommand{\Xodo}{\mathbf{x}^{odo}} \newcommand{\Xobs}{\mathbf{x}^{obs}} \newcommand{\xtrue}{x
Inside-Outsideアルゴリズムを試す - Negative/Positive Thinking
はじめに 確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いてくれているのはなさそうだったので、手計算確認用にプログラムを書いた。 Inside-Outsideアルゴリズムとは 内側・外側アルゴリズム 確率文脈自由文法の生成規則(チョムスキー標準形)の確率値をコーパスを求める際に、内側確率βと外側確率αを導入することで効率よく求められる 隠れマルコフモデルにおける前向き・後ろ向きアルゴリズムに似た感じ 内側確率 : 非終端記号Aから終端記号列w_i^jが生成される確率 外側確率 : 導出中に出現するAについて、Aが支配しているw_i^j以外の両側の終端記号列w_1^{i-1}とw_{j+1}^Nが現
ConText v3: Convolutional Neural Network and LSTM Code for Text Categorization
WARNING: This document describes an old version, v3. Here is the latest: CONTEXT v4. CONTEXT v3: Convolutional Neural Network and LSTM Code for Text Categorization Revision history May, 2016: Revised when v3.00 (corresponding to [3]) was released. In particular, Sections 4 and 5 were added for LSTM, and the description of memory usage in Section 7 was revised. September, 2015: Revised when v2.00 (
Introducing our Hybrid lda2vec Algorithm | Stitch Fix Technology – Multithreaded
The goal of lda2vec is to make volumes of text useful to humans (not machines!) while still keeping the model simple to modify. It learns the powerful word representations in word2vec while jointly constructing human-interpretable LDA document representations. We fed our hybrid lda2vec algorithm (docs, code and paper ) every Hacker News comment through 2015. The results reveal what topics and tren
/proc/cpuinfo: 全点対間最短路を高速に求める
フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。 全点対間最短路問題 全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。 // 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み // 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和 for(int k = 0; k < N; ++k) for(int i = 0; i < N; ++
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
LCA and RMQ ~簡潔もあるよ！~
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
Crash Reporting, Error Tracking, and Beyond | Backtrace.io
Breakpoint: George Neville-Neil and the Multi-Threaded ServerBreakpoint is a series of articles where we follow engineers along the journey of debugging the most challenging bugs they’ve encountered over the years. These war stories, in turn, help inform our product roadmap. Last time, [...] Backtrace has News for Unity and XBox Developers!Crash Reporting for C#, Unity, and XBox One now available
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました - EchizenBlog-Zwei
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました。 実装がとても簡単で、ハイパーパラメータも論文に推奨値が書いてあるのが良いですね。 持っておかないといけないパラメータの数は(たぶん)AdaGradと同じです。 https://github.com/echizentm/Adam AdaGradやAdamのようなオンライン学習器は実装が簡単、省メモリなど優れた特徴があり大変実用的ですし、そろそろ有益な書物も発売されるようなので、気になった方はこれを機に学んでみると良いですよ。 しかしこうなるとAdamを改良したEveという学習器を作ってみたいですね(作るとは言っていない)。
1/30 発売！「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 - iwiwiの日記
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です．会津大の渡部先生が著者で，Short Coding 本の Ozy さんと私が協力としての参加です．どうかよろしくお願いします． プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)出版社/メーカー: マイナビ発売日: 2015/01/30メディア: 単行本（ソフトカバー）この商品を含むブログ (4件) を見る 本書はアルゴリズムとデータ構造の入門書です．整列，探索，木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します．前提とするのは基礎的なプログラミング能力のみです．コード例では C++ を用いています． これだけだと，よくある本のように思われるかもしれません．しかし，本書は非常にユニークな特徴として，オン
ランダムフォレストのつくりかた（C++の実装例つき） - じじいのプログラミング
この記事は24日目の記事のつづきです。前日の関連記事「ランダムフォレストのつかいかた」もありますので、こちらもよろしくお願いします。 ランダムフォレストのつかいかた - じじいのプログラミング ランダムフォレストは、機械学習の中でも、確率統計の知識がほぼ無しで実装できる簡単なアルゴリズムで、しかも性能もなかなかのものです。TopCoder機械学習マッチのいくつかは、コードを提出してTopCoderサーバで実行するルールなので、実装しやすいランダムフォレストは有力な選択肢です。実際にランダムフォレストが１位をとったコンテストもかなりあります。 決定木の作り方さえ理解すれば、ランダムフォレストは実装できたも同然ですので、この記事では、決定木を作る部分をメインに取り上げます。 アドバイスをいただけると、とてもうれしいです。間違いのご指摘は大歓迎です。 実装は、TopCoderの他の競技者（Psy
A Fast, Minimal Memory, Consistent Hash Algorithm ご紹介(システム系論文紹介 Advent Calendar 2014）. - Qiita
(本稿は, システム系論文紹介 Advent Calendar 2014, 12/20 です http://www.adventar.org/calendars/440) 論文は arXiv から取得できます. http://arxiv.org/abs/1406.2294 Jump Consitent Hash と呼ばれる, 分散ストレージ系で有益なハッシュ関数を求めるアルゴリズムです. 現在史上最強のハッシュアルゴリズムのひとつと言えるでしょう. 無性に分散ストレージライブラリを作りたくなってきますね! 共著者の Eric Veach にも注目です. Google を救ったと言われている distinguished engineer です. (G 社のひとは彼の名前を社員名簿データベース? から探してみましょう! 社員番号 20 くらいにあるらしいですよ!) そんな彼がなんと 10 年以
大規模グラフ解析のための乱択スケッチ技法
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - google/brotli: Brotli compression format
https://jp.techcrunch.com/2015/03/13/20150312algorithmia-launches-with-more-than-800-algorithms-on-its-marketplace/
OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation