はてなブックマーク

はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker's Alias Methodというアルゴリズムがある。この手法は一度$O(N)$の手間で配列を作ってしまえば、後は$O(1)$でインデックスを選ぶことができる。 例えば重みとして[3, 6, 9, 1, 2, 3, 7, 7, 4, 8]という10個の要素を

char str1[8] = "hoge "; char str2[8] = "fuga "; char *str3 = strcat(str1,str2); C言語を知っている人が見れば「あ、これはC言語をよく知らない人が書いたな」ということがわかるかと思います。これ、もちろん駄目なコードなわけですけど、ちゃんとプログラムを習わずに自己流でプログラマになり、コードレビューなどがない会社に就職してしまったりすると、このままになってしまうかもしれません。私も友人に指摘されるまでしばらくこれに似たコードを書いていた経験があり、決して他人事ではありません。 そもそも、C言語における文字列リテラルって、結構いろいろ面倒だったりします。というわけで、この機会に文字列リテラルの扱いについてあれこれ書いてみます。 例1: グローバルな宣言 文字列の宣言には、以下の二通りの方法があります。

はじめに 離散ウェーブレット変換による多重解像度解析について興味があったのだが、教科書や解説を読んでも説明が一般的、抽象的過ぎてよくわからない。個人的に躓いたのは スケーリング関数とウェーブレット関数の二種類が出て来るのはなぜだ？ 結局、基底を張ってるのはどっちだ？ 出て来るのはほとんどウェーブレット関数なのに、最後に一個だけスケーリング関数が残るのはなぜだ？ といった点。このあたり、わかってからテキストを見直すとすごく簡単なのだが、わかるまでにちょっとギャップがある。なので本稿では、多重解像度解析の一番簡単な例である一次元のハールウェーブレットによる変換を例に、そのあたりを大づかみに理解することを目的とする1。 簡単な例 以下、簡単のため1次元の離散空間を考える。$N=2^m$個の格子点があり、それぞれに数値が与えられているとしよう。例えば、$m=3$、すなわち8点のデータとして、こんな

はじめに 劇場版malIoc、もう見ましたか？ラストで無人在来チャンクがヒープに突っ込んでくシーンなんか鳥肌ものそろそろ怒られるのでやめよう これまでmallocの様々な動作を確認してきました。 mallocの動作を追いかける(mmap編) mallocの動作を追いかける(prev_size編) mallocの動作を追いかける(main_arenaとsbrk編) mallocの動作を追いかける(fastbins編) mallocの動作を追いかける(マルチスレッド編) ← イマココ mallocの動作を追いかける(環境変数編) これだけでもかなりややこしいですね。っていうかソース読むよりgdb経由で解析したほうがわかりやすいってどういうことよ？ さて、これまではシングルスレッドでの動作のみを考えてきました。たいがいのものは並列だの分散だのになった瞬間に考えなければいけないことが滅茶苦茶増えて

はじめに 大量のパワーポイント資産がある時、「あれ？この話どこでしたっけ？」とか「あの話をしたスライドどれだっけ？」と悩むことが多い。そんな時のためにpptxファイル内をgrepするRubyスクリプトを書いた。これはこれで便利だったのだが、手抜き処理が多かったために動作が遅く、大量のpptxファイルの検索には向かなかった。Rubyスクリプトのまま高速化することもできるのだろうが、勉強を兼ねて別の言語で書き直したい。というわけでD言語版を作った。 ファイルは https://github.com/kaityo256/pptxgrep においてある。 自分で言うのもなんだけどわりと便利なので、pptx資産が大量にある人は是非使って欲しい。 使い方 とりあえずコンパイルして、aliasなりPATHの通ったところに置くなりする。

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? TL;DL 機械学習において前処理って大事ですね。 はじめに 「そうだ、機械学習をしよう」と思って、とりあえず始めるのはMNISTを使った手書き数字認識だと思う。例えばChainerのサンプルとか動かして、ロスが減って「なんか学習できてるっぽいなぁ」と思うところまで行ったとする。次に「ちゃんと学習できてるか、学習させたモデルに自分の手書き文字を認識させてみよう」と思ってやってみると全然認識できなかったりして驚くわけですね。 この話を機械学習に詳しい人にしたら「ちゃんと前処理した？」と言われて、「いやしてないけど、こんな簡単な認識、前処理

はじめに ncursesを使って、こんな感じのブロック崩しゲームを作ります。 ソースは以下に置いておきます 以下のStepは、それぞれ上記リポジトリのディレクトリに対応しています。 ncursesとは ncursesとは、キー入力や画面表示など、端末のテキストユーザインタフェース(TUI)を作るのに便利なライブラリです。マウスや画面表示などはわりと端末ごとにいろいろ違っていて面倒なのですが、それを吸収してくれます。このライブラリを使うと、キーの入力、マウスイベント処理、画面表示などが簡単にできるようになります。 直接このライブラリを使って何かを組む人は少ないと思いますが、何かアプリケーション(例えばVim)をソースからビルドするときに要求されるので、ご存知の方は多いでしょう。 なんか娘を寝かしつけていて、ようやく寝たと思ったら僕が寝そけてしまったので1、このライブラリの紹介がてら簡単なゲー

はじめに あるクラスから派生したクラスで、基底クラスのメソッドをオーバーライドしたとする。この時、派生クラスがコンパイル時にわかっているときに、コンパイラはそれを認識して最適化できるか試してみた。 使うコンパイラは以下の通り。 g++ (Homebrew GCC 7.3.0_1) 7.3.0 clang++ Apple LLVM version 9.1.0 (clang-902.0.39.2) icpc (ICC) 18.0.1 20171018 ただし、インテルコンパイラについては最後でちょっと触れるだけにする。 ケース1: 静的な宣言 こんなコードを考える。

はじめに 履歴書、書いてますか？＞挨拶 僕もいま任期付きなもんで履歴書を書いては送る日々なわけですが、履歴書ってなんであんなに書きづらいんでしょうね？ で、これまでは履歴書をLaTeXで書いて管理してたのですが、ちょっとスタイルを修正するのもすごく面倒だし、そもそもデータとスタイルの分離がよろしくないのがストレスでした。そんな時にこの【退職】履歴書をGit管理したかってん【しました】という記事を見て、僕も履歴書をもう少し扱いやすいフォーマットから作るスクリプトを書きました。ソースはGitHubに置いてあります。 (2020年7月19日追記) 2020年7月17日付で、日本規格協会グループは、JIS Z 8303『帳票の設計基準』に掲載されていた「履歴書」の様式例を削除しました。2020年7月19日現在は「お知らせ」に記載されていますが、パーマネントリンクが無いようなので、そのうち消えるかも

はじめに Vimの非同期文法チェックエンジン、ALE (Asynchronous Lint Engine)に、プロジェクト固有の情報を教えたいことがある。典型的なのがC/C++のヘッダのインクルードパスで、makefileで-Iで場所を教えていたりすると、ALEから呼ばれたgccやclangがそのパスを探せずにエラーを報告してしまう。これを解決するには以下のようにすれば良い。 .vimrcを修正して、カレントディレクトリに.vimrc.localがあったら読むようにする ALEに追加情報が必要な場合はそこに.vimrc.localを作って、その中に情報を書く 例えばC/C++のインクルードパスを教えるにはg:ale_cpp_clang_optionsとg:ale_cpp_gcc_optionsに"-std=c++14 -Wall -Ipath/to/header"を指定する 状況 あるプロ

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

はじめに Twitterで、文字化けネタを幾つかつぶやきました。 サッちゃんはね サチコっていうんだ ほんとはね だけど ちっちゃいから 自分のこと SJISで 保存するんだよ おかしいな 繧ｵ繝ちゃん — ロボ太 (@kaityo256) 2017年10月10日 「私 魔女のキキです。こっちはSJISの繧ｸ繧ｸ」 — ロボ太 (@kaityo256) 2018年1月6日 UTF-8「もしかして…」 SJIS「私達…」 「「入れ替わ縺縺ｦ繧九≦縲懶ｼ†」」 — ロボ太 (@kaityo256) 2018年2月13日 どれもUTF-8で保存された文字をSJISとして解釈したための文字化けを表現したものですが、パッと見で「糸偏の漢字が多いな」ということがわかるかと思います。なぜそうなるかを簡単に説明してみようと思います。 なお、文字コードはいろいろ面倒なので、ここではざっくりとしたことしか言い

はじめに Twitterで見かけた「一見平等に見えるルールが不平等を生む」という話題についてのちょっとした覚書です。 ゲームのルール こんな「ゲーム」を考えます。 最初、6人がリンゴを一つずつ持っている 6人はそれぞれ1〜6までの番号が振られている サイコロを二回振り、最初に出た目の人が、次に出た目の人にリンゴを一つあげる。ただし、最初の人がリンゴを持っていない場合はそのまま 以上を繰り返す この試行を繰り返した時、リンゴを持っている数の分布はどうなるでしょうか？ ウェブで定期的に話題になるためご存知の方も多いでしょうが、十分時間がたつと多くの人がリンゴを一つも持たず、リンゴが一部の人に偏る「富の独占」がおきます。この「ゲーム」は、 公平なルールであっても富の独占は起きる このゲームにおいて富を独占する人はたまたま運が良かっただけであり、特に他の人よりも優れていたわけではない といった文脈

#はじめに 多くの人にとって、初めてモンテカルロ法に触れるのは「ダーツを投げて円周率を求めるプログラム」だと思う。プログラムは簡単だけれど、そこそこの桁数を得るのに相当な試行回数が必要になるので、他のもっと収束が早い公式と比較したりして「モンテカルロ法は遅い」という印象を持ってしまう。 しかし、現在一般に「モンテカルロ法」というと、ほぼ「マルコフ連鎖モンテカルロ法(Markov-Chain Monte Carlo, MCMC)を指す。マルコフ連鎖モンテカルロ法は他の高次元数値積分法に比べて収束が早く、かつ他の近似手法と違って得られる答えにバイアスが無いという特徴があり、極めて強力な手法である。 さて、マルコフ連鎖モンテカルロ法を習得するにあたって、初学者1の鬼門は詳細釣り合い条件(Detailed Balance)だと思う。詳細釣り合い条件の次に、メトロポリス法や熱浴法などで遷移確率を決め

はじめに これは多分MPI Advent Calendar 2017の２日目の記事です。 MPIというのはMessage Passing Interfaceの略で、異なるプロセス間でデータをやりとりするものなんだけれども、ライブラリという形で提供されている。これはつまり、もともとプロセス間通信という概念を含まない言語に、なんか関数を呼ぶと通信できるようにする追加機能という感じで、そのために特にスコープまわりが居心地が悪いものになっている。 筆者はそんな「MPIの気持ち悪さ」をたびたび口にしているんだけれど、いまのところ誰からも共感されたことがない。 本稿はそんな、いまのところ僕だけが気持ち悪いと思っているMPIのスコープ関連の話をしてみる。 サンプル とりあえずこんなコードを見てほしい。 #include <cstdio> #include <mpi.h> int main(int arg

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

はじめに 「C++アドベントカレンダーが埋まらない〜」という悲鳴が聞こえてきたので、小ネタを投下します。 未定義動作 C++には「未定義動作」というものが存在します。いや、もちろん他の言語にもあるんですけど、C++の未定義動作はちょっと雰囲気が違っています。つまり、世の中には「C++未定義動作を愛する人」というのがいるんですね。愛するというか、未定義動作の匂いを嗅ぎつけるとどこからともなくやってきて「ハナカラアクマ！」と叫びます。「ハナカラアクマ！」というのが何か詳しくは知りませんが、未定義動作を浄化するためのおまじないのようなものだと思えば間違いないと思います。 そんなわけで、うっかり未定義動作を踏んだコードを書いて公開しようものなら、「シープラプラシヨウケイサツ」という秘密結社のメンバーがやってきて、コメント欄で「ハナカラアクマ！」と叫ばれてしまいます。 で、世の中様々な未定義動作の例

Chainer Advent Calendar 2017 4日目の記事です。 はじめに 最近、猫も杓子も機械学習って感じですね。「私も機械学習やってみたい！でもどうやっていいかわからない」って人、多いと思います。で、TensorFlowでもChainerでもセットアップして、MNISTとかの学習やってみて「あーなんか動いてるな」となった後、どうして良いかわからなくなる人、多いんじゃないでしょうか。画像の分類とかやってみたくても、スクレイピングとかやらなきゃいけないし、タグ付けとかどうすればいいのかわからないし、そもそもたくさんの画像をどうやってニューラルネットに食わせればいいのかわからない・・・。機械学習ビギナー、あるあるですね。 というわけで、本稿では機械学習ビギナー(=僕)が、とりあえず簡単に何か機械学習を試すために必要な最低限のプログラム群を作ってみたりして、初心者の敷居を下げられた

はじめに mall0c動画見てますか？＞挨拶 Twitterで「malloc動画」で検索かけると、眠れない夜に見ると良いとか、健康に良いとかいろいろ出てきて、健康に良い上にmallocのこともわかるなんて、もう見ない理由はないですね。 というわけで、今回はmallocにおけるmain_arenaとsbrkの振る舞いを追います。 mallocの動作を追いかける(mmap編) mallocの動作を追いかける(prev_size編) mallocの動作を追いかける(main_arenaとsbrk編) ← イマココ mallocの動作を追いかける(fastbins編) mallocの動作を追いかける(マルチスレッド編) mallocの動作を追いかける(環境変数編) main_arenaとsbrkの動作を追いかける gdbで追いかける mallocは、メモリをアリーナ(arena)という単位で管理し

はじめに malloc動画見てますか？＞挨拶 前回は比較的振る舞いがシンプルな、mallocが内部でmmapを呼ぶケースについて調べたが、今回はmalloc_chunk構造体と実際に使われるメモリ配置がちっとも対応していないことを見てみる。 mallocの動作を追いかける(mmap編) mallocの動作を追いかける(prev_size編) ← イマココ mallocの動作を追いかける(main_arenaとsbrk編) mallocの動作を追いかける(fastbins編) mallocの動作を追いかける(マルチスレッド編) mallocの動作を追いかける(環境変数編) chunkについて 繰り返しになるが、mallocはメモリをチャンク(chunk)という単位で管理する。これは「ヘッダ＋ユーザが使える領域」なのだが、メモリを効率利用するために、チャンクのヘッダが他の使用中メモリを指してい

はじめに malloc動画見てますか？＞挨拶 こんな記事に興味持つような人はみんなmalloc動画見てる人たちばかりだと思いますが、僕はmalloc動画見るまでは「え？メモリの管理ってOS側じゃなくてユーザランドでやってたの？」って感じでした。ここでは僕みたいなmalloc初心者のために、mallocの動作を実際に追いかけて見ようと思います。 mallocの動作を追いかける(mmap編) ← イマココ mallocの動作を追いかける(prev_size編) mallocの動作を追いかける(main_arenaとsbrk編) mallocの動作を追いかける(fastbins編) mallocの動作を追いかける(マルチスレッド編) mallocの動作を追いかける(環境変数編) mallocについて mallocについては、それこそmalloc動画とか、このへんを見ていただければと思うけれど、要

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

はじめに x86系では、long doubleが内部80bit精度の拡張倍精度浮動小数点数フォーマットが採用されている。おそらくx87系命令の内部精度が80bitなのと合わせてあるのだと思われる。それをざっと確認しておく。 拡張倍精度浮動小数点数フォーマットとは Wikipediaのこの図の通りなんだけれど、要するに 符号 1bit 指数部 15bit 仮数部 64bit の合計80bitの表現になっている。ここで気をつけなくてはならないのは、この仮数部はいわゆる「ケチ表現」になっておらず、正規化した数字の最上位ビット1を省略しないこと。従って、単精度、倍精度と仮数部のbit数を比較するなら、63bitの精度になっている。 long double 環境に依存するのだろうが、手元のMacやx86 Linux+GCCの組み合わせでは、long doubleのサイズは16バイト、精度は80bit

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

はじめに 特異値分解、してますか？＞挨拶 今の職場、毎週あるミーティングでみんなが発表するんですが、だいたい「こんなものをSVDしました」という感じなので、僕もSVDしてみたのですが、その続きです。 ソースコードは https://github.com/kaityo256/image_svd においてあります。 はじめにお断りしておきますが、僕はテンソル、というか線形代数全般が苦手です1。なので以下の情報の正確性については保証できません。自分が「あれ？どの足をつぶすんだっけ？」とかごちゃごちゃになるので、その覚書のつもりです。 また、行列$A$の随伴行列(転置して各成分の複素共役をとったもの)を$A^\dagger$で表記することにします。 特異値分解と行列の近似 特異値分解 まず、行列の積を考えます。m行n列の行列と、n行k列の行列の積を取ると、m行k列の行列ができます。 上の式はアイン