近似最近傍探索ライブラリ比較 - Qiita
はじめに kNNなどの近傍探索はpythonやnumpyだけだとデータ数に応じて時間がだいぶかかるようになります。 もちろん厳密なNNではなく近似最近傍探索(ANN search)を行うのが中心かと思います。 Pythonから使え、ANNをC等で最適化しているライブラリがあったのでいくつか試してみました。 弊社内ではFLANNやFaissが使われていました。 今回はこれらと追加で、人気のありそうなAnnoy、速そうなNMSLIBを比較してみます。 （社内kibelaでまとめたものを転載してみました） 参考記事 まとめる際のきっかけになった記事です。 ベンチマーク等はこちらが参考になります。 ann-benchmarks 著者は実はAnnoyの作者なのに、他のいいライブラリを勧めてくれています。 ブログ版 この図を見るとnmslibとfaissが特に早そう。 Approximate Near
多腕バンディット問題とA/Bテスト (Part 1) | リクルート
リクルートデータ組織のブログをはじめました。※最新情報はRecruit Data Blogをご覧ください。 Recruit Data Blogはこちら みなさん、こんにちは。ギャンブラー🤡の鹿野です。 今回は、機械学習の分野で注目を集めている多腕バンディット問題の中でも、 特にWebサイト最適化の文脈でしばしば出てくる確率的多腕バンディット問題 (stochastic multi-armed bandit problem) の基本的な枠組みとそれを解くアルゴリズムについて解説いたします (簡単のため、以下では「確率的多腕バンディット問題」を単に「多腕バンディット問題」と表記します) 。 本記事を読み終わったあとには 多腕バンディット問題の基本的な枠組みとそれを解くアルゴリズム Webサイト最適化においてどのように役に立つのか A/Bテストと多腕バンディット問題の関係 について理解ができる
ei1333's page
Wiki 競技プログラミングをするときのまとめ。まだ途中 データ構造 セグメント木(Segment-Tree) BIT(Binary-Indexed-Tree) スパーステーブル(Sparse-Table) 素集合データ構造(Union-Find) 平衡二分探索木(RBST) ウェーブレット行列(Wavelet-Matrix) トライ木(Trie) スライド区間の昇順k個の和 長方形の和集合 Skew-Heap Pairing-Heap Radix-Heap 永続配列(Persistent-Array) グラフ テンプレート グリッド上の幅優先探索(Grid-BFS) 単一始点最短路(Dijkstra) 単一始点最短路(Bellman-Ford) 単一始点最短路(SPFA) 全点対間最短路(Warshall-Floyd) 最小全域木(Prim) 最小全域木(Kruskal) 最小全域有向木
高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablog
高速ゼータ変換・高速メビウス変換が気になっていたところにタイムリーに先日のARC 100のE問題が来て（ちゃんと解けなかったので）折角なのでこの機会にマスターしようと思い競プロ有識者の皆さんのブログやツイートを漁ってみました。 はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知 高速ゼータ変換 - とどの日記 高速メビウス変換について - lan496の日記 https://pekempey.hatenablog.com/entry/2016/10/30/205852 ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary 競技プログラミングにおける畳み込み問題まとめ（FFT,アダマール変換,メビウス変換,ゼータ変換） - はまやんはまやんはまやん 高速ゼータ変換、高速メビウス変
GitHub - flame/blis: BLAS-like Library Instantiation Software Framework
BLIS is an award-winning portable software framework for instantiating high-performance BLAS-like dense linear algebra libraries. The framework was designed to isolate essential kernels of computation that, when optimized, immediately enable optimized implementations of most of its commonly used and computationally intensive operations. BLIS is written in ISO C99 and available under a new/modified
C言語でオレオレ行列積ルーチンを作るプロジェクト (その1) - Unity 勉強メモ
行列積の計算に興味をもったので、 自分でも行列積を計算するプログラムを自作してみようと思います。 最初に何の工夫もない行列積プログラムを作って、 それを順次最適化していく事で、自力でどこまで高速なルーチンを 実現できるか挑戦していきたいと思います。 初回の今回は何の工夫もない行列積プログラムです。 プログラム プログラム全体は以下のGitHubリポジトリにあります。 今回利用するプログラムは、main.cとmy_dgemm01.cです。 OpenBLASも同時に走らせて、結果を比較してルーチンが正しいことを確認しています。 コンパイル $ clang -static -O3 main.c my_dgemm01.c -I/opt/OpenBLAS/include \ -L/opt/OpenBLAS/lib -lopenblas -lpthread -lrt 実行結果 今回はコンパイラにcla
LinuxでOpenBLASとATLASを使って行列積の計算をしてみた - Unity 勉強メモ
最近BLAS(Basic Linear Algebra Subprograms)に ついて調べたので簡単な使い方等をまとめます。 はじめに BLAS (Basic Linear Algebra Subprograms) は行列やベクトルに関する基本的な演算の 仕様を定めたもので、この仕様に従った実装がいくつか存在します。 私の使っているIntelのCPUを搭載したラップトップPCで利用可能な代表的な実装としては、 Reference BLAS: リファレンス実装。遅い。 OpenBLAS: 高速なオープンソース実装。 ATLAS: 自動チューニングするオープンソース実装。 Intel MKL: Intelによる高速な実装。有料。 があるようです。今回は、OpenBLASとATLASを実際にインストールして使ってみたので、 その結果を記録します。 今回の実験環境は以下のとおりです。 OS:
カルマンフィルタってなに？ - Qiita
はじめに この記事について そもそもカルマンフィルタってなに？なんのためにあるの？ 何を受け取って，何を出力しているの？ どういう原理で動いているの？ 最適カルマンゲインってなに？ というところを解説していきます． わかりやすさの向上のため，わかりにくいところや気づいたことがあれば気軽にコメントしてください． 書かれていないこと この記事ではカルマンフィルタの考え方を知っていただきたいので，最適カルマンゲインの導出方法やその先のことは書かれていません． \newcommand{\Xtrue}{\mathbf{x}^{true}} \newcommand{\Xest}{\mathbf{x}^{est}} \newcommand{\Xodo}{\mathbf{x}^{odo}} \newcommand{\Xobs}{\mathbf{x}^{obs}} \newcommand{\xtrue}{x
色々なダイクストラ高速化
HCPC 勉強会 (2019/4/4) - Convex Hull Trick ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路をZDDとして表したら、すっきりと経路情報が扱えました。 http://d.hatena.ne.jp/nowokay/20121018#1350528607 あとは、このZDDを効率よく構築できれば、おねえさんを救えそうです。このZDDの構築には、クヌース先生の開発したSimpathアルゴリズムを使うと非常に効率よく構築できます。 前回生成したZDDを見ると、同じノードにまとまっているものがいくつかあることがわかります。特に後半になるとどんどん同じパターンになるものがまとめられていきます。 つまり、この経路問題のZDDを構築するときには、いかに同じパターンになるものをまとめるかが鍵になるということです。 Simpathでは、辺の端だけに注目して、同じパターンになっていればそれ以降のノードを使いまわすという考え方で、ノードをまとめていきます。 つ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
data-structures
Library Checker
TheAlgorithms/Python: All Algorithms implemented in Python
learning-algorithms.com
https://www.cc.u-tokyo.ac.jp/events/lectures/X01/shiryou-1.pdf
Home
https://www.cs.utexas.edu/~jianyu/presentations/strassen_sc16.pdf
ぷよぷよAIの新しい探索法
Account Suspended
ウェーブレット木の世界 - Preferred Networks Research & Development
