【またかよ】「Haskellでクイックソート」問題【何度目だ】Pin📍AppBrew CTO @spinute クイックソート何行だと思う？ rubyが40行、c++が35行、haskellは5行だよ？ 大きいのと小さいのにちぎる、空だったら終わる、それが本質でそれだけが必要最低限。 クイックソートのイデアは五行に収まるらしい 2013-01-27 00:18:27
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
クラウド時代の新しいソートアルゴリズムTask Queue Sortを発明しました. - kissrobberの日記
Task Queue Sortは, Google App Engineの並列処理の仕組みTaskQueueを使ってソート処理を行う,クラウド時代の新しいソートアルゴリズムです. （クラウドソートとも言う） ネタ元 http://d.hatena.ne.jp/gfx/20110519/1305810786 http://www.yuyak.com/1339 http://togetter.com/li/137698 重要な仕様 ソートした結果のソート順は保証されない. たまにソート対象の要素が増える事がある. Java(slim3)での実装例 TaskQueueを投げる側 public class IndexController extends Controller { @Override public Navigation run() throws Exception { addToQue
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック：最強最速アルゴリズマー養成講座（1/3 ページ） 競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 教育的な観点から見るTopCoder 今回からTopCoderに関する実践的アルゴリズムを解説していく予定でしたが、序盤のうちに触れておきたいことがありましたので、今回の枕は“教育的視点から見るTopCoder”というテーマで少し書こうかと思います。 まず、最初に宣言しておきたいことは、この連載は初心者向きである、ということです。「どう考えても上級者向けだろう」という意見はたくさんの方から寄せられていますが、筆者は、まだプログラミングレ
広く知られているinsertion sortのコードは駄目すぎる - やねうらお−よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術
insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 ) ■ 日本語版 Wikipediaの日本語のページのコードを引用すると次のようになっている。 for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味に
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
パフォーマンス劣化はインデックスのせいなのか!? をみっちり検証
リーフブロックの中に格納されている値とは？ それでは、実際にリーフブロック-1と0にはどのような値が格納されているのか、ブロックの中身を確認してみることにしましょう。 ブロックの中身は、以下コマンドで確認できます。 SQL> SELECT DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(16831123) as "FILE_ID(LEAFBLOCK-1)", 2 DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(16831123) as "BLOCK_ID(LEAFBLOCK-1)", 3 DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(16831262) as "FILE_ID(LEAFBLOCK0)", 4 DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(16831262) as
Oracleパフォーマンス障害の克服（3）Bツリーインデックスに最高のパフォーマンスを―@IT
Oracleデータベースの運用管理者は、突発的に直面するパフォーマンス障害にどうやって対処したらよいか。本連載は、非常に複雑なOracleのアーキテクチャに頭を悩ます管理者に向け、短時間で問題を切り分け、対処法を見つけるノウハウを紹介する。対象とするバージョンはOracle8から9iまでを基本とし、10gの情報は随時加えていく。（編集局） SQL処理（インデックス）にかかわる確認 前回「ロックをつぶせ！最初に疑うべき原因」では、SQLにかかわる問題の解決方法としてロックの確認方法を説明しました。データ更新には必ずオブジェクトの処理が行われていることを理解できたと思います。 SQL文をきっかけに更新されるOracleサーバ内のオブジェクトとして、今回はインデックスを取り上げます。SQL文発行時、直接データとのかかわりを意識しづらいオブジェクトなので、データの更新頻度やインデックスの作り方によ
Oracle の B*Tree インデックスの内部構造についてお勉強中（その３）
このリーフは必ずソートされて状態で管理されているがために、データの挿入、更新でリーフ分割によるインデックスのパフォーマンス劣化が発生するわけです。また、この解析からわかるように同一ブロック内もしくは近くのブロック内には第一キーが同じものがかたまって存在します。それゆえ、複合索引の場合は、第一キーのみによる SELECT 文でも、効率よくアクセスが可能（ INDEX RANGE SCAN ）で、逆に第二キーのみによる SELECT 文では、いくつものブロックを読む（ INDEX SKIP SCAN もしくは TABE FULL SCAN ）必要がでてくるわけです。 見ての通り、同一ブロック内の第一キーの同一値がほぼ全て網羅されています。Oracle はブロック単位で I/O 管理されているため、上記の例だと where ID=1 のように第一キーの等価評価による絞り込みを行う場合、ブロックを
Oracle の B*Tree インデックスの内部構造についてお勉強中（その２）
まずは前エントリで書いた Oracle のインデックス構造図解を再掲から。 本題です。Oracle のインデックスの内容をダンプする TreeDump の使い方と解析方法について説明をします。これも定型文なので、覚えておいて損はないかと思います。特にインデックスに関して深追いするなら必須のテクニックです。参考にしたページは下記の２つです。 Bツリーインデックスに最高のパフォーマンスを（1/4） − ＠IT パフォーマンス劣化はインデックスのせいなのか!? をみっちり検証 − ＠IT 特に株式会社インサイトテクノロジーの記事が秀逸です。この会社の Oracle スキルは尋常じゃぁありませんね。お仕事で見ている DB システムでは、同社が開発している Performance Insight というツールを導入して Oracle を運用管理しているのですが、パフォーマンスチューニング、障害監視な
Oracle の B*Tree インデックスの内部構造についてお勉強中（その１）
お仕事のデータベース一式のリース切れ間近ということで、リース延長で耐えることができるのか、それともシステム更改が必要なのかを見極めるため、最近はデータベース周りのチューニングばかりやってます。 当初設計時に、５年間持つ設計をしたのですが、流石に５年目にもなると予定とはそれなりに乖離が発生するものです。テーブル＆インデックス設計をユーザ向けの処理をとにかく高速に処理できるように設計したので、ユーザ向けの処理は速度的に全然大丈夫なのですが、データの肥大化によるバッチ処理のパフォーマンス劣化が顕著です。単純にストレージと CPU パワーが足りていないのでしょう。 しかしながらチューニングの余地はまだまだ十分にありそうです。バッチ向けの最適化を図ることにしました。うまくいけば来年度どころか、後数年はリース延長で延命できるかもしれません。 今回実施したチューニングの１つのポイントとして、バッチ処理向
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
【予算5,000〜10,000pt情報が良い＆多ければそれ以上も】 東京23区武三地区で、タクシーの営収につながる情報を教えてください ・時間帯、曜日別で流し営業のコ…
【予算5,000〜10,000pt情報が良い＆多ければそれ以上も】 東京23区武三地区で、タクシーの営収につながる情報を教えてください ・時間帯、曜日別で流し営業のコツや具体的に流すエリア ・時間帯、曜日別で比較的流れる、台数が少ない、客が付きやすいツケ待ちの場所 ・その他営収に繋がる情報があればどんな小さな抽象的〜具体的情報を ブレーンストーミングのように何でも教えて下さい 私は平日池袋、新宿、渋谷周辺を営業していますが、特にエリア等は限定しません 収入に直結し、業界的にも貴重な情報のため、高額なポイントを用意しました これでも安過ぎるくらいだとは思いますが、この質問がここを見ている “一部の”現役ドライバーが生き残る情報になるのではないでしょうか インターネット上に存在する情報は個人の日記が殆どで、検索での限界を感じ ここに質問してみました 出番の日に実際に営業して確認もしたいと思いま
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
DHTからAmazon Dynamoまで — ありえるえりあ
IBM Developer
