いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
プリム法（最小全域木問題）
プリム法 (Prim's MST Algorithm) は最小全域木問題を効率的に解くグラフ理論におけるアルゴリズムです。 最小全域木 (MST: Minimum Spanning Tree) とは，グラフを構成する「辺の重みの総和」が最小となる全域木です。 「全域」とは，元のグラフがあって，その部分グラフのうち（辺の構成は変わっていても）頂点集合が同じグラフを指します。 木とは連結 (connected) でかつ閉路 (loop) が無いグラフなので，つまり，元となる（木ではない）グラフがあって， そこから，切り離された頂点を作らずに（連結であり），閉路を作るような辺が「辺の重みの総和が最小となるように」全て取り除かれた（木である）グラフを求める問題です。 MST（最小全域木）を求めるアルゴリズムとしては，ここで説明するプリム法の他にクラスカル法が有名です。 アルゴリズム 以下のグラフを
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
ActionScript入門Wiki@rsakane - バックトラックで経路探索を行う
おすすめリンク | 価格比較@price | オークション落札相場@price | デジカメプリント | 年賀状 | ましかくプリント | @wiki - 無料レンタルウィキサービス | プライバシーポリシー| 関連ページ| 関連ホットワード
第4回 できるだけ短いルートでゴールに到達する
図1を見てください。A地点にロボットがいます。B地点がゴールです。途中には障害物があります。障害物を避けながらなるべく少ない歩数でロボットをゴールまで移動させるアルゴリズムを作成し，その移動したルートを図に示してください。ロボットは縦，横，斜めに進めるものとします＊1。 私は結構あきっぽいようです。プログラミングも黙々とやらなくてはいけないものは苦手です。ついふらふらと出かけてしまったりして，なぜかバグが多くなってしまいます。そんな私でも好きだと言えそうなのが画像処理やグラフ問題といった「作った結果が目に見える」題材です。自分で作った成果が目で見てすぐわかると，とても楽しくなります。今回の問題はそうしたものの一つです。プログラミングに飽きてきたら，今回のような問題にちょっとチャレンジしてみてください。きっと楽しめると思います。 手当たり次第に調べてもうまくいかない 問題を整理してみましょう
無職のプログラミング A*アルゴリズムっぽいものをJavaScriptで実装する
前回のブログから4日も日があいてしまった。 アルゴリズムをちょっと調べていて、迷路探索などに使われるA*(エースター)アルゴリズムを知った。 覚えて損は無いだろうから、JavaScriptでA*を組んでみることにした。 まず、A*を知ったこのページのソースコードをナナメ読みした。 第4回 できるだけ短いルートでゴールに到達する - 地球にやさしいアルゴリズム：ITpro 上記のページではA*についての詳しい説明が無かったので、エースターで検索して見つけた以下のページを読んで何となく理解した。 A*（A-star：エースター）探索アルゴリズム｜カンガルーハウス 二次元長方形の迷路から脱出するプログラムを作ってみた。 仕様はこのようにした。 ・スタートからの移動コストと、ゴールまでの推定移動コストを足してコストを算出 ・現在地の座標から次に探索する座標を求める(次の座標は必ず現在地に隣接する座
A*アルゴリズムまとめ - octech
数年ぶりにA*アルゴリズムを実装したので、まとめなおしておきます。何回かじっくり読むとようやく理解が出来てきました。基本的にそんなに難しくないアルゴリズムです。 概要 「A*アルゴリズム」は、A-Star（エースター）と読み、パス探索アルゴリズムの一つです。 ノードネットワーク上にスタート地点とゴール地点を結ぶパスが存在すれば、最悪でもそのパスの存在を確認できるアルゴリズムです（見落とすことがない）。 内容はシンプルな再帰計算で、コスト計算の部分にヒューリスティックと呼ばれるパラメータがあり、その算出アルゴリズムを変更することにより、各種アプリの状況に応じた高速化と最適化が望めます。 2007-07-16 修正 「A* - Wikipedia」の擬似コードを見ていたら、自分の書いたコードでは最適なルートを計算しない可能性があることが分かりましたので修正しました。下記のC++的擬似コード内で
A*（A-star：エースター）探索アルゴリズムの原理
当サイトは、興味のあること、疑問に思って調べたこと、作業したことなどを、忘れないように書き留めたノートです。 いただいたコメントはすべて、有難く拝見しております。すごく喜んでおります。 その他のお問い合わせは、自己紹介ページからお願いします。 最近よくご覧いただいているページはこちらです。 経路探索アルゴリズムのひとつに、A*（A-star：エースター）探索アルゴリズムと呼ばれるものがあります。 今、迷路の中でスタート地点からゴール地点まで歩くことを考えます。早くゴールへたどり着くために、A*探索アルゴリズムを用いて、最短経路を計算してみます。 A*探索アルゴリズムにはコストという概念があります。今、単純に「コスト」＝「距離」と置き換えて考えると、迷路が一様の場合はコストの一番小さな経路が最短経路といえます。つまり、コストが小さくなるような経路を探していくと、最短経路が見つかるわけです。
モバイルゲームの歴史を年代別にご紹介します。モバイルゲームの成長と今後について詳しく解説していきます。
モバイルゲーム 物凄い勢いで勃興したモバイルゲーム業界は、いろいろな課題や問題に直面しながらも巨大化し、今日の時点でのスマートフォン向けゲームの市場へと継承されていきます。 モバイルゲームの歴史 2001 Javaアプリと3Dゲームの登場 Javaが利用できるようになったことにより、ダウンロード型のゲームが供給できるようになりました。 2002 携帯電話端末の大容量化・3D化競争 Java搭載携帯電話端末が登場してからごく僅か1年の間に、アプリのサイズに関しては10倍に広大化し、表現方法も2Dから3Dにシフトし始めました。J-PHONEは『ゼビウス』や『スペースハリアー』などといった昔のアーケードゲームを、ドコモはSIMCITYなどパソコンで世界的規模のヒットを飛ばしたゲームを主力商品としていました。 2003 モバイルゲームの一般化 メモリの制限が厳しいJava仮想マシン上ではなく、OS
DextroII先生のロマサガ閃きシステムのアルゴリズム講座
つしま（あなたの原稿はどこから） @chartreuse37 @DextroII 先生ッ！ サガシリーズの閃きシステムの概念ってどうなってるんですか！？ って弟が言ってました よかったらちらっと教えてください
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック：最強最速アルゴリズマー養成講座（1/3 ページ） 競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 教育的な観点から見るTopCoder 今回からTopCoderに関する実践的アルゴリズムを解説していく予定でしたが、序盤のうちに触れておきたいことがありましたので、今回の枕は“教育的視点から見るTopCoder”というテーマで少し書こうかと思います。 まず、最初に宣言しておきたいことは、この連載は初心者向きである、ということです。「どう考えても上級者向けだろう」という意見はたくさんの方から寄せられていますが、筆者は、まだプログラミングレ
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www40.atwiki.jp/spellbound/pages/1566.html