組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
Graphillion: 数え上げおねえさんを救え / Don't count naively
Graphillion は膨大な数のグラフに対して検索や最適化、列挙を行うための Python モジュールです。このビデオは Graphillion の概要を知るためのチュートリアルです。「フカシギの数え方」 http://youtu.be/Q4gTV4r0zRs の続編として作成されました。 Graphillion is a Python software package on search, optimization, and enumeration for a very large set of graphs. This video is a quick tutorial to learn what Graphillion is. The story follows our previous episode, "Let's count!" http://youtu.be/Q4gT
再帰クイックソートの可視化: Days on the Moon
「いやなブログ - JavaScript でソートアルゴリズムを可視化」より。何も考えずに再帰処理のクイックソートの様子を逐次描画しようとするとこうなります。 function quickSort(data, begin, end, log) { if (begin >= end) return data; var pivotPos = begin; var pivot = data[pivotPos]; for (var i = begin + 1; i < end; i++) { if (data[i] < pivot) { var temp = data[i]; data[i] = data[pivotPos + 1]; data[pivotPos + 1] = data[pivotPos]; data[pivotPos] = temp; pivotPos++; } } log(da
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
最適化超入門
本スライドは、弊社の梅本により弊社内の技術勉強会で使用されたものです。 近年注目を集めるアーキテクチャーである「Transformer」の解説スライドとなっております。 "Arithmer Seminar" is weekly held, where professionals from within and outside our company give lectures on their respective expertise. The slides are made by the lecturer from outside our company, and shared here with his/her permission. Arithmer株式会社は東京大学大学院数理科学研究科発の数学の会社です。私達は現代数学を応用して、様々な分野のソリューションに、新しい高度AIシステム
視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは
大規模データ処理のための行列の低ランク近似 -- SVD から用例ベースの行列分解まで -- - 武蔵野日記
id:naoya さんのLatent Semantic Indexing の記事に触発されて、ここ1週間ほどちょくちょく見ている行列の近似計算手法について書いてみる。ここでやりたいのは単語-文書行列(どの単語がどの文書に出てきたかの共起行列)や購入者-アイテム行列(どの人がどの本を買ったかとか、推薦エンジンで使う行列)、ページ-リンク行列(どのページからどのページにリンクが出ているか、もしくはリンクをもらっているか。PageRank などページのランキングの計算に使う)、といったような行列を計算するとき、大規模行列だと計算量・記憶スペースともに膨大なので、事前にある程度計算しておけるのであれば、できるだけ小さくしておきたい(そして可能ならば精度も上げたい)、という手法である。 行列の圧縮には元の行列を A (m行n列)とすると A = USV^T というように3つに分解することが多いが、も
ハフマン符号 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ハフマン符号" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2011年9月） ハフマン符号（ハフマンふごう、英: Huffman coding）とは、1952年にデビッド・ハフマンによって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される[1][2]。 ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。 コンパクト符号やエントロピー符号の一つ。JPEGやZIP (Deflate)
Solving Every Sudoku Puzzle
by Peter Norvig Note: This page is the original 2006 essay; an updated Python 3 Jupyter notebook is available here and should probably be read instead of this page. In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about one page of code for the main idea and two pages for embellishments) using two ideas: constraint propagation and search. Sudoku Not
キャッシュアルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "キャッシュアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年8月） キャッシュアルゴリズム（英: cache algorithm）は、コンピュータ上で情報を格納するキャッシュを管理するプログラムまたはハードウェア構造を最適化するアルゴリズム群。キャッシュが一杯になったとき、このアルゴリズムで新たな情報を格納するための場所を選択し確保する。置換アルゴリズムあるいは置換ポリシーとも。 キャッシュのヒット率（hit rate）とは、探しているデータがキャッシュ上で見つかる率（頻度）である。キャッシュサイズを増やさずにヒット
アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。
AWSユーザーは必ず覚えておきたいExponential Backoffアルゴリズムとは何か - yoshidashingo
cloudpackエバンジェリストの吉田真吾（@yoshidashingo）です。 Exponential Backoff 直訳すると「指数関数的後退」つまり、指数関数的に処理のリトライ間隔を後退させるアルゴリズムのことです。 詳しくはWikipediaに記載があります。 Exponential backoff - Wikipedia 日本語でブログに書かれている方もいらっしゃいます。 exponential backoffのメモ – Siguniang's Blog これを見ていると、どうやらこのアルゴリズムは古くから通信装置において、イーサネットフレームのデータ送信時にコリジョン（衝突）を検出したら一定時間待機して再送して、処理を完結させるためのアルゴリズムとして使われているようです。 通信機器の世界に限らず、アプリケーションの分野でも、大規模で予測不能な処理量を有限なリソースでさばく
「高速文字列解析の世界」を読むのに参考にした資料
現時点では、ビッグデータではなく、サンプリングされたデータを扱っているのですが、「大規模」データであることには違いなく、それらを如何に高速に処理するかに頭を悩ませています。 この本は、その悩みを解決する助けになりました。 実際には、いくらかの前提知識が必要ですし、対象とする問題や開発環境も考慮しなければなりませんでした。 部分的な調整しかできていませんが、それでも、当初は致命的とも思われた実行速度を、何とか現実的な速度まで持てくることができました。 以下に、この本を読む際に参考にしたページ、各種実装関連のページなどへのリンクを（備忘録も兼ねて）記しておきます。 なお、「参考にした」ページですので、必ずしも本書にて解説されている項目とは限りません。 ※実装コードの項目に記載したライセンスは調査時のものですし、未確認・未記載のものもあります。利用に際しては、それぞれ確認が必要です。 ■全般
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Non-negative Matrix Factorization（非負値行列因子分解） - あらびき日記
レコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1
Amazon.co.jp: 情報検索アルゴリズム: 研二,北, 和彦,津田, 正幹,獅々堀: 本
さまざまなアルゴリズムをアニメーションで解説してくれる『Algomation』 | 100SHIKI
Paxos
