splay tree をソラで書く！！！
(2023/02/05) 実はここに書いた方法はとにかく覚えにくいので、今度新しく書きます。考察不足でしたのでおわび申し上げます。 動機の例 自作ライブラリで Library Checker の問題[1]を解きたい link/cut tree を実装したい splay tree の面白い機能を思いついたときに実装したい 平衡二分探索木や動的木が JOI に出る(?)[2] [3] ネタバレ注意 PCK に出る(?)[4] ネタバレ注意 目標 平衡二分探索木の一種である (bottom-up の) splay tree の C++ 言語による実装例を示す splay tree を覚えやすい・一発で書きやすい方法で実装し、注意点をまとめる 注意点はできるだけ多くの点を挙げ、実装の方針が同じ splay tree が正しく動作しなかったときのチェックリストになるようにする この実装を用いて Li
t-SNEで遊ぶ - Negative/Positive Thinking
はじめに 最近よく見かける「t-SNE」という非線形次元圧縮手法を試してみた。 t-SNEとは t-Distributed Stochastic Neighbor Embedding SNEと呼ばれる次元圧縮手法の問題点を改善した手法 SNEは、「各点間の"ユークリッド距離"を、類似度に相当する"条件付き確率"に変換して低次元にマッピングする手法」のこと 各点について、高次元での確率分布と低次元での確率分布が一致するように低次元での点を探している 確率分布の違いは「カルバックライブラー情報量」で、これを損失関数にして勾配法で低次元の点を求める 低次元での分布に「自由度1のt-分布」を利用する さらに、高速化を行った「Barnes-Hut t-SNE」という手法ではO(n log n)で計算できる http://arxiv.org/abs/1301.3342 詳しい説明は、元論文や紹介記事が
SdAで遊ぶ - Negative/Positive Thinking
はじめに Deepな話で、簡単に試せそうだったStacked Denoising AutoEncoderを試しに遊んでみる。 あんまり詳しく調べていないので、お遊びレベルという感じで・・・ 注意:下記では「特徴抽出器」として利用する方法を試しています。通常は事前学習として行い、それを初期値に使い、普通にニューラルネットの学習を行うことを指すと思いますが、下記のような特徴抽出器的使い方もありみたいですね(ref.機械学習プロフェッショナルシリーズ「深層学習」pp.72-74)。 Stacked AutoEncoderとは BengioやVinsentによって提案や紹介 AutoEncoderを何層も重ねたもの 各層の学習は、一つ前の隠れ層を入力にAutoEncoderを学習し、出力部分を捨てて次の層を学習する Unsupervised layer-wise pre-training 層の最後
DNN推論用ライブラリ「Menoh」リリースについて - Preferred Networks Research & Development
Python以外も使いたくないですか？ 特にDeepLearning界隈で． Menoh開発者の岡田です．この記事ではMenohの紹介と開発に至った動機について説明します． Menohのレポジトリ： https://github.com/pfnet-research/menoh Menoh（メノウ）は学習済みのDNNモデルをONNX形式から読み込んで動作させる推論専用のライブラリです．実装はC++で書きましたが，C言語のインターフェースを持たせて，他の言語用からもその機能を呼び出しやすくしてあります．リリース時点でC++版ラッパーとC#版ラッパー，Haskell版ラッパーがあり，Ruby版ラッパーとNodeJS版ラッパー，Java（JVM）版ラッパーが開発中です．バックエンドにはIntelの開発しているMKL-DNNを採用し，GPUが無くてもIntel CPUが使える環境で高速にモデルの
AdaDeltaを試す - Negative/Positive Thinking
はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。 AdaDeltaとは M. D. Zeiler, ADADELTA: AN ADAPTIVE LEARNING RATE METHOD http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf 学習率を自動調整する方法の一つ 他の関連手法の問題点等を改良 過去すべての勾配を考慮→直近の勾配だけを考慮したいので、指数関数的に減衰するように考慮 グローバルな学習率を指定→second order methodsの特性を持つように、パラメータの変化について直近のパラメータの変化から計算し
HyperLogLogで遊ぶ - Negative/Positive Thinking
はじめに 「さぁ、お前の罪の異なり数を数えろ！」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLogとは cardinalityと呼ばれる、要素の異なり数を決定する問題 かなり省メモリで精度のよい異なり数を推定できる方法 要素をそのまま保存せず、ハッシュ値に変換したものをうまくレジスタに保存しておく ので、レジスタサイズ程度しかメモリを使わない 並列化もできて、最近のbigdataとかで注目されている また、googleが並列計算用に改善したHyperLogLogを提案してるみたい http://blog.aggregateknowledge.com/2013/01/24/hyperloglog-googles-take-on-
Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体（例えば、struct hogehoge）で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
Caffeで手軽に画像分類
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは。システム統括本部 データソリューション本部の宮崎です。 最近ディープラーニングと呼ばれる技術の話題を耳にすることが増えてきました。 この記事ではディープラーニングの手法を実装し画像認識系の用途で便利に使えるCaffeというツールの使い方を紹介します。 Caffeの概要 Caffeは、C++で実装されGPUに対応した高速なディープラーニングのライブラリです。 大規模画像認識のコンテストILSVRCで2012年にトップとなった畳込みニューラルネットワークの画像分類モデル[1]がすぐに利用できるようになっています。 Caffeは、カリフォルニア大学バークレー校のコンピュータビジョンおよび機械学習に関する研究センターであるBV
Fisher-Yates Shuffle - Faith and Brave - C++で遊ぼう
Fisher-Yates Shuffle – An Algorithm Every Developer Should Know てきとうに抜粋して書く。 以下のシャッフルアルゴリズムは間違っていて、 def incorrect_shuffle(items): for i in range(len(items)): randomIndex = random.randint(0, len(items)-1) temp = items[randomIndex] items[randomIndex] = items[i] items[i] = temp return items これには、以下の3つの問題がある： 偏る 偏る 偏る 実は1つだったけど、これは大きな問題だ。 Fisher-Yates Shuffle (Knuth Shuffleとも呼ばれる)の実装は、以下のようになる： def fi
LOUDS Trie ライブラリを書いた - WebService::Blog->new( user => ’hide_o_55’ )
C++ で LOUDS Trie を扱うライブラリhsds::Trieを書きました。 GitHub - hideo55/cpp-HSDS: Succinct Data Structure Library Collection.Includes bit-vector/wavelet-matrix/trie. LOUDS Trieとは？ Level-Order Unary Degree Sequence という木構造を表現するデータ構造を利用したTrie木です。 Space-efficient Static Trees and Graphs hsds::Trie の機能 現在は以下の機能をサポートしています。 木のノードレベルでの探索(traverse) 完全一致検索(exactMatchSearch) 共通接頭辞検索(commonPrefixSearch) クエリ文字列を接頭辞に含む全てのキ
機械学習ライブラリ SHOGUN入門 – Rest Term
The machine learning toolbox’s focus is on large scale kernel methods and especially on Support Vector Machines (SVM) * The SHOGUN Machine Learning Toolbox サイトのデザインどうにかしたらいいのにとか将軍ってなんだよとかいろいろあるかと思いますけども、プロダクトとしては素晴らしいという噂を聞くので今回このSHOGUNという機械学習ライブラリを試してみました。目的は一般物体認識における分類タスクでMultiple Kernel Learning(MKL)やLatent SVMの実装を試すことなのですが、まずはインストール方法と簡単な使い方を調べるところから始めます。 また、この記事の内容はQiitaにも投稿しています。 * 機械学習ライブラ
LIBLINEAR -- A Library for Large Linear Classification
Machine Learning Group at National Taiwan University Contributors Version 2.49 released on May 25, 2025. We continue to improve the Python interface. Version 2.43 released on February 25, 2021. Installing the Python interface through PyPI is supported > pip install -U liblinear-official The python directory is re-organized so >>> from liblinear.liblinearutil import * instead of >>> from liblinearu
高速フーリエ変換(FFT)をおじさんもC++で作ってみたよ - nursの日記
マンガでわかるフーリエ解析 作者:渋谷道雄,晴瀬ひろきオーム社Amazon やあ子どもたち。数値配列を日常的に扱っている俺達プログラマーにとって、フーリエ変換がいかに簡単かというイメージを忘れないように以前日記を書きました。その中で、DFT（離散フーリエ変換）計算の実践実装例も見ました。 そして今日はその高速版、FastFourierTransform（高速フーリエ変換）（以下、FFT）の実装及び原理を紹介します。（実際に動くC++のプログラムソースコードは本記事の一番最後の方にあります。） FFTは20世紀の10大アルゴリズムの中にも数えられる、とても有名なアルゴリズムでもあります。とはいえその歴史は古く、FFTやDFTの本当の起源というところまで行くと、あの大数学者ガウス（1777年生まれ）が既に気付いていた？などという噂もあるらしく、それ自体をテーマにした研究論文が出版されたりしてい
マルチキークイックソートとstd::sortの比較 - sileのブログ
以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。 使用データ Wikipediaの記事タイトル約500万行を使用。 データ作成方法などはここを参照。 $ wc -l wiki.title.500 5340378 wiki.title.500 $ ls -lh wiki.title.500 -rw-r--r-- 1 user user 103M 2010-10-27 02:14 wiki.title.500 これを次のRubyスクリプトでシャッフルする。 # ファイル名: shuffle.rb lines=open(ARGV[0]).read.split("\n") 2.times{|k| lines.size.times{|i| j = rand(lines.size) tmp = lines[i] lin
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CRF++: Yet Another CRF toolkit
graph/example at master · boost-cmake/graph · GitHub
Index of /~sk1/algo
http://www.larsson.dogma.net/qsufsort.c
GitHub - watashi/AlgoLib: Library for Algorithm Contest