実用アルゴリズムの基礎「動的計画法」と機械学習の基礎「類似度」を知る
実用的なソフトウエアを開発するにはアルゴリズムの知識は欠かせない。基礎から機械学習まで、厳選した10個のアルゴリズムをPythonによる実装とともに解説する。 ［7 動的計画法］ レーベンシュタイン距離 多くの人にとって、アルゴリズムの学習の最初の壁となるのが、「動的計画法」ではないでしょうか。動的計画法は、「問題の部分的な結果を記録・利用しながら、最終的な結果を求める」手法の総称です。クイックソートや深さ優先探索のような手法よりも、1 段か2段、抽象的な概念である点と、アルゴリズムを可視化しにくい点が、難しく感じる原因なのだと思われます。また、“動的計画法”という名称が内容に合っていないことも、動的計画法をわかりにくくしていると言えるでしょう。 しかし、多くの有用なアルゴリズムは動的計画法の手法を使っているので、避けて通ることはできません。 ここでは、動的計画法で「レーベンシュタイン距離
Parsing Expression Grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
巡回冗長検査 - Wikipedia
巡回冗長検査（じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。 デジタル回路で簡単に実装でき、数学的にも分析が容易であり、また、ビットのランダム誤りやバースト誤りを検出できるので、HDLC手順やCSMA/CD方式などにおいて誤りチェック・伝送路ノイズチェックによく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。 W・ウェスレイ・ピーターソンが発明し
動的計画法 - Wikipedia
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。 計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。 「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に現
高次元ベクトルデータ検索技術「NGT」のpythonライブラリ公開のお知らせ
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog はじめに 検索技術の菅原です。 以前にこのTech Blogで紹介されたNGT（Neighborhood Graph and Tree）という高速な近傍探索を実現するソフトウエアのpython用インターフェースが公開されました。pythonは機械学習のライブラリが多く公開されており、より手軽にNGTを組み合わせて使うことができるでしょう。 そこで今回はword2vecのベクトルを近傍探索する実践的な内容を紹介します。word2vecを扱うライブラリとしてgensimを使用します。word2vecやgensimの詳しい説明は省略しますが、分からなくてもpythonの文法を知っていれば理解できると思います。今回使用した環境はMacBo
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ - エンジニアHub｜若手Webエンジニアのキャリアを考える！
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ 過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。 2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平（うらべ・しょうへい／@shyouhei／以下、卜部）は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。 オブジェクト指向スクリプト言語 Ruby HashDoSの概要 なぜ約6年後の今、修正内容を公開するに至ったか？ 前史：すでに内包されていたリスク
Algorithm - JavaScript - 新兵の整列(Lining Up Recruits) | Kamimura's blog
Algorithm - JavaScript - 新兵の整列(Lining Up Recruits)
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
Ruby で高速なプログラムを書く
2. 自己紹介：遠藤侑介 • Ruby コミッタ（2008年～） – Rubyのテストを増強した – コードカバレッジ測定機能を 実装した – キーワード引数を実装した – Ruby 2.0 リリースマネージャ だった – 最近は何もしてない 2 ’06下 ’07上 ’07下 ’08上 60 70 80 90 100 coverage(%) 70% 85% C0カバレッジ遷移 3. と私 • 立ち上げの時に @chezou さんに相談を受けた • 初期に数回だけ参加した • Kawasaki.rb #005 （2013-10-23）で発表した – 以上（すみません） • ちなみに Kawasaki.rb #005 で発表したものは 3 4. eval$s=%q(eval(%w(B=92.chr;N=10.chr;n=0;e=->(s){Q[Q[s,B],?"].gsub(N,B+?n)};
はてな社内の勉強会で構造学習について発表しました - yasuhisa's blog
先週末、はてな社内の勉強会で構造学習、特に実装が簡単な構造化パーセプトロンについて発表しました。発表資料と説明用にサンプルで書いたPerlの品詞タグ付けのコードへのリンクを張っておきます。 今日からできる構造学習(主に構造化パーセプトロンについて) from syou6162 structured_perceptron/structured_perceptron.pl at master · syou6162/structured_perceptron 「えっ、Perlかよ」という人がいるといけないので、Clojureで構造化パーセプトロンを使った係り受け解析のサンプルコードへのリンクも張っておきます(2種類あります)。PerlもClojureもあれば8割くらいの人はカバーできそうなので、安心ですね。 syou6162/simple_shift_reduce_parsing syou616
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
定番アルゴリズム本リスト - カレーなる辛口Javaな加齢日記
どうせ何度も使い回ししそうなので，独立した項目に切り離した． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21件) を見るアルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/12/26メディア: 単行本購入: 1人 クリック: 4回
三目並べで学ぶミニマックス法 | POSTD
最近、「絶対に勝てない三目並べ」のゲームを作ったのですが、非常にささやかながらも楽しいプロジェクトで、いろいろ学ぶこともできました。ゲームの全体像に興味がある方は、 こちらでゲームを試してみてください 。 無敵のゲームにするには、コンピュータ側が全ての手を計算し、何らかの基準を用いて最善の手を決められるようなアルゴリズムを作る必要があります。多岐にわたって調べた結果、このプロジェクトにはどうやら ミニマックス アルゴリズムが適当そうだということが分かりました。 このアルゴリズムを根本的な意味で真に理解し、自分のゲームに実装できるようになるまでにはある程度の時間が必要でした。多くのコードサンプルと説明に目を通しましたが、私が能なしだからか、どれを見てもプロセスの内実を十分に理解することはできなかったのです。この投稿が、ミニマックスアルゴリズムに関する皆さんの理解に少しでもお役に立てたらと思い
Mac、iOSで、rand()関数の疑似乱数アルゴリズムがヘン！ - Qiita
話の発端は、StackOverflowの、この質問にあった。 StackOverflow 日本語版 - c言語での乱数生成 質問に対する回答は、きわめて単純で、rand()関数を、取得したい乱数の個数分、呼んでやりましょうというもの。 いちおう、XcodeのCommand Line Toolで、サンプルコードを作って、それを実行してみて、ちゃんと意図したとおりの結果になることを確認する。が、ここで奇妙なことに気づく。 何度実行しても、初項が4になる。 試しに、こんなC言語のコードを書いて、Xcodeで実行してみる。 #include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, const char * argv[]) { unsigned int i; unsigned int seed = (uns
もし女子大生プログラマに『アルゴリズム』を図解で教えるとしたら - paiza times
2014年4月16日より2014年5月14日まで開催していたpaizaオンラインハッカソン（略してPOH![ポー！]）Vol.2「女子大生とペアプロするだけの簡単なお仕事です！」で提出された最速コードはどのような高速化のアプローチでで生み出されたのでしょうか？ POH Vol.2に登場した女子大生インターンプログラマの木野ちゃん（左のイラスト）にアルゴリズムを図解で教えるとしたら、どう教えるだろうか、という事で、今回は図解してみました。 今回は前回の最速コード発表レポート（【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選）に引き続き、最速コードの裏側に迫ります。 ■高速化のアプローチ方法について 今回もPOH Vol.1 と同様に、POH Vol.2では計算量の改善による高速化を柱とするアプローチを想定して出題されました。基本は定数倍高速化によって想定解法よりも悪い計算量の
オブジェクト指向プログラミング再入門
24. よくない設計 ! ／￣￣＼ ／ _ノ ＼ | （ ●）（●） | （__人__） | ｀ ⌒´ﾉ | } ヽ } ヽ､.,＿＿ __ノ _, ､ -― ''"::l:::::::＼ｰ-..,ノ,､.ﾞ,i ､ /;;;;;;::ﾞ:':､::::::::::::|＿:::;､>､_ l|||||ﾞ!:ﾞ､-､_ 丿;;;;;;;;;;;:::::i::::::::::::::／:::::::＼ﾞ'' ﾞ||i l＼>::::ﾞ'ｰ､ . i;;;;;;;;;;;;;;;;;;;;;;|::::::::::::::＼::::::::::＼ .||||i|::::ヽ::::::|:::! 年齢は？ 店員（売る人） ! ／￣￣＼ ／ _ノ ＼ | （ ●）（●） | （__人__） | ｀ ⌒´ﾉ |
MSのあまりにもひどいマクロ - ここは匣
2013-10-10 MSのあまりにもひどいマクロ maxとかminとかが使えないと思ったらminwindef.hとかいうところでマクロとして定義されていてキレそうっていうかこれは完全にブチギレ— 秋弦めい (@maytheplic) October 10, 2013 http://stackoverflow.com/questions/5004858/stdmin-gives-error StackOverflowにも同じような事言ってる人が居たので引用。 どうやら以下のようなコードがエラーになるらしいです #include <algorithm> #include <Windows.h> int main() { int k = std::min(3, 4); return 0; } error C2589: '(' : illegal token on right side of
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
大規模量子コンピュータに期待。世界初、複数の論理量子ビットを復号する量子誤り訂正アルゴリズム開発
計算量オーダーについて - Qiita
スターバックスは2フェーズコミットを使わない - gregors-ramblings-ja - Google Code