1900-01-03 ショートコーディング理論(C/C++編)
■ショートコーディング理論(C/C++編) 
ようやくショートコーディングという言葉も定着し、たった一つのコードを厳しく、また情熱的に向き合う姿勢を持ったプログラマーが増えた事を喜ばしく思います。ショートコーディングを通じて得られた経験と、多くのトップコーダー達の天才的なアイデアをここに記します。
- ショートコーディングとは
「コードを短く書く」という遊びは、最近始まったことではありません。海外では、“コードを短く書く”==“少ないキーストローク”ということから、スポーツのゴルフにたとえて○○ゴルフ(○○の部分に言語名が入る)と言い、現在はPerl Golf, Python Golf, 複数のスクリプト言語に対応したCode Golfが有名です。
日本国内でも、7行プログラミングという(79文字＋改行コード)×7行内で様々なプログラムを書く伝統的な遊びがあります。しかし、約560文字という長さでのコーディングは、ある程度の規模のプログラムが書けますが、短さを追求するにはあまりに緩い文字制限なのです。また、7行プログラミングには厳格なルールがなく、あくまで“ちょっとした遊び”の域を超えるものではありません。
ショートコーディングとは、データ構造・アルゴリズム・処理系の3つを極限まで追及し、「限られた環境の中作動するコードの中で、最短のものを目指す」ことです。“仕様”ではこうなっているから、良い・悪いではなく、現実的に動くコード。短いコードを書くためのデータ構造とアルゴリズムを熟考し、時には処理系を欺いてでも、短くなるコードを書くため、たった1バイトを短縮するために、あえてメモリ破壊を犯すようなコードでも書く。その繰り返しが、ショートコーディングなのです。
- ルールを決める
コード短縮を極限まで追い求めるには、厳格なルールがなければなければなりません。ショートコーダー達が、共通の条件で、共通の問題を考える事によって、最短のコードは実現されます。我々は、厳格なルールとして北京大学に設置されている"PKU Judge Online"(http://acm.pku.edu.cn/JudgeOnline/)という、我々がソースコードを提出するとコンパイル、実行、正否・性能判定を行ってくれる、優れたシステムです。厳格なルールとは、我々の手が届くことのない、絶対的な評価システムのことです。仮にシステムが誤った評価をしようとも、我々にとってはそれが共通の条件・問題であり、ショートコーディングのルールは保たれるのです。
- 倫理的なルール
しかしながら、このようなオンラインの評価システムには必ずセキュリティホールが存在します。もし、悪意を持ってシステムを攻撃しようものなら、我々の手が届かないはずのシステムに踏み込んでしまうことになるでしょう。そうなってしまうと、ショートコーディングに必要不可欠な“厳格なルール”失われる事になってしまうのです。ショートコーダーは、システムのセキュリティホールを発見した場合、ルールが失われる事を防ぐため、システム管理者にセキュリティーホールの報告と、可能な限り対策案を提示しなければなりません。
- 協力
ショートコーディング理論は、たくさんのショートコーダーたちの知恵と努力の結晶です。僭越ではありますが、協力者の方々の名前と共に感謝の意を表したいと思います。
(とりあえず名前だけですが、少しずつ紹介文を追加する予定です。)
ロベールさん(id:Robe)
kurimuraさん(id:kurimura)
RiSKさん(id:RiSK)
やねうらおさん(id:yaneurao)
木下菫さん(id:O-saka)
hinoeさん
wajさん
k.inabaさん(http://www.kmonos.net/)
shinhさん(id:shinichiro_h)
tanakhさん(id:tanakh)
namasuteさん(id:namasute0)
菊さん(id:kikx)
letterさん(id:letter)
kosakさん(id:kosak)
ushiodaさん(id:ushioda)
nuさん
colunさん(id:colun)
majia001さん(http://hi.baidu.com/lfj_2)
- データ構造とアルゴリズム
ショートコーディングにおいて、データ構造とアルゴリズムに関する一般的な知識だけでは不十分です。一般的な知識をベースとして、各問題ごとに自身が常に最適化を行うのです。最短のコードが実現するデータ構造とアルゴリズムは、最速・省メモリコードのそれと同じ場合もありますし、そうでない場合もあります。ショートコーダーは常に複数のデータ構造とアルゴリズムを想定し、一つの結果だけで満足しないよう心掛けるべきでしょう。
一つ一つの問題に対して熟慮し、多くのショートコーダーと競い合った成果の一部を
http://4dm.tortoise.ne.jp/ShortCoding/index.php
に記録しています。ショートコーディングというものを具体的に見てみたいという方は御一読されるのが良いでしょう。
- 処理系と一般的なコード短縮技法
処理系については、PKU Judge Onlineにアクセスすれば、ある程度の情報が得られます。処理系を詳しく調査する事で、ショートコーディングについての一般的な知識と技法を学ぶ事が可能です。以下、私Ozyが多くのショートコーダーの強力を得て調査・研究した成果を記録します。
- for文とmain関数再帰
単純なコード、例えば標準入力から整数を読み込んでそれを出力するというコードを書いた場合、このようにforループの方が1B少なくて済みます。
main(n){for(;~scanf("%d",&n);)printf("%d\n",n);}
main(n){~scanf("%d",&n)&&main(printf("%d\n",n));}
main再帰の方が短くなるパターンも書き表すことができればCのショートコーディングを体系化していくヒントにもなるし、これまでmain再帰で達成した最短コードの正当性も主張できるはず。というわけで、この問題について考えてみました。
- マクロは使えるか
C/C++のプログラミングにおいて、マクロは使い方次第で強力な武器になりますが現代のプログラミングにおいては推奨されないものです。ショートコーディングを通して、マクロについてよく考えてみましょう。
第5回 while文の可能性(D) 標準ライブラリのマクロ利用
まだ途中(｀ω´)
