読者です 読者をやめる 読者になる 読者になる

Binary Searchと分割統治によるコード最適化

Binary Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。 分割統治(Divide-and-conquer)はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。 今回はランダムに数値…

tracerouteのベストプラクティス

ファイヤウォールの設定が厳しいネットワークや、ロードバランサーが動作するネットワーク、使用するパケットのプロトコルによる違い、等を考えて最も経路発見しやすい方法を考える。 ファイヤウォールの設定が厳しいネットワーク ファイヤウォールの設定が…

Git for WindowsにおけるRubyのputsの挙動

Git for Windows (Git bash)でrubyのプログラムを走らせているときプログラムが停止しているような挙動に遭遇した。デバッグしてみると、停止している箇所はユーザからの入力を受け付ける部分であったが、入力待ちで停止しているのではなく、putsでユーザに…

仮想マシンのスタックとネットワークI/Oについて

仮想マシン=ゲスト=ゲストOS 仮想マシンモニタ=VMM=ハイパーバイザー 仮想化コンセプト 仮想マシンモニタ=VMM(Virtual Machine Monitor)は、自身の子プロセスとして仮想マシンを実行し、ユーザモードでは実行できない命令を仮想マシンが発行したとき…

Sortアルゴリズムの消費メモリについて(続 〜In-place merge sort & Multithread merge sort〜)

Quick Sortは理論上は対象データの並び順によって最速のソートになる可能性があるが、最悪の場合(降順にソートされている場合かつPivotを先頭あるいは最後の要素に選択する場合)はO(n^2)かかってしまう、という問題点があり、Merge Sortは安定してO(nlog(n…

Binary Searchの集合への適用について

Binary Search – topcoder Binary Searchは、例えばソートされている整数のリストにある値が含まれているかどうかを確認するときに使うと、単純なループでチェックするよりもかなり計算量を抑えることができる。単純にループで確認するやり方は計算量がO(n)…

Linuxにおける各種メモリについて

Linuxで扱う様々な種類や単位のメモリについてまとめておく。また、メモリというリソースに関する制御や管理について考察する。 ulimit $ ulimit -a | egrep "memory|stack" max locked memory (kbytes, -l) 64 max memory size (kbytes, -m) unlimited stac…

コード最適化についての考察

文字列のリストとその出現数をカウントして多い方からN個取得する処理を考える。単純にやろうとすれば、とにかく文字列とその出現数をkey/valueとしてカウントしていき、最後にvalueでソートして多い方からN個取得すればいい。 ただし、Nが非常に小さい場合…

ファイルシステム(ext2/ext3/ext4)の基礎まとめ

ext2 正常にアンマウントが実行されなかった場合には、パーティション全体のメタデータと実データの整合性をfsckによって確認する必要がある ブロック構造 - ブロックサイズは1KB,2KB,4KBのいずれか スーパーブロックには全体のi-node数など、グループデスク…

FeliCa/Suicaについて調べた

Suica(FeliCa)がiPhone7とApple Watch series 2に搭載されることになったので、この機会にいろいろ調べてみた。まだ、憶測の域をこえないところはある。 Sony Japan | FeliCa | FeliCaとは | FeliCaって何? SuicaはFelicaに対応した一つのアプリケーショ…

Linuxのブートシーケンスの基礎まとめ

ファームウェア(BIOS or UEFI*1)が マザーボードのROMからメモリにロードされて実行開始し、ハードウェアをスキャン(POST - Power-On Self Test というハードウェアの自己診断を)する [BIOSの場合] プライマリHDDのMBR(先頭のセクタ(512バイト))を見る…

AVL木の更新状況が見たい

AVL木は平衡二分木の一つで、ノードの追加・削除のたびに木の再構成を行い、検索時の計算時間を最小に抑えるようなデータ構造を維持する。木の再構成を行わない場合、最悪の場合には木の片側のみを使ってしまい検索時にO(n)の時間がかかってしまうが、再構成…

Sortアルゴリズムの消費メモリについて(続)

ソートにおいて、ソート対象の配列に対するポインタを操作すれば、各関数の中でソート対象の配列が持つ要素に対するメモリを確保する必要が無くなる。もし、ソート対象の配列の要素の型がポインタよりも小さいサイズであれば、その要素に対するメモリを確保…

いかなる算術演算子も使わずに加算を実現する

という問題を解く。 答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。 具体的には、XORによって各位の加算を実現し、ANDと左シフト演算子によって繰り上げを実現する。 繰り上げ…

動的計画法とメモ化の実行状況が見たい

N x N のマス上にいくつか穴が開いていて、2マスを使うドミノを置いて、穴以外のマスを埋めることができるか、という問題があるとする。愚直に一つずつ試していくやり方としては、動的計画法が使える。ドミノは2マス使うので、縦に置くか、横に置くか、の…

Kubernetes background and network configuration

Kubernetesとそれに関連するミドルウェア Kubernetesはdockerなどのコンテナのスケジューリングやロードバランスを担うクラスタリング制御用運用管理ツール。様々なミドルウェアを組み合わせて使うモジュラー型のアーキテクチャになっている。 etcdは分散KVS…

ハノイの塔でディスク遷移が見たい

Necessary moves over 3 rods = logN - 1 (N = # of disks) 5 disks 8 disks 12 disks 実装はこちら Tower of hanoi with arbitrary disks showing the move among rods · GitHub

Sortアルゴリズムの消費メモリについて

Sortアルゴリズムの消費メモリについて(続) - Tech random memoranda Sortアルゴリズムを自分で書いてみるとそれぞれの特性が良く分かってくる。メモリを最も消費しないのは、Bubbleソートのようにソート対象の配列を直接触っていけるような、時間がかかる…

Sortアルゴリズムについて

Bubbleソート、Quickソート、Mergeソート、をpythonとCで実装してみた。何年ぶりだろうか。なお、pythonはバグがあるので、Cを参照のこと。 Quickソートさえ分かっていればよくて、qsortとか標準ライブラリを使えば良いと思っていたけれど、Mergeソートに負…

Rustの文字列とコピーのlifetimeについて

Rustで簡単なマルチスレッドプログラムを書いているとき、ふとコンパイルが通らなくなって困ったのでいろいろと調べていて、gitterできいて解決したことを書き留めておく。 標準入力から入力された文字列を取得して関数に渡し、その中でチャネルを通してスレ…

ブログがFlickrの写真貼り付けに対応した

staff.hatenablog.com ということでFlickr Proで管理していた時代からだいぶ時間が経ってしまっていた写真を載せてみた。ユーザ選択も写真マルチ選択も簡単で、楽しい。 Touring on the back photo by senbonzakura08 A young man walking into the classic …

Google Code Jam 2016 Qualification Round レビュー in Haskell

今年もスケジュールが合わず参戦できなかったので後日レビュー実施。Pythonで解いた後にHaskellでやってみた。ただしHaskellで解いてみるだけでは今までと変わらない気がするので、do構文とArrayは使用しない、という制約を付けた。ただ、HaskellらしくList…

IPフラグメントされたTCPの接続テストを行う環境をNetwork Namespaceで構築する

TCP接続の際にはIPフラグメントが発生しないように、通常はPath MTU DiscoveryによってEnd-To-Endのパス中で最小のMTUを認識して、そのサイズに収まるようにパケットを送出する。これはTCPのデータ転送を効率良く行うための最適化の結果であり、インターネッ…

Deep Learning勉強会に参加しました

大阪大学人工知能研究会 Deep learningの勉強会に参加して、TensorFlowのBeginnersチュートリアルと、多層パーセプトロンの実装をPythonでやりました。基本的なところは青本やCouseraなどでカバーしてありましたので導入部分は特に問題無く進めましたが、ニ…

numpyの多次元配列の比較時に発生するエラーについて

numpyの多次元配列を比較しようとすると、配列の各要素を比較した結果を配列として返すので、all()やany()を使ってANDやORでreduceした結果を取得できそうだが、以下のようなエラーに遭遇する。 ValueError: The truth value of an array with more than one…

Haskell Stateモナド(状態モナド遊びについての理解)

状態モナド遊び - あどけない話 すごいHaskellたのしく学ぼう!作者: Miran Lipovača,田中英行,村主崇行出版社/メーカー: オーム社発売日: 2012/05/23メディア: 単行本(ソフトカバー)購入: 25人 クリック: 580回この商品を含むブログ (70件) を見る Haskell…

Cousera Machine Learning Course 修了

www.coursera.org CouseraのMachine Learningコースを修了した。iPhoneのアプリもフルに活用していたので、修了までの期間は始めてから1ヶ月ちょっとくらい。このコースにはQuizとAssignmentがあって必要な点数を取らないと修了とみなされないのだが、Octave…

ズンドコキヨシをErlangのgen_fsmを使って書いた

FSMが保持するStateDataを使わないバージョンを追加 そういえばズンドコキヨシは gen_fsm のイイサンプルになるとおもうので、誰か書きませんか。— V (@voluntas) March 18, 2016 ということで書いてみた。graceful exitがなかなか思うようにいかなかったし…

Pandas DataFrame について

Pythonによるデータ分析入門 ―NumPy、pandasを使ったデータ処理作者: Wes McKinney,小林儀匡,鈴木宏尚,瀬戸山雅人,滝口開資,野上大介出版社/メーカー: オライリージャパン発売日: 2013/12/26メディア: 大型本この商品を含むブログ (12件) を見る PandasのDat…

PythonでPandasのPlotを試す

qiita.com こちらの記事のオマージュです。環境は、Windows/Python3.4です。pandasなどはpipでインストールします。groupbyによる集計や、日本語表記などに対応しました。 gist.github.com 補記:可変長引数・キーワード可変長引数 $ cat kwargs.py def func…

Cythonによるパフォーマンス向上

Cython ―Cとの融合によるPythonの高速化作者: Kurt W. Smith,中田秀基,長尾高弘出版社/メーカー: オライリージャパン発売日: 2015/06/19メディア: 大型本この商品を含むブログ (3件) を見る Pythonのような書きやすいインタープリタ型言語で書き始めて結果を…

Pythonの正規表現でバックスラッシュを含む文字列とマッチする場合

Pythonのreモジュールでsearchなどの関数に正規表現を与える場合、rubyやperlなどのように正規表現を直接与えることができず、文字列として与える必要があるため、WindowsのPath区切りにマッチさせたいときなどに正規表現内にバックスラッシュを使いたい場合…

stroll(nicer walk)のC++バージョンを書いた

ディレクトリを幅優先探索で掘っていき、ディレクトリやファイルに対する条件を適用し、それらを与えた条件(関数)によってソートし、見つけたファイルパスを返すライブラリを書いた。ちょうどPythonのos.walkを高機能にしたもので、所望のファイルだけを取…

os.walkを便利に使える関数strollを書いた

リスト指定と正規表現マッチに対応し、ディレクトリパスとファイル名を返すようにして、関数名をnicewalkからstroll*1に変更(短い単語の方が良かった) ディレクトリの扱いを明確化。rootはカレントディレクトリのディレクトリ名で、pathはカレントディレク…

OpenCV入門

Max OS X(10.10.5)でOpenCVに入門してみた。写真はtoeさんです。 導入はbrewで簡単にインストールできるし、インクルード検索パスやライブラリ検索パスもpkg-configで簡単に指定できる。 ネガポジ反転は、~演算子(ビット反転・1の補数)を実行するだけで取…

Pythonのpickleでserializeできない問題の回避策(dill)

読み込んだデータをシリアライズしておきたい場合、pickleを使えば任意のクラスのオブジェクトを扱える。ファイルを開いて、dumpで書き出し、loadで読み出しを行えば良い。しかし、ある構造を持つクラスのオブジェクトをpickleでシリアライズしようとすると…

Pythonで統計処理した結果を表示する場合の便利関数を書いた

全てのキーの組み合わせが無い場合でも、defaultdictの初期値を用いて表を完成させるように修正。 pandasのMultiIndexを使って表示する処理を追記。 統計処理ではネストされた辞書(dict)が多用することで、比較的簡単に所望の複合キーに対応する値を取得し…

ファイルの最後の方に出現する行を取得する

大量のファイル、しかもサイズの大きいものを読み込んで、ある特定の小数の行だけを取り出したいような場合で、その特定の行がいつもファイルの最後に近い位置に出現することが期待できる場合、ファイルを先頭から読み込んで行って、特定の行に達するまで読…

セーブ機能を追加しました@transatonce.appspot.com

transatonce 単語を翻訳するとき、こういった要求を満たせるサイトがあると良いと思って作っているものです。 いくつかの単語を一度に翻訳したい(英文の記事や論文を読み終わったあとでメモしておいた単語を at once に翻訳したい) それらを一つのページで…

Valgrind で Pthread の Debug

OS X Yosemite (10.10.5) でC(GNU99)でpthreadを用いたマルチスレッドプログラムを書いていて、なかなかerrorが取れなかったときに以下ツイートを起点にした議論を見て、ValgrindのHelgrind toolが使えそうということで使ってみた。 pthread_create に渡した…

Go で Package を Build

うまくいかなくなったビルドが元通りにうまくいくようになったので、とりあえずそのメモ $ env | grep GO GOROOT=/usr/local/Cellar/go/1.5.1/libexec GOPATH=/Users/nishidy/.go $ head -n1 *go ==> count.go <== package ParseWikipediaXML ==> parse.go <…

Erlang で Process の Join

Erlang(BEAM)のProcessは、他言語でThread.Joinのようなスレッド・プロセスの終了を待つ機能が無さそうなので、Receiveを用いたメッセージパッシングで実装した 今回は、Preforkモデルのように予めProcessをワーカースレッド的に起動しておく実装ではなく、…

ISUCON5から学ぶいろいろ

ISUCON5のエントリを見てるとたくさん得られることがある。コンテストといっても、実際に課題になった技術は単に知っているだけのものとは違って、手を動かして実際に実装してみないといけないな、と思わせるには十分なインパクトがある。単に知っているだけ…

アンアラインメントデータアクセスについて

メモリにデータを格納する際、通常はアラインメントに沿って展開される。ワード単位以上のデータを格納する場合、その開始アドレスがワード単位の整数倍になっていないと、メモリフェッチが余分に発生してスループットが落ちるか、アラインメント違反によっ…

MySQLのグループコミットとそれに連想するもの

グループコミット MySQLでは、バイナリログへの書き込みのタイミングを、sync_binlogによってユーザが指定することができる。具体的にはsync_binlogの値によって、何回コミットを行ったらバイナリログをディスクにフラッシュするか、を指示するため、sync_bi…

Haskellのパース処理(文字コードについて)

文字コードについて Unicodeは文字集合である。Unicodeで規定される文字を、UTF-8やUTF-16などの符号化方式で扱うことができる(e.g. Shift-JISやEUC-JPは別の文字集合を扱う)。Unicodeでは文字集合を、コードポイントという各文字に対する通し番号のようなも…

純粋関数型言語 Haskell 基礎まとめ

すごいHaskellたのしく学ぼう!作者: Miran Lipovaca出版社/メーカー: オーム社発売日: 2012/09/21メディア: Kindle版購入: 4人 クリック: 9回この商品を含むブログを見る Haskellを学ぶ上で難しいのは、その概念が高度に抽象化されている点にある*1。そのた…

Embulk.batのハックについて

WindowsでEmbulkを使う場合はJavaをインストールした上で、Quick startにあるように以下のコマンドでファイルをダウンロードしたものを実行する > PowerShell -Command "& {Invoke-WebRequest http://dl.embulk.org/embulk-latest.jar -OutFile embulk.bat}"…

ConsulのDNSインターフェースから学ぶDNSの基本

ConsulはDNSインターフェースを通してノードとサービスの死活監視の状況を提供することができる e.g. ロードバランスのためラウンドロビンしているノード群を問い合わせ結果として提供するとき、問い合わせ結果からダウンしたノード・サービスを動的に外す D…

YAPC::Asia Tokyo 2015 に参加しました

自分が聞いた2日間の中で良かったトークと、見るべきだったけど見れなかったトークについても載せておいて、次回の教訓にする 単純だけど重要なことは、「直感で見たいと思ったものを優先して見る(なんやかんや深く考え過ぎない)」、「良い人のトークは良…