最強最速アルゴリズマー養成講座：あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 はじめに はじめまして。高橋直大です。本連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。 なお、本稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問
セガが取り組んだ「ゲーム開発のプロセス改善策」
家庭用ゲーム機の劇的な進化がゲーム開発をより困難にしている？ 1983年に任天堂の「ファミリーコンピュータ」が登場し、社会現象を巻き起こしてから約26年。家庭用ゲーム機は飛躍的に進化を遂げ、現在の最新機であるソニーの「プレイステーション 3」（以下、PS3）、マイクロソフトの「Xbox 360」などでは、CGを駆使してまるで実写のようなリアルな映像が楽しめるゲームタイトルが次々と生み出されている。 こうした家庭用ゲーム機の進化に伴い、ゲームソフトの開発を手掛けるメーカーにとっては「より高品質なゲームタイトルを、より短納期に開発する」ことが求められるようになった。そのため、その開発プロジェクトも従来とは比べものにならないくらい規模が大きくなった。これが「開発工数とプログラムコード行数の増大によるバグの大量発生」など、さまざまな問題を引き起こしており、ゲーム業界全体の重大な課題となっている。
プログラミング言語の特徴を視覚的に比較する - Radium Software
The Computer Language Benchmarks Game のページでは，計 32 個のプログラミング言語処理系のベンチマークを集計して，そのパフォーマンスを比較している。そして最近，このページに新たなプロットが追加された。単純にパフォーマンスだけの比較を行うのではなく，パフォーマンスと「コードの長さ」を関連付けて比較を行うというものだ。上はそのプロットから一部を転載したもので，全体はこのページで見ることができる。 このプロットでは，縦軸が処理時間（上にいくほど遅い），横軸がコードの長さ（右にいくほど冗長）に割り当てられている。このようなプロットを行うと，多くの言語は３通りの偏り方を見せる ― 左上（簡潔だけど遅い）に偏る「スクリプト系」，右下（速いけど冗長）に偏る「システム系」，そして，左下（速くて簡潔！）に偏る「理想系」だ。ちなみに，右上（遅くて冗長）に偏る言語は無い…
続・バグを生まないコーディング法 | EE Times Japan
フォーラムでの議論は次のような発言から始まった。 「中括弧を使って複合文を記述し、文の切れ目にセミコロン「;」を使う言語では、オールマン・スタイルを使うべきではない」 私はどちらのスタイルでもよいと思っているが、「1TBSでは図2のような間違いを人間のコード・レビュワーが発見しにくい」という1TBSに対する批判は受け入れがたい。 人間のコード・レビュワーが、このような間違いを見落とす可能性があることは認める。しかし、まさにこの例は、ここで紹介するようなコーディング規則の重要性を物語っている。つまり、「バグを効果的に排除するためには、コーディング規則に強制力がなければならない。2個以上の競合する規則がそれぞれバグを防げても、それらの中の1つの規則だけが自動的に強制できる場合は、より強制力がある規則の適用が推奨される」ということだ。 われわれのコーディング規則では、上記のような例はまさに自動
『パターン、Wiki、XP - 時を超えた創造の原則』感想、少しばかりの余談 - Kentaro Kuribayashi's blog
江渡浩一郎氏(id:eto)による『パターン、Wiki、XP - 時を超えた創造の原則』を読みました。プログラミングに関わる者ならば誰もが知っているだろう「デザインパターン」という言葉が、クリストファー・アレグザンダーの建築理論に由来することは、少しでもそのあたりの事情に通じている方ならば、聞いたことぐらいはあるでしょう。本書は、長年Wikiについて深く考察し、また実装を行ってきた著者が、建築に端を発した思想が現在の創造性のある大きな一角を胚胎した歴史についてついに一書を成したものであり、楽しみに読みました。 パターン、Wiki、XP ~時を超えた創造の原則 (WEB+DB PRESS plusシリーズ) 作者: 江渡浩一郎出版社/メーカー: 技術評論社発売日: 2009/07/10メディア: 単行本（ソフトカバー）購入: 75人 クリック: 1,306回この商品を含むブログ (152件)
kur.jp - 身も蓋もないが本当に有効な「コードの書き方」
インターネットをぶらぶらしていたら，こんなエントリを見つけました． 身も蓋もないが本当に有効な「企画書の書き方」 身も蓋もないが本当に有効な「論文の書き方」 こういうことって良いプログラムを書くために大事なことに通じるような気がするので私も真似して書いてみます． 前例を重視する アルゴリズムについて 完成品としてのソフトウェアの機能には独自性を求められますが，その機能を実現するためのアルゴリズムには独自性を求められません． むしろ、独自性が高く前例にしたがっていないプログラムはダメなプログラムであるとみなされる傾向にあります． たとえば，暗号を独自実装しましたとか，ソートに独自アルゴリズムを実装しましたとか，自慢気に話してくれる人がよく居るのですが，セキュリティを重視したいなら用途に応じてAESとかRSAとかを素直に使ってくれたほうが安全なのは明らかだし，ソートにしたって，素直にクイックソ
納期が迫ってるプロジェクトにおけるOJTの効果って？ - smellman's Broken Diary
今のプロジェクトでは新人がOJTとしてプログラムの一部を組んでいます。 これは良くある話なんですが、気になる点が一つ。納期近すぎじゃね？ 新人とはいいつつも、一人は学校でJavaやってましたよ(おっと、Javaスクールの話をする訳じゃないですよ)と前に本人から直接聞いていたので、たぶんそこから即戦力として投入されているのかもしれない。 ただ、納期が近いプロジェクトに投入されていて余裕があるのかなというのが疑問点。だって、毎日9時とか今日なんて10時まで残って仕事をしているんですよ。新人がやるべき事なんでしょうか？ 別に新人だから甘やかすべきとかそういう話ではなくて、彼等に学習する余裕ってあるんでしょうか？一年目というのは多くの事を吸収する大事な時期のはずなのに、本当に学んでいるのでしょうか？ 実際今日帰りに一緒だった同じプロジェクトの新人に聞いてみたら、日々の業務をこなす事に精一杯で何をや
Fine Software Writings
最近のもの 目標でなく恐怖を明確にすべき理由 (Tim Ferriss) 我々が築き、掘っている未来 (Elon Musk) 表計算ソフト誕生の話 (Dan Bricklin) Linuxの背後にある精神 (Linus Torvalds) 先延ばし魔の頭の中はどうなっているか (Tim Urban) 好きになる仕事はどうしたら見つかるのか (Scott Dinsmore) 人間に新たな感覚を作り出すことは可能か？ (David Eagleman) 人工知能が人間より高い知性を持つようになったとき何が起きるか？ (Nick Bostrom) 厄介な問題を解決したい？ ではトーストの作り方を説明してください (Tom Wujec) 子供の夢を奪う学校というシステム (Seth Godin) 彼らがいなくなってしまう前に (Jimmy Nelson) 頭良さそうにTED風プレゼンをする方法 (W
いいアジャイルと悪いアジャイル
スクラムはラグビーにおいて最も危険な段階であり、それというのも、潰れたり不適切なかみ合い方をすると、前列のプレーヤーが怪我をしたり、首の骨を折る危険すらあるからだ。—Wikipedia 私が子供の頃には、コレステロールは体に悪いものだった。これは覚えやすかった。脂肪は悪い。コレステロールは悪い。塩分は悪い。みんな悪い。しかし近頃では、コレステロールが「いい」コレステロールと「悪い」コレステロールに分かれている。私たちがこの2つをどうにかして見分けられるとでもいうように。そしてその切り替わりは奇妙なものだった。FDAが突然プレスリリースを発表して、殺鼠剤には2種類、いい殺鼠剤と悪い殺鼠剤があり、いい方はたくさん摂って悪い方は摂ってはならず、そして決して2つを混ぜたりしてはいけないのだと言ったかのようだった。 一年くらい前まで、私はいわゆる「アジャイル」プログラミングに対して、ごく一次元的な見
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
システム開発の入門者から中級者にステップアップするための10のティップス - builder by ZDNet Japan
ある読者との電子メールのやり取りの中で出てきた話である。彼は、開発者向けのブログや記事、雑誌の内容が2種類に分類できるということを述べていた。その2種類とは入門者向けのもの（"Hello World"に代表されるもの）とエキスパート向けのもの（MSDN Magazineのようなもの）である。 これはなかなか鋭いポイントを突いている。開発者が入門レベルから中級レベルにステップアップするうえで役立てることのできる情報がほとんどないのだ。以下は、こういったステップアップを実現するための10のティップスである。 ＃1：新たなプログラミング言語を学習する 新たなプログラミング言語を学習することは、それがどのような言語であったとしても、より優れた開発者になるための近道となるのである（このことは、あなたが既に多くのプログラミング言語を修得していたとしても成立することである）。言語を選択する際には、あなた
JavaScript正規表現メモ。 (JavaScriptでよく使う書き方。) - こせきの技術日記
タイトル変えました。旧タイトル「JavaScriptでよく使う書き方」。よく使うけど毎回忘れる。 正規表現にマッチするかどうか。 RegExp#testを使う。 /abc/.test("abcdefg") // => true String#searchはマッチした位置を返す。マッチしない場合は-1。先頭にマッチすると0でfalseなので注意。真偽値が欲しい場合はString#searchを使わない。 "abcdefg".search(/xxx/) // => -1 "abcdefg".search(/def/) // => 3 "abcdefg".search(/abc/) == false // => true 正規表現の部分マッチを得る。 部分マッチを得るには、RegExp#execかString#matchを使う。execとmatchの速度は大して変わらない。 正規表現のベンチマー
MeCabの辞書にはてなキーワードを追加しよう - 不可視点
MeCabは形態素解析のためのソフトウェアです。日本語を分かち書きするために使われるものとしては最も人気の高いものだと思われますが、チャットや掲示板に書き込まれるような崩した日本語や、正しく書かれた日本語でも新語を期待した通りに分かち書きしてくれないことがあります。これはMeCabの内部で使われている辞書が一般的な言葉を情報源としているわけではないことに関係があります。MeCabというか、より一般的な話ですが以下のような認識が一般的かと思われます。 というのも、一番広く使われているであろう自然言語処理技術は形態素解析(単語分かち書き、と言ったほうがいいのかもしれない)であろうが、これは現在99%くらいの精度になっていて、すでに人間がやるより遙かに高精度で行えるのだが、これだけ高い精度が出せるのは新聞記事を相手にしたときだけであって、それは新聞記事をコーパスとして用いる機械学習により形態素解
PHP: Manual Quick Reference
Getting Started Introduction A simple tutorial Language Reference Basic syntax Types Variables Constants Expressions Operators Control Structures Functions Classes and Objects Namespaces Enumerations Errors Exceptions Fibers Generators Attributes References Explained Predefined Variables Predefined Exceptions Predefined Interfaces and Classes Predefined Attributes Context options and parameters Su
オブジェクト指向っぽい話が分かるかもしれないJavaScript講座 その1 | Takazudo Clipping*
自分はスーパーJavaScripterでこんなすげーのが5行で書けちゃう。やばいだろ！とかいうのでは全然無いですが、オブジェクト指向っぽい話が最近分かってきたつもりで、それでやっときゃ問題無いってことを思い始めているので、なんかそんな話を書いていきます。 こんな短く書くテクニックがあるぜ！ var hoge = hage ? huga : hoga; とか書けちゃうんだぜ！とかより、長くていいから分かりやすく拡張しやすいようにするにはどうするのかとか、そういう話ができればなーと思います。内容的には全くもって新しくも何とも無いですが。jQuery使ってやる前提です。 まんじゅう製造スクリプト 今日はまんじゅうを5個作ります。なんと、まんじゅうは、クリックすると隠れます。 まんじゅうサンプル var Manju = function(){ this.elem; this.hidden = fa
データベースの動的デフラグ - mixi engineer blog
ノートPCの冷却ファンがうるさいのを対処しようとしてWebで調べたら、そのファンの設計者が「静音性へのこだわり」を語ったページにたどり着いて複雑な心境のmikioです。今回は、Tokyo Cabinet（TC）の最新バージョンで実装された動的デフラグ機能について長々と説明します。 断片化とデフラグ 任意のサイズのデータを管理する記憶装置においては、利用可能領域の断片化（fragmentation）の問題が常につきまといます。ファイルシステム上で任意のサイズのファイルを管理する際にも、データベースファイル内で任意のサイズのレコードを管理する際にも、C言語のmalloc/free関数群でメモリの管理をする際にも、様々なレイヤで断片化が起きうるのです。なぜなら、データを削除もしくは移動した際の空き領域を再利用するにあたって、その領域と同じサイズのデータが常に入ってくるとは限らないからです。特にデ
きれいなソースコードを書くために必要な、たったひとつの単純な事 - よくわかりません
「構造のきれいなプログラムを書けるようになるためにはどうすればいいのか？」という質問を受けたので、「はて？どうしているだろうか？」と考えてみました。あ、形式知にきちんとなっているようなテクニックみたいなもんじゃなくて、モノローグなので、あまり凝ったものは期待しないように。 http://blog.shibu.jp/article/28983162.html 自分なりにもっと凝縮版を。渋川さんが言っている事全体もその通りとは思うけど*1、もっと簡単で、しかも射程が広い、と自分が思っている事。 渋川さんはちょろっと触れてるだけだけど、自分はこれが最も基本的で汎用的、かつ、ソースをきれいにする原動力となる上にバグをも減らしてコードの汎用性まであげる、コーディングのエンジンみたいなものと思ってる。それは、 「すべてに正しい名前を付けて、そして、正しい名前であることを維持する」という鉄の意志 クラス
Shibu's Diary: きれいなソースコードを書けるようになるためには
渋日記@shibu.jp 渋川よしきの日記です。ソフトウェア開発とか、ライフハックを中心に記事を書いていきます。 by chazmatazz 「構造のきれいなプログラムを書けるようになるためにはどうすればいいのか？」という質問を受けたので、「はて？どうしているだろうか？」と考えてみました。あ、形式知にきちんとなっているようなテクニックみたいなもんじゃなくて、モノローグなので、あまり凝ったものは期待しないように。あ、Pythonに限定してますが、他の言語でも似たようなものはあると思いますので、脳内変換をお願いします。 事前の設計はしません 「こういう処理が必要」「こういう計算しなきゃね」みたいなロジックや「要件はこうかな？」ということは事前に考えたりするけど、クラス構造とかは基本的に考えないで手をつけます。そして、ある程度規模が大きくなって「あ、ちょっとこの関数大きすぎて理解しにくいなぁ」と
Manpage of SCREEN
Section: User Commands (1) Updated: Aug 2003 Index JM Home Page roff page 名前 screen - VT100/ANSI 端末エミュレーション機能を持つ画面管理ソフトウェア 書式 screen [ -options ] [ cmd [ args ] ] screen -r [[pid.]tty[.host]] screen -r sessionowner/[[pid.]tty[.host]] 書式 screen は、ひとつの物理的な端末を複数のプロセス (特に対話シェル) で共有化できるようにする、フルスクリーンウィンドウ管理ソフトウェアである。 各仮想端末は DEC VT100 端末の機能に加え、ANSI X3.64 (ISO 6429) や ISO 2022 規格に含まれる制御機能 (例えば行の挿入/削除や複数の文
phpを高速化する computed goto : DSAS開発者の部屋
前回 インタプリタ型言語を高速化する computed goto で紹介したcomputed gotoを、「phpでも使えないの？」という声が社内であったので、 php のソースコードを見たところ、特定のビルド手順で php でも computed goto が使えることが判りました。そのビルド手法とベンチマーク結果を紹介しておきます。 php の VM のソースコードは、phpソースパッケージ中の Zend/ というディレクトリの中にあります。zend_vm_で始まる幾つかのファイルのうち、 zend_vm_execute.h というファイルが命令ディスパッチが実装されているファイルで、このファイルは zend_vm_gen.php というスクリプトで生成されています。そして、 zend_vm_gen.php のオプションで、命令ディスパッチの方法を選択できます。(phpのビルドにphp
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
