ICFPC 2011 - d.y.d.
22:15 11/06/27 ICFPC 2011 ここ 8 年くらいほぼ毎年参加していた ICFP Programming Contest ですが、今年は出題者側に回ってみました。 問題の原型決定の議論、画像に変なネタを仕込む、Windows版バイナリのビルドをする、対戦サーバの中身を突貫でどうにかする、 などなどをしていました。 ゲームのバランス調整が非常によくできていたとの評価を頂いているのですが、 肝心のその辺りは、出題チーム内の熟練者達の高度な議論に既についていけなくなっており、 私は全然貢献できていないという…。 詳しいことは 9 月の ICFP で発表があると思いますので、ここでは今年のテーマの紹介だけ。 公式の問題文はこちら です。 一言でいうと、関数を呪文に変えて撃ち合う、プログラミング魔法バトル。 Lambda: the Gathering L:tG という２人対戦ゲー
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash
CityHash, a family of hash functions for strings. Introduction ============ CityHash provides hash functions for strings. The functions mix the input bits thoroughly but are not suitable for cryptography. See "Hash Quality," below, for details on how CityHash was tested and so on. We provide reference implementations in C++, with a friendly MIT license. CityHash32() returns a 32-bit hash. CityHash
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
重なる気持ち -台形補正- | _level0 - KAYAC Front Engineer Blog
どもはじめまして、タローです。 flashとの出会いから早1年、flash好きが昂じてそのまま入社して2月目に入ろうとしている、2009新卒の新入社員です。 先輩のやっているコンテンツで計算のお手伝いをしたことがあったので、今回は座標変換のお話について少ししようと思います。四角形と四角形がぴったり重なりあいたいという気持ちをどう説明するか、ということで「アフィン変換」と「射影変換」のお話をします。図やサンプルもつけてみましたので是非ご覧下さい。 アフィン変換って？ 詳しくは、livedocsのMatrixのところにある図のような変換が出来て、任意の平行四辺形から任意の平行四辺形への変換が可能です。つまり、平行な直線が平行な直線に移るような変換です。
よくあるコーディングパターンと LINQ to Objects の対応付け - 予定は未定Blog版
あると便利ですよね、ということで書いてみた。 よくあるコーディングパターンには yield とか使ってないです。 こっちの方がよくありそうでしょ？ Select 全ての要素に何らかの処理を行いたいときに使用します。 // よくあるコーディングパターンその1 // 全ての要素を2倍するメソッド public IEnumerable<int> DoubleAll(int[] target) { var result = new int[target.Length]; for (int i = 0; i < target.Length; i++) { result[i] = target[i] * 2; } return result; } // Selectで書き直し public IEnumerable<int> DoubleAll(IEnumerable<int> target) { re
Story of Your Life » Blog Archive » Expression Templateの蛇足的な話
Preface 前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。 で、そっちを説明しようと思ったんですが、やっぱり気が変わって、式テンプレート自体の自分なりの理解を簡単に説明したいと思います。 ちなみに式テンプレートのちゃんとした入門は、参考URLの方で錚々たる方々が素晴らしい記事を書いているので、そちらを参考にしてください。この記事はまぁ、蛇足的な、自己満足のためのものです。 Introduction 式テンプレートは、最初、行列やベクトルを使った科学計算の効率化のために考案されました。 例えば以下のようにVectorクラスの演算を行うとします。 Vector v_result, v1, v2, v3; v
L'eclat des jours(2011-01-20)
_ カンマ区切りの作成 今、文字列の配列 array = { "a", "b", "c" ... "z" }があって、ここから、"a, b, c, ..., y, z"というカンマ区切りの文字列を作るとする。 C#なら、何も考えなくとも、string.Join(", ", array);で出来てしまうが、Javaには今のところそういうメソッドはStringにもArraysにもない。この2つになければきっとないだろうと思う。 C#だって、zipしながらじゃできないのではなかろうか。と思ってSystem.Arrayクラスを眺めていたらAsReadOnlyっていう便利なやつがあるんだな。気付かなかった。後で試してみよう。 で、最近はString#+が賢くなったので、StringBufferとかStringBuilderとかをあまり使わないような気がするのだが、カンマ結合のときは、非常に便利なので
【コラム】攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | エンタープライズ | マイコミジャーナル
各種文字列検索アルゴリズムを実装したStringSearch Johann Burkard氏が公開しているStringSearchは、高速な文字列検索アルゴリズムを実装したJava用ライブラリである。BNDM法や、BMH法とその派生、Bit-parallel手法といった複数のアルゴリズムをサポートしている点が特徴。いずれのアルゴリズムを利用する場合でも基本的な使い方は共通しているため、用途によって簡単に使い分けることができる。 Burkard氏によれば、StringSearchを利用すればjava.lang.Stringクラスによる文字列検索に比べて5倍から10倍程度の高速化が可能とのことである。ただし、この主張には異論も出ている。また、String.indexOf()メソッドなどで採用されているというnaiveアルゴリズム(シンプルだが低速)にしても、短い文字列を対象とした検索であれば十
LockfreeListについて - くまメモ
ロック無しで複数のスレッドから同時に操作できるLockfreeListについて資料を作りました。 この考え方をベースにLockfreeHashmapやLockfreeSkiplistなどが発展していくため、大事なアルゴリズムです。 パラパラめくるだけでも流れがわかりやすいよう配慮したつもりですがいかがでしょうか？ Lockfree listView more presentations from Kumazaki Hiroki. ABA問題やGCに付いても少し言及しています。 Cでのソースコードは完成し次第追記します。
ハザードポインタ版Lock-Free List - yamasaのネタ帳
前回の記事で時間切れのために書ききれなかった Lock-Free List について、サンプルコードをgithubに上げました。 GitHub - yamasa/lockfree: Experimental implementations of lock-free algorithms, using hazard pointers and tagged pointers. sortedlistmap.h がそれです。わかりやすくするため、Allocator対応などの細かい機能については省いています。決して手抜きではありません。;-) Lock-Free List のアルゴリズムについてはkumagiさんの解説記事が非常にわかりやすいので、そちらをご覧ください。
Android用Firewall·DroidWall MOONGIFT
DroidWallはAndroid用のオープンソース・ソフトウェア。Androidの自由度はiOSに比べるととても広い。開発者にとってはその自由さが魅力ではあるが、利用ユーザにとってはサードパーティーが触れるデータが多いためにちょっと怖い部分もあるだろう。 アプリが一覧表示される ローカルでしか動かないはずのアプリが実はネットワークを使っていた、なんて言うと何かのデータを引き出しているのかも知れないと勘ぐってしまう。そのために使ってみたいのがDroidWall、Android用のファイアウォールだ。 DroidWallの動作原理としてはWindows標準のファイアウォールに近い。ホワイトリスト方式であり、アプリケーションごとに3GまたはWiFiを使って良いかどうかを設定する。つまりWiFiは良くとも3Gは拒否といった具合に細かく設定することもできるのだ。 メニュー ローカルデータのみ使うゲ
昆布じゃないのよ
目次 ホーム 連絡をする RSS Login Blog 利用状況 投稿数 - 1078 記事 - 2 コメント - 27236 トラックバック - 363 ニュース 著作とお薦めの品々は 著作とお薦めの品々は 東方熱帯林へ。 わんくま 東京勉強会#2 C++/CLI カクテル・レシピ 東京勉強会#3 template vs. generics 大阪勉強会#6 C++むかしばなし 東京勉強会#7 C++むかしばなし 東京勉強会#8 STL/CLRによるGeneric Programming TechEd 2007 @YOKOHAMA C++・C++/CLI・C# 適材適所 東京勉強会#14 Making of BOF 東京勉強会#15 状態遷移 名古屋勉強会#2 WinUnit - お気楽お手軽UnitTest CodeZine Cで実現する「ぷちオブジェクト指向」 CUnitによるテスト駆
正規表現しちへんげ！ 第二夜
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト５（順不同）： 『
Stories of Your Life and Others » Blog Archive » C++で文字列のsplit
つい最近、C++の文字列splitが必要な場面がありました。 いい加減C++のsplitを毎回書くのが面倒になってきましたので、忘れないようにメモっておきたいと思います。 C++でsplitを書く方法はいくらでも方法があると思いますが、代表的な実装例をあげてみます。 boostが使える環境であれば一番最初の選択肢としてboostのstring algorithmを利用した方が車輪の再発明をしなくて済むかと思います。 ただ、競技プログラミングなどでは残念ながら利用できません。 find_first_ofを利用する方法 vector<string> split(const string &str, char delim){ vector<string> res; size_t current = 0, found; while((found = str.find_first_of
Efficient substring searching
There are many times when programmers need to search for a substring, for example when parsing text. This is commonly referred to as searching for a needle (substring) in a haystack (the string to search in). The most straightforward way to do this is by using search functions that your language provides: C: strchr()/memchr(), strstr()/memmem() C++: string::find() Ruby: String#index or regular exp
Android NDK で .so ではなく、実行ファイルをつくる - Hacking My Way 〜 itogのhack日記
AndroidにはNDKという、JavaではなくネイティブのC/C++で開発するためのツールチェインが用意されていて、これを使えばパフォーマンスアップを望めたり、C/C++で書かれた資産を流用出来たりします。 こういった使い方をする場合は、ネイティブのコードをコンパイルして.soをつくり、それをJavaからloadLibrary()でロードする、という使い方をするのですが、.soではなく、実行ファイル形式もつくることが出来ます。 やり方は至って簡単で、Android.mkに以下を追記するだけです(※NDK r4) include $(BUILD_EXECUTABLE) サンプル hello-exe.c #include int main(int argc, char ** argv) { printf("Hello, world!\n"); return 0; } Android.mk L
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
コードサイズと実行速度の関係に関する話 - melancholic afternoon
マルチコア時代のLock-free入門
Common CRC parameters