CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。
![50年前に作られたメモリ管理アルゴリズム「Buddy memory allocation」](https://cdn-ak-scissors.b.st-hatena.com/image/square/143d333e266b349775b9c02ff88aa76f25bc6a3d/height=288;version=1;width=512/https%3A%2F%2Fcodezine.jp%2Fstatic%2Fimages%2Farticle%2F9325%2F9325_t.gif)
たくさんのデータを大小関係に従って、小さい順(昇順)や大きい順(降順)に並び替える作業はソート(整列)と呼ばれ、ソフトウェア・プログラムではよく使われています。このようなソート作業を行うために並び替えの方法を手順化したのが「ソート・アルゴリズム」で、アイデアを理解すると「ほほー、なるほど」と思えるのですが、複雑すぎて理解しづらいものもあります。そんなソート・アルゴリズムの中でも有名で、仕組みを理解しておきたいものばかりを題材に、なんとフォークダンスに合わせてアルゴリズムを表現するムービー集「AlgoRythmics」が公開されており、学習効果があるかどうかは脇に置いて、思わず見入ってしまう魅惑のムービーとなっています。 最も有名なソート・アルゴリズムの一つである「バブルソート」をハンガリーのフォークダンスにのせて表現するのが「Bubble-sort with Hungarian ("Csá
プログラマの面接をするときには実際にコーディングをしてもらうべきという話は良く聞くが、もうちょっと細かくどういうお題を出したら良いかとか、どういう風に評価したら良いかとかの話はあんまり聞かない気がする。せっかくなので、ユビレジでの面接で私がコーディングについて確認するときのパターンを、いくつか紹介してみようと思う。 実際にコードを書いてもらうパターン 候補者がどのくらいプログラミングできそうかの予備情報がない場合に、簡単なアルゴリズムを書いてもらうことが多い。例としては、 Linked Listを書いてください Stackを書いてください など。ここで、おもむろに int main(int argc, char* argv[]) { などと書き始める人は、あまり良い印象をもたれない。 class Stack などと書き始める人は上よりは期待できる。 このとき、わざと出題で詳細をあまり明らか
dlmalloc, tcmalloc, jemallocについて,以下の各記事を読めば各mallocのアルゴリズムはわかるはず. dlmalloc Linuxの一部やAndroidのDalvik VMで利用されている.シンプルながらうまく考えられている. チャンク(連続空き領域1つ)の境界と構造体の境界が違う所が罠. http://g.oswego.edu/dl/html/malloc.html http://mkosaki.blog46.fc2.com/blog-entry-241.html にわかりやすい講演資料が,と思ったら動画がprivateになってる… tcmalloc thread-caching malloc. Googleで利用されている. スレッドがキャッシュ持つのでfreeしてもメモリ利用量が減らない!のが罠. http://goog-perftools.sourcef
« git で pull-request を clone する設定が覚えられないので alias 書いた。 | Main | Vim で peco する「veco」書いた。 » 掟1 プログラムが時間を費やす箇所がどこにあるのかは知り得ない。ボトルネックは意外な場所で発生するため後知恵で批判してはならないし、ボトルネックがどこにあるか証明出来るまではスピードハックを入れてはいけない。 掟2 測定しよう。測定し終えるまでは、さらにはコードの一部分が残りのコードの支配的な量とならないならばチューニングを行ってはいけない。 掟3 凝ったアルゴリズムは、n が小さいときに低速となり、通常 n は小さい。凝ったアルゴリズムは大きな定数を有する。n は頻繁に大きくなり得ることを知るまでは凝ったアルゴリズムを得てはならない。 (n が大きくなる場合であっても、まず掟 2 を行いなさい) 掟4 凝ったアル
初めまして。Gunosyのマーケティング担当の竹谷と申します。 ※下部がきれてしまうというCSSマターの問題があったため同内容をはらせて頂いております。 http://bit.ly/10cRtX6 週末から、Gunosyに対する批判記事があり様々なユーザー様から質問を頂いているので簡単に所感を書かせて頂きたく思います。 ここまで大きな騒動になっているにも関わらず会社から何も出さないことは良くないと思いましたのでこの場を借りて所感を記載させて頂きます。 おそらく批判記事の内容を見ていると大きく分類して論点となるのは以下かと思います。 1.Gunosyは、はてブの再編集である/アルゴリズムなど存在しない? 結論から先に言わせて頂きますと、そんなことは無いです。ただ、我々のアルゴリズムの未熟さにより実際にそういう風に見えてしまう部分はあると思います。 現状、以下のフローで配信準備を行っております
ハッシュテーブルからエントリーを検索する処理は,一般に定数時間で済むとされている。つまり,どんなにエントリーが増えても検索の速さは変わらない,ということ。データ構造の教科書には必ず載っていることだね。 でも実際には,ハッシュの衝突が起こった場合に,速度の低下が発生する可能性がある。例えば,一般的なチェイン法(オープンハッシュ)だと,衝突したエントリーに関して線形検索を行うことになるから,衝突が多ければ多いほど,定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing (カッコウ・ハッシング)は仕組みが面白い。こいつは,エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では,2つのハッシュ関数と,2つのテーブルを用いる。ここでは,2つのハッシュ関数をそれぞれ h1, h2 として,2つのテー
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
A fast and simple algorithm for approximate string matching/retrieval SimString is a simple library for fast approximate string retrieval. Approximate string retrieval finds strings in a database whose similarity with a query string is no smaller than a threshold. Finding not only identical but similar strings, approximate string retrieval has various applications including spelling correction, fl
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
天方です。 今日からモテるアルゴリズム講座を始めたいと思います。 それでは、第1回グラフでモテたいの講義を始めようと思います。 なんといってもアルゴリズムができるとかいうと、いろいろモテます。 この講座を通じて、皆さんもアルゴリズムをマスターしてモテてください。 本日は、モテるアルゴリズムを考える上で重要な グラフのデータ構造について話をしたいと思います。 グラフというと、普通思い浮かべるのは棒グラフとか円グラフとかかもしれませんが、今回は違います。そんな反応をしていると婚期を逃します。 グラフというのは、点と枝かつながってできるものをグラフと言います。 グラフの例 グラフはいろいろな分野で使われていると思いますが、 あのGoogleも検索エンジンのページの順位付けのためにグラフの概念を利用していたいりします。 さて、グラフをコンピュータ上で扱おうとすると、そのデータ構造の持たせ
実績紹介 採用情報 ニュース 研究室 ブログ ギャラリー OSAKA 〒556-0011 大阪市浪速区難波中2-10-70 パークスタワー28F TEL : 06-6641-5710 FAX : 06-6641-5711
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
Structure Synth is a cross-platform application for generating 3D structures by specifying a design grammar. Even simple systems may generate surprising and complex structures. The design grammar approach was originally devised by Chris Coyne (for a 2D implementation see the popular Context Free Art). Features: Graphical environment with multiple tabs and OpenGL preview Integration with third-part
目次 はじめに 解析結果についての解説 ファイナルファンタジーIV ファイナルファンタジーV ファイナルファンタジーVI ドラゴンクエストV ドラゴンクエストVI ドラゴンクエストI・II ドラゴンクエストIII ロマンシング サ・ガ2 ロマンシング サ・ガ3 技術資料 ファイナルファンタジーIV ファイナルファンタジーV ファイナルファンタジーVI ドラゴンクエストV ドラゴンクエストVI ドラゴンクエストI・II ドラゴンクエストIII ロマンシング サ・ガ2 ロマンシング サ・ガ3 今後の予定 おわりに はじめに ゲームの内部で起こっている処理を推測するのはなかなか難しいものです。ユーザーサイドから見れば、ゲームの内部処理はほとんど「ブラックボックス」のようなものです。ユーザーサイドでは「(内部で複雑な処理が行われた末の)最終結果」しかわかりませんし、ゲーム中の様々な要素(各種パラメ
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
Cell_雀 不定期コラム 第三十二弾! 麻雀ゲームは数字の並び替え 毎度ーっ! 今年もあとわずかになりましたね。 月日がたつのはホントに早いものです♪ Cell_雀、新バージョンのver2.70で思考ルーチンの「劇的」強化をはかりました。 新しいCell_雀、お楽しみいただいておりますでしょーか? 麻雀のプログラミングは楽しいです。 メインのロジックさえ組んでしまえば思考ルーチンの強化は全く別のところで行なえますから、実に保守性がいい! ver2.70よりCell_雀のソースコードも併せて公開しております。 たくさんの方から、 「ソースコードが見たい!」 とご要望いただきました。 そんなにニーズがあるのか…とちょっと感動し、お粗末なコードながらも公開させていただいた次第です(汗)。 中をご覧いただくと大体わかると思うんですが…、麻雀ゲームのプログラミングは雀牌を数字に置き換えるところから
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く