tag:blogger.com,1999:blog-12852411283149385242024-02-08T07:05:57.795+09:00「や」の字yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.comBlogger38125tag:blogger.com,1999:blog-1285241128314938524.post-91797873299807012922019-06-02T21:54:00.001+09:002019-06-02T22:22:05.611+09:00[C++][Google CodeJam] C++20 rangeでGCJ2019 R2-Aを解く<p>5年空いた更新でのっけから言い訳で始まりますが、C++20どころかC++14から周回遅れ状態で突っ込みどころが多々あるかと思いますがそれ相応にお願いします。</p>
<p>さて2008年以降毎年参加しているGoogle CodeJamですが、最新のC++で頑張る(特に時間に余裕のあるQualification Roundでは)という裏目的は2018年にコンテストシステムがローカル実行からリモート実行へ変更されて以降難しくなってしまいました(2019年ではgcc-6.3.0で-std=c++14になっています)。ということでC++欲が高まっているところにGCJ R2-Aが割ときれいに書けた&<a href="https://github.com/CaseyCarter/cmcstl2">cmcstl2</a>を見つけた(遅い)ということでC++20 rangeで書いてみたものです。</p>
<p>該当の問題は<a href="https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/0000000000146183">New Elements: Part 1</a>。実装した解法はanalysisに書いてあるのと同じだと思います。競技時間中に書いていたものをC++20 rangeを使って書き直したものが↓でwandboxによる実行結果が<a href="https://wandbox.org/permlink/9xaBBQOpCvVBqds9">これ</a>です。</p>
<pre class="brush: cpp">#include "cmcstl2/include/meta/meta_fwd.hpp" // force to use meta in cmcstl2
#include "cmcstl2/include/meta/meta.hpp" // same as above
#include <experimental/ranges/ranges>
#include <experimental/ranges/iterator>
#include <experimental/ranges/algorithm>
#include <vector>
#include <set>
#include <iostream>
#include <utility>
#include <cstdint>
namespace ranges = std::experimental::ranges;
// for ADL for operator>>
struct vec2 : std::pair<int,int> { using std::pair<int,int>::pair; };
inline std::istream& operator>>(std::istream& is, vec2& p) { return is >> p.first >> p.second; }
inline constexpr vec2 operator-(const vec2 &v1, const vec2 &v2) { return { v1.first - v2.first, v1.second - v2.second }; }
inline constexpr vec2 operator-(const vec2 &v1) { return { -v1.first, -v1.second }; }
inline constexpr auto ratio_less = [](const std::pair<int,int> &v1, const std::pair<int,int> &v2){
return static_cast<std::int64_t>(v1.second) * v2.first > static_cast<std::int64_t>(v1.first) * v2.second;
};
// from http://ericniebler.com/2018/12/05/standard-ranges/
inline constexpr auto for_each = [] <ranges::Range R, ranges::Iterator I = ranges::iterator_t<R>, ranges::IndirectUnaryInvocable<I> Fun>
(R&& r, Fun fun) /* requires ranges::Range<ranges::indirect_result_t<Fun, I>> */ {
return std::forward<R>(r) | ranges::view::transform(std::move(fun)) | ranges::view::join;
};
inline constexpr auto all_pairs = [](int N) {
return for_each(ranges::iota_view(0, N), [=](int n){ return ranges::view::transform(ranges::iota_view(n+1, N), [=](int m){ return std::make_pair(n, m); }); });
};
inline constexpr auto all_pairs_r = [](auto &&r){
return for_each(
ranges::iota_view(ranges::begin(r), ranges::end(r)) | ranges::view::transform([e=ranges::end(r)](auto it){return ranges::subrange(it, e);}),
[](auto &&rr){
return ranges::view::transform(rr.next(), [pp1=ranges::begin(rr)](auto p2){ return std::make_pair(*pp1, p2); });
}
);
};
int main()
{
int P; std::cin >> P;
ranges::for_each(ranges::iota_view(1, P+1), [&](int p){
int N; std::cin >> N;
std::vector<vec2> v(N);
// At least, ranges::copy_n can't be used because input iterator is incremented for a result value
// see also http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2471
std::copy_n(ranges::istream_iterator<vec2>(std::cin), N, ranges::begin(v));
#if 1
auto r = all_pairs_r(v) | ranges::view::transform([](auto p){ return p.first - p.second; })
| ranges::view::filter([](auto p){ return p.first * p.second < 0; })
| ranges::view::transform([](auto p){ return p.first > 0 ? p : -p; })
| ranges::view::common;
#else
auto r = all_pairs(N) | ranges::view::transform([&v](auto p){ return v[p.first] - v[p.second]; })
| ranges::view::filter([](auto p){ return p.first * p.second < 0; })
| ranges::view::transform([](auto p){ return p.first > 0 ? p : -p; })
| ranges::view::common;
#endif
// Use deduction guide (gcc8 required for libstdc++ part)
std::set s(ranges::begin(r), ranges::end(r), ratio_less);
std::cout << "Case #" << p << ": " << s.size() + 1 << std::endl;
});
return 0;
}</pre>
<p>以下簡単な説明。</p>
<p>最初の2行とコンパイルオプション-I/opt/wandboxはwandboxだとcmcstl2内のmetaと<a href="https://github.com/ericniebler/range-v3">range-v3</a>のmetaが衝突するのでその回避用です。まず必要なヘッダを#includeして適当にnamespace aliasを作成。vec2を定義しているのはiostream用のoperator>>がADLで引っ掛けられるようにするためです(std::pairのままだとstd名前空間内にoperator>>を定義しないとADLで引っ掛けられないが<a href="https://en.cppreference.com/w/cpp/language/extending_std">未定義動作になる</a>)。using部分は<a href="https://cpprefjp.github.io/lang/cpp11/inheriting_constructors.html">inheriting constructors</a>です。このvec2に対して、iostream用operator>>、減算、単項マイナス、有理数として見た場合の比較関数(の符号手抜き版)を定義します。比較関数は32bit環境向けに64ビット変数へのキャストを入れています。</p>
<p>for_eachはRangeの神様 Eric Niebler 氏の<a href="http://ericniebler.com/2018/12/05/standard-ranges/">記事</a>からぱくってきたものです。Constraint lambdaがとてもえぐいですがシグネチャとしては明確になっていると思います(でもあまり書きたいとは思えない)。コメントアウトしてあるrequires部分はtrailing requires-clauseとしてここにかけるはずなのですがgcc-9.1.0では通りませんでした(HEADだとコンパイラが落ちる)。</p>
<p>このfor_eachを利用して、N未満の2整数の組のrangeを生成するall_pairsと、渡されたrange中の2要素の組のrangeを生成するall_pairs_rを定義しています。all_pairs_rについてはとりあえず動いてるように見えますが書いた当人がまじで動いてるのこれ?状態です。</p>
<p>最初の ranges::for_each にはあまり意味はなく、せっかくだら for なくそうというだけでしかありません。</p>
<p>最初にデータ数を読みだしてきてstd::copy_nを使ってstd::cinからvec2の列を読みだしてきます。このとき少なくともranges::copy_nだと意図通り動作しません。ranges::copy_nはstd::copy_nと違い入力側のiteratorについても処理後の値を返り値で返すのですがいわゆるone-past-endの値になっています。一方でistream_iteratorはインクリメント時に次のデータを読みだしてくるのでN個コピーするときにはN+1個読みだされた状態になってしまいます(実質1個分捨てられる)。実際にはstd::copy_nについても現状は明確な記載がなく<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2471">lwg-2471</a>がOpenになっていますが既知の実装ではN-1回インクリメントになっているようです。</p>
<p>次がメインの処理で、all_pairs起点の場合、N未満の2整数の組を生成→これを添え字としたときのvec2列の要素間の差を生成→firstとsecondの積が負になる場合(=傾きが負になる場合)のみに限定→first(分母)が正になるように正規化しています。all_pairs_r起点の場合には添え字の組ではなく最初から要素の組が生成されています。最後のranges::view::commonは次にsetのコンストラクタ(Iteratorの組を引数にとるもの)に渡すためにbeginとendが同じ型になるようにしています。これを有理数としてみた場合のsetに突っ込んで独立な傾きの数を求めて+1して終了です。setでは<a href="https://cpprefjp.github.io/lang/cpp17/type_deduction_for_class_templates.html">クラステンプレートのテンプレート引数推論</a>で型引数を省略しています。<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1206r1.pdf">ranges::to: A function to convert any range to a container</a>が入れば</p>
<pre class="brush: cpp">auto s = all_pairs_r(v) | ... | ranges::to<std::set>(ratio_less);</pre>
<p>みたいに書けるようになるかもしれません(多分)。<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1035r5.pdf">Input Range Adaptors</a>も加えて</p>
<pre class="brush: cpp">auto v = ranges::istream_view<vec2>(std::cin) | ranges::view::take(N) | ranges::to<std::vector>;</pre>
<p>とでも書けるともっといいと思いますが、copy_nの時と同じ話になってしまいます。せっかく無限Rangeが表現できるようになったので++時には入力を読まない版ができればいいのかもしれません。</p>
<p>どうでしょうか。もちろんこの処理なら普通に書いてもよっぽどシンプルですがまるでアルゴリズムの教科書に書いてあるかのごとく処理内容・意図が簡潔・明確に示されている感じがしないでしょうか。C++11以降とそれより前でC++は大きく変わっているわけですが、Conceptが入ることもありC++20はそれ以上に大きな変革になりそうです。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-38833549022672916432014-05-29T02:31:00.000+09:002014-05-29T02:34:41.876+09:00[C++] next_combination() 書いてみた<p>C++ 標準ライブラリの <algorithm> には next_permutation() という関数があります。辞書順で順列を列挙してくれる大変便利な関数で競プロ関連でお世話になったことのある人も結構いるのではないかと思います。順列があるなら組み合わせはないの?ということで next_combination() で検索をかけると nyama++ さんの <a href="http://www.programming-magic.com/20090123132035/">全ての組み合わせを作る【C++】 - Programming Magic</a> という記事が引っかかります(他の検索結果からも結構参照されているようです)。この記事のリンクで指し先が消失しているものがありますが、内容自体は <a href="http://www.open-std.org/jtc1/sc22/wg21/">ISO C++ 標準化委員会(JTC1/SC22/WG21)</a> に提案されているペーパー <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf">n2639 Algorithms for permutations and combinations, with and without repetitions</a> です(実装は Reference implementation のところ)。next_pertial_permutation() (next_permutation() が n! の列挙なら、これは <inf>n</inf>P<inf>r</inf> を列挙する) の実装が</p>
<pre class="brush: cpp">template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
{
reverse(middle, last);
return next_permutation(first , last);
}</pre>
<p>というのも私的に感動ポイントですが、next_combination() は確かに訳が分かりません。ってことで一度自分で書いてみたところ最終的にほぼ同様のアルゴリズムとなり理解が進みましたので解説記事っぽいものを書いてみようと思います。なお図としては全ての要素が1ずつ異なるようなイメージで書いていますが、値が跳んでいてもいいですし重複があっても問題ないはずです。</p>
<p>まず最初に意味不明と書かれていた prev_combination() について。処理上何かと便利なので [first, middle), [middle, last) がソートされている、という前提を置いておきます。このとき、[first, middle) に対して next_combination() した場合の例は以下のようになります。</p>
<p><img src="https://docs.google.com/drawings/d/13Kp71_kr2RgRWyTglVfKWNuOcmmZquYF21x7wPpZmHk/pub?w=303&h=330"></p>
<p>見ての通り、[middle, last) に対しては prev_combination() になっています(両方の領域がソート済み、かつ、辞書式順序で列挙なのでこうなる)。ということで先の前提の下で next_combination() が正しく実装できれば他方の領域に対して next_combination() をかけてやれば元々の領域に対する prev_combination() になります。</p>
<p>さて、では本論のコードについて。さすがに真っ白の状態だと書けないので n2639 で参考文献として挙げられている Knuth 先生の <a href="http://www.amazon.co.jp/dp/4756151299">The Art of Computer Programming. Volume 4, Fascicle 3 GeneratingAll Combinations and Partitions</a> を見ると(※立ち読み。分冊が一冊になったら買います、多分)確かに列挙アルゴリズムが記述されてはいますが添字の列挙としてのアルゴリズムであって実際に要素の並び替えを行う next_permutation() 風の next_combination() の場合だとそのままでは使えなさそうです。そうすると指針としては、汎用的な方法として挙げられている「最も右端の増加可能な要素を見つけて増加、以降の要素は設定可能な最小値を設定していく」になります。これを実装してみましょう。</p>
<p>まずは「最も右端の増加可能な要素」を見つける必要があります。右端(middle - 1)が最大値でない場合はそこが増加可能です。では右端ではない部分が「最も右端の増加可能な要素」となる場合を考えてみましょう。この時その要素(*targetとしておきます)の右側には、右端(*(middle-1))が最大値となる状態で連続して昇順に要素が並んでいることになります。さもなくば、より右側の要素が増加可能になるからです。[middle, last) もソート済であることと合わせると、*target < *(last-1) となる最も右端の target を見つければいいことになります。これが存在しない場合には列挙終了です。</p>
<p><img src="https://docs.google.com/drawings/d/1550dkcIVXe4a9-NVQXsUHsPq3wnq1lfxY73ZZygEUi8/pub?w=381&h=145"></p>
<p>次に、*target をどの値に変更すれば良いかを考えましょう。target の右側が最大値から連続で詰まっているので、[target, middle) の間の値は考慮する必要がありません(target から middle まで埋めるには要素が足りない)。ということで、[middle, last) のうちで *target より大きくなる最小値に設定すれば良いことになります(next とします)。*target < *(last-1) なので [middle, last) で必ず見つかります。</p>
<p>では、[target+1, middle) (と [next, last) をどのように埋めれば良いでしょうか? これまでの条件から [target, middle) [next, last) 近傍の順序は下図上段のようになっています。[target, middle) はできるだけ最小になるように設定すること、[middle, last) もソートされている必要があることを考えると最終結果は下図下段のようになっている必要があります。これは target と next を iter_swap した後、[target+1, middle), [next+1, last) が一つの領域だとみなして、next+1 が先頭となるように rotate() することに他なりません。</p>
<p><img src="https://docs.google.com/drawings/d/1DdO8hkcj-gRQR8Yh2Pq8B2NitOILZABZuFPm284aU9M/pub?w=509&h=577"></p>
<p>というのをコードにまとめると以下のようになります。C++er な人には言うまでもないとは思いますが、わざわざ !(a < b) みたいな書き方になってるのは operator< のみ使用にしたかったからです。なお、rotate() は en.cppreference.com の参考実装(Forward Iterator 向けですが)に分割2領域用にちょっとだけ修正したものです。</p>
<pre class="brush: cpp">// possible implementation introduced at http://en.cppreference.com/w/cpp/algorithm/rotate with slight modification to handle parted ranges
template<typename FI>
void parted_rotate(FI first1, FI last1, FI first2, FI last2)
{
if(first1 == last1 || first2 == last2) return;
FI next = first2;
while (first1 != next) {
std::iter_swap(first1++, next++);
if(first1 == last1) first1 = first2;
if (next == last2) {
next = first2;
} else if (first1 == first2) {
first2 = next;
}
}
}
template<typename BI>
bool next_combination_imp(BI first1, BI last1, BI first2, BI last2)
{
if(first1 == last1 || first2 == last2) return false;
auto target = last1; --target;
auto last_elem = last2; --last_elem;
// find right-most incrementable element: target
while(target != first1 && !(*target < *last_elem)) --target;
if(target == first1 && !(*target < *last_elem)) {
parted_rotate(first1, last1, first2, last2);
return false;
}
// find the next value to be incremented: *next
auto next = first2;
while(!(*target < *next)) ++next;
std::iter_swap(target++, next++);
parted_rotate(target, last1, next, last2);
return true;
}
// INVARIANT: is_sorted(first, mid) && is_sorted(mid, last)
template<typename BI>
inline bool next_combination(BI first, BI mid, BI last)
{
return next_combination_imp(first, mid, mid, last);
}
// INVARIANT: is_sorted(first, mid) && is_sorted(mid, last)
template<typename BI>
inline bool prev_combination(BI first, BI mid, BI last)
{
return next_combination_imp(mid, last, first, mid);
}</pre>
<p>基本的に n2639 とほぼ同じことをするコードです。nyama++ さんの記事で②③となっているところが実は合わせて rotate() だったわけです。</p>
<pre class="brush: cpp">reverse(first, mid);
reverse(mid, last);
reverse(first, last);</pre>
<p>という reverse() 3連打の rotate() 実装を 2 領域対応にした形が②③になります。後の違いは、false を返す時に先に return する(rotate() が 2 ヶ所になる)か、1ヶ所で rotate() するかくらいですね。</p>
<p>ついでなので、計算量(iter_swap の呼び出し回数)について実際に計数させてみたところ、<inf>2n</inf>C<inf>n</inf> 列挙時での 1 next_combination() 辺りの平均 iter_swap() 回数は 1.7 くらいに収束しそうな感じです。 もちろん組み合わせの数自体が指数関数的に増えるので全体的にはすぐに苦しくなるのですが、かなり悪くない数字に感じます。</p>
<pre class="brush: text">#n,r,the number of iter_swap,the number of combinations,average iter_swap per one next_combination() call
2,1,2,2,1
4,2,8,6,1.33333
6,3,30,20,1.5
8,4,112,70,1.6
10,5,414,252,1.64286
12,6,1540,924,1.66667
14,7,5754,3432,1.67657
16,8,21656,12870,1.68267
18,9,81994,48620,1.68643
20,10,312068,184756,1.68908
22,11,1192954,705432,1.6911
24,12,4577356,2704156,1.69271
26,13,17619034,10400600,1.69404
28,14,68003992,40116600,1.69516
30,15,263097002,155117520,1.69611
32,16,1019997844,601080390,1.69694
34,17,3961678122,2333606220,1.69766
36,18,15412309480,9075135300,1.6983
38,19,60046904394,35345263800,1.69887
40,20,234252753696,137846528820,1.69937</pre>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-9168706426006785152014-04-15T22:43:00.000+09:002014-04-15T22:43:50.814+09:00TopCoder Open 2014 Algorithm Round 1A<p>システム不調ということで開始できず1週延期になった TCO R1A ですが、今回は System test に問題ってことで今のところ暫定結果でしかないものの、珍しく 1A で通過できたっぽいです。大体 1C 通過なんですけどね。またテンプレからです。今回から TopCoder も C++11 使用ですが吟味が足りない感じ。提出時には適当に削ってから提出してます。</p>
<pre class="brush: cpp">#include <iomanip>
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <initializer_list>
#include <cmath>
#include <cassert>
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned int UI;
#define MP make_pair
#define RNG(v) (v).begin(), (v).end()
#define RRNG(v) (v).rbegin(), (v).rend()
struct irange {
struct irit {
int value;
operator int&() { return value; }
int operator *() { return value; }
};
irit begin() const { return { first }; }
irit end() const { return { last }; }
int first, last;
};
inline irange IR(int first, int last) { assert(first <= last); return { first, last }; }
template<typename T> struct rpq { typedef std::priority_queue<T, std::vector<T>, std::greater<T> > type; };
using namespace std;
class $CLASSNAME$ {
public: $RETURNTYPE$ $METHODNAME$($METHODPARAMS$) {
return $DUMMYRETURN$;
}
};
</pre>
<p>GCJ と基本変わりませんが、TopCoder では boost が使えないので IR() だけ似非 range クラスでごまかしています。早いところ range 標準で入ってくれないですかね……。</p>
<h4>250. EllysSortingTrimmer</h4>
<p>まず最初に問題の意味を取り違えました。複数回使えるをすっ飛ばしてコード書いて実行して例の結果見てから「ふぁ?」ってなりました。それはともかく。1回のソートで L 文字ソートできる訳ですが、結果を引き継ごうとしてずらして実行する時には最大 L-1 文字しか引き継げないわけで右から順に1つづつずらしていったら最終的には先頭文字と先頭以外で最小の L-1 文字からなる文字列のソートになります。</p>
<pre class="brush: cpp">class EllysSortingTrimmer {
public: string getMin(string S, int L) {
sort(S.begin() + 1, S.end());
sort(S.begin(), S.begin() + L);
return S.substr(0, L);
}
};
</pre>
<h4>500. EllysScrabble</h4>
<p>左側から可能な範囲内で一番小さな値を探して詰めていきますが、可能な範囲の左端に未使用の文字が残っていて次に可能な範囲から外れてしまう場合はそれ使うしかないので強制的に選択します。'~' は使用済みフラグです。string のコンストラクタの引数順序間違えたり、min_element の終端指定で +1 忘れたりしましたがまぁどうにか。結構 C++ らしいコードで書けた気がしています。</p>
<pre class="brush: cpp">class EllysScrabble {
public: string getMin(string letters, int maxDistance) {
string result(letters.size(), ' ');
for(int i : IR(0, letters.size())) {
if(i >= maxDistance && letters[i - maxDistance] != '~') {
result[i] = letters[i - maxDistance];
letters[i - maxDistance] = '~';
} else {
auto it = min_element(letters.begin() + max(0, i - maxDistance), letters.begin() + min<int>(letters.size(), i + maxDistance + 1));
result[i] = *it;
*it = '~';
}
}
return result;
}
};</pre>
<h4>1000. EllysLamps</h4>
<p>いつも 1000 出せない感じですが、Example は通ったので記念半分で提出しました。……正直に言えば、休憩時間に駄目だってのに気付くまでは結構テンション高かったです。結局 Challenge されましたがちゃんと気付くもんですね。まぁ YYYNY で駄目なので Challenge する側の方は簡単かもしれませんが。</p>
<p>実例を紙に書きながら Y が残ってしまって駄目な場合はどうなるのか考えたところ、2スイッチの場合は↓の場合だけ2スイッチが独立で変更できません(縦横転置してます)。この場合、NY か YN だとどちらか 1 つは残ってしまいます。これで Example を確認したところ最後の例だけ数字が合いません。</p>
<pre>
A|AB
B|AB
</pre>
<p>ぱっと見 YYY と連続しているところが臭そうということでここで 3 スイッチでも書き下してみたところ例えば↓なんかだとYYYで1個残ってしまいます。</p>
<pre>
A|AB
B|ABC
C| C
</pre>
<p>ということでとりあえず書いたのが以下のコードです。</p>
<pre class="brush: cpp">class EllysLamps { // 間違ってます
public: int getMin(string lamps) {
int result = 0;
for(int i: IR(0, lamps.size() - 1)) {
if(lamps[i] != ' ' && lamps[i] != lamps[i+1]) {
++result; lamps[i] = lamps[i+1] = ' ';
}
}
if(lamps.size() >= 3) {
for(int i: IR(0, lamps.size() - 2)) {
if(lamps[i] == 'Y' && lamps[i] == lamps[i+1] && lamps[i+1] == lamps[i+2]) {
++result; lamps[i] = lamps[i+1] = lamps[i+2] = ' ';
}
}
}
return result;
}
};</pre>
<p>先に一通り YN/NY を消してしまってから YYY を調べていますが同じループ内で調べていれば実は通っていたようです。それで良いことが言えていないのであまり意味はないですが。足りないのはこれらのパターンだけでいいのかと、取り方が左から greedy でいいのか、でしょうか。greedy の方は NY, YYY, YN は(これらだけであれば)被っても 1 文字だけで内包もされないのでできるだけ片方に寄せた方がたくさんとれる、でいいかもしれません。これらのパターンだけでいいのかはうーん、2+2とかに分解した場合にその境界を超えるところがあっても高々左右1スイッチしか広がらなくて境界内では逆に独立性があがる、みたいな。あるいは結局これらの最小パターンに帰着できる、ということになるんでしょうか。はっきりこれだと言えない感じです。</p>
<h4>まとめ</h4>
<p>今回珍しく簡潔に書けちゃったもので、Challenge 中に他の人のコード見てると「なんでこんなややこしいの」って感じになってしまいました。Challenge するには気力が足りなくなってる感じです。今回たまたま R1A で通ってしまいましたが、どう考えてもリハビリが足りない感じなので Parallel Round にはできるだけ参加したいと思っています。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-70609880502524631072014-04-15T01:49:00.000+09:002014-04-15T01:53:36.698+09:00Google Code Jam 2014 Qualification Round<p>今年も GCJ に参加しているわけですが、無事、Qualification Round は突破した模様です。一応全完。今回も C++11 で書こう、は有効の状態です。あまり活用してないですが。まず最初にテンプレ。</p>
<pre class="brush: cpp">// gcc version 4.8.2 with -std=c++11
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <tuple>
#include <initializer_list>
#include <cmath>
// Boost library can be retrieved from http://www.boost.org/
// 1.52 is used
#pragma GCC diagnostic ignored "-Wconversion"
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
#pragma GCC diagnostic warning "-Wconversion"
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
using namespace std;
template<class Integer>
inline auto
IR(Integer first, Integer last) -> decltype(boost::irange(first, last))
{ return boost::irange(first, last); }
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
cout << "Case #" << casenum+1 << ": " << endl;
}
return 0;
}</pre>
<p>Range-based for loop 用に IR() を作ってます。元々 REP マクロ(というかマクロ全般)があまり好きではないので基本 Range-based for loop 使用ですが元々のテンプレで使っていた部分から外すほど修正もしていない感じです。では、以下各問題について。</p>
<h4>Problem A. Magic Trick</h4>
<p>やるだけ。わざわざ set 2 つ作って set 演算してますが、1 つだけ作っといてもう一方は読み込みながら判定、の方が無駄が少ないですね。後、サイズ既知の vector の場合は for(auto &val : v) { cin >> v; } でさくっと読み込めますけどこれくらい簡単に set とかも読み込みたい感じ。inserter みたいな感じでラッパ作ればいけそうではありますが。</p>
<pre class="brush: cpp">set<int> read()
{
set<int> t;
int ans; cin >> ans;
for(int i : IR(1,5)) {
int n;
if(i != ans) {
for(int j: IR(0,4)) { cin >> n; }
} else {
for(int j: IR(0,4)) { cin >> n; t.insert(n); }
}
}
return t;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
set<int> s1 = read();
set<int> s2 = read();
set<int> sr;
set_intersection(RNG(s1), RNG(s2), inserter(sr, sr.end()));
if(sr.size() > 1) {
cout << "Case #" << casenum+1 << ": " << "Bad magician!" << endl;
} else if(sr.size() == 0) {
cout << "Case #" << casenum+1 << ": " << "Volunteer cheated!" << endl;
} else {
cout << "Case #" << casenum+1 << ": " << *sr.begin() << endl;
}
}
return 0;
}</pre>
<h4>Problem B. Cookie Clicker Alpha</h4>
<p>ループで回した場合のループ回数を確認するのが面倒だったのでへたれて不等式を解いて一撃にしてしまいました。$$ X/{2+(n+1)F} ≤ C/{2+(n+1)F} + X/{2+(n+2)F} $$ n と n+1 で立式すればよかったんですが、なぜか n+1 と n+2 で立ててしまったので微妙にずれた感じです。一応、累積誤差を考えて数が小さい方から加算するようにしていますが気にしなくても良かったかも。</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin << cases;
REP(casenum, cases) {
long double C, F, X; cin << C << F << X;
int thr = floor((F*X - 2*C - F*C)/(F*C));
long double result = 0;
if(thr <= 0) {
result += X / (2+(thr+1)*F);
for(int i : IR(0, thr+1)) {
result += C / (2 + (thr-i)*F);
}
} else {
result = X / 2;
}
cout << "Case #" << casenum+1 << ": " << fixed << setprecision(7) << result << endl;
}
return 0;
}</pre>
<h4>Problem C. Minesweeper Master</h4>
<p>Cookie Clicker には Orteil does not endorse and has no involvement with Google Code Jam. と書いてあるのに Minesweeper には Microsoft Windows への言及があるのに同様の文言がなかったのは何か意味があるのでしょうか。</p>
<p>DP で解いた人も居るようですが、場合わけでやりました。書いてる時には(コピペ分も多いので)そんなに長く書いたつもりはなかったのですが、結果としては結構長いですね。</p>
<p>全体を貫く考え方としては、(1行、あるいは1列の場合でなければ)空きマスが最低2行あるいは2列繋がっていないと広がらない、です。また、c は必ず左上にしています(一般性を失わない)。最初の場合分けとしては、1行の場合、1列の場合、2行の場合、2列の場合、それ以外(3行3列以上)の場合で分けています。行・列を転置してしまえば場合わけは少なくなりますが、転置するのも面倒なんでコピペベースでいいや、という駄目な手抜きです。</p>
<p>1行あるいは1列の場合は、impossible は無しで右端あるいは下端から詰めるだけ。</p>
<p>2行あるいは2列の場合は爆弾が奇数の場合は基本 impossible ですが、1 マスだけ残っている場合は OK。OK の場合は右端あるいは下端から詰めるだけです。</p>
<p>最後、3行3列以上の場合は、さらに場合わけしています。最低2行あるいは2列必要ということから考えると、1) M ≦ (R-2)*(C-2) の場合は、左端および上端2列分を開けておいて右下から詰めていけば良い 2) R*C-M < 9 の場合、R*C-M = 2, 3, 5, 7 の場合 impossible、それ以外の場合は左上の状態は R*C-M の値に合わせて決め打ち、で良いことが分かります。最後、R*C-M ≧ 9 の場合ですが、空きマス8個分は確定、(2,2) の位置で偶奇を調整して、後は右2列を下から1行(2マス)づつ、上2行を右から1列(2マス)づつ埋めていけば良いことになります。</p>
<p><a href="https://docs.google.com/drawings/d/1p2tnSozJNKlqm7pb4rw5XiCUFefLQNzsz3HsPOsD-W4/pub?w=952&h=932"><img src="https://docs.google.com/drawings/d/1p2tnSozJNKlqm7pb4rw5XiCUFefLQNzsz3HsPOsD-W4/pub?w=476&h=466"></a></p>
<p>Short input については全入力パターンが (1+2+3+4+5)^2 = 225 通り、制約の数字から全パターンが入力になってそうってことでローカルで全入力作っといて目視で確認してから subumit してます。時間に余裕のある Qualification Round ならではって感じですね。</p>
<pre class="brush: cpp">void c1(int R, int M)
{
cout << "c" << endl;
for(int i: IR(0, R - M - 1)) cout << "." << endl;
for(int i: IR(0, M)) cout << "*" << endl;
}
void r1(int C, int M)
{
cout << "c";
for(int i: IR(0, C - M - 1)) cout << ".";
for(int i: IR(0, M)) cout << "*";
cout << endl;
}
void c2(int R, int M)
{
if(2*R-M == 1) {
cout << "c*\n";
for(int i: IR(0, R - 1)) cout << "**" << endl;
} else if(M % 2 || 2*R-M == 2) {
cout << "Impossible" << endl;
} else {
cout << "c.\n";
for(int i: IR(0, R - M/2 - 1)) cout << ".." << endl;
for(int i: IR(0, M/2)) cout << "**" << endl;
}
}
void r2(int C, int M)
{
if(2*C-M == 1) {
cout << "c";
for(int i: IR(0, M/2)) cout << "*";
cout << endl;
cout << "*";
for(int i: IR(0, M/2)) cout << "*";
cout << endl;
} else if(M % 2 || 2*C-M == 2) {
cout << "Impossible" << endl;
} else {
cout << "c";
for(int i: IR(0, C - M/2 - 1)) cout << ".";
for(int i: IR(0, M/2)) cout << "*";
cout << endl;
cout << ".";
for(int i: IR(0, C - M/2 - 1)) cout << ".";
for(int i: IR(0, M/2)) cout << "*";
cout << endl;
}
}
char result[50][50];
void gen(int R, int C, int M)
{
for(int i: IR(0,R)) { for(int j: IR(0,C)) { result[i][j] = '*'; } }
if(R*C - M == 1) { // nothing to do
} else if(R*C - M == 4) {
result[0][0] = result[0][1] = result[1][0] = result[1][1] = '.';
} else if(R*C - M == 6) {
result[0][0] = result[0][1] = result[1][0] = result[1][1] = result[2][0] = result[2][1] = '.';
} else if(R*C - M == 8) {
for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
result[2][2] = '*';
} else if(R*C - M < 9) {
cout << "Impossible" << endl;
return;
} else if(M <= (R-2)*(C-2)) {
for(int i: IR(0,2)) { for(int j: IR(0,C)) { result[i][j] = '.'; } }
for(int i: IR(0,R)) { for(int j: IR(0,2)) { result[i][j] = '.'; } }
int MM = (R-2)*(C-2);
for(int i: IR(2, R)) {
if(M == MM) break;
for(int j: IR(2,C)) {
result[i][j] = '.'; --MM;
if(M == MM) break;
}
}
} else {
for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
int MM = R*C - 9;
if(((R*C-M) % 2) == 0) {
result[2][2] = '*'; ++MM;
}
for(int i: IR(3, R)) {
if(M == MM) break;
for(int j: IR(0, 2)) {
result[i][j] = '.';
}
MM-=2;
}
for(int i: IR(3, C)) {
if(M == MM) break;
for(int j: IR(0, 2)) {
result[j][i] = '.';
}
MM-=2;
}
}
result[0][0] = 'c';
for(int i: IR(0,R)) { for(int j: IR(0,C)) { cout << result[i][j]; } cout << endl; }
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
int R, C, M; cin >> R >> C >> M;
cout << "Case #" << casenum+1 << ":" << endl;
if(R == 1) { r1(C, M); }
else if(C == 1) { c1(R, M); }
else if(R == 2) { r2(C, M); }
else if(C == 2) { c2(R, M); }
else { gen(R, C, M); }
}
return 0;
}</pre>
<h4>Problem D. Deceitful War</h4>
<p>War について Ken の戦略は Naomi の戦略に依らないということなので順序は気にしなくとも良いはず。ということで、Ken としては勝つときには最小の余力(Naomi の値以上で最小のものを出す)で勝ち、負けるときは最小で出すという自然な戦略で良いはずです。では、Deceitful War ではどうなのかといことで、とりあえず最初にできるだけ強いカードを捨てさせて(相手の最大に自分の最小をぶつける)、後は先後逆転で計算する形で書いたら結果が合いません(この時点でなんで先後逆転で計算しようと思ったのか細かいことを忘れちゃってます)。入力例の最後をソートして眺めると、勝ちようがない最小の1枚だけ捨てて後は Naomi が全て勝ってるんですよね。ってことで捨てる枚数でループさせて最大値を取る、で一応結果は合うのですが……。ここで天啓。「あれ?相手のカードも戦略も全部分かってるんだから相手の出すカード全部操作できるんじゃね?」これで先後逆転で一発計算すればいいや、となりました。実際には submit 時点では宣言した値と勝敗が異なってはいけないという条件を忘れていたので考えが足りなかったのですが、Ken の最大値より大きな値を言い続ければ最小から出てくるのでそこで勝ち続けて、勝てなくなるところからは最小値より小さな値を言い続ければやっぱり小さい方から出てきてそこで負ければよい、となるので問題ないことになります(仮に本当にこのまま実際にに人間相手にやったら普通ばれるでしょうけれども)。</p>
<pre class="brush: cpp">int calc_war(const set<double> &naomi, set<double> ken)
{
int ret = 0;
for(double i : naomi) {
auto it = ken.upper_bound(i);
if(it != ken.end()) {
ken.erase(it);
} else {
ken.erase(ken.begin());
++ret;
}
}
return ret;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
set<double> naomi, ken;
int N; cin >> N;
for(int i: IR(0, N)) { double t; cin >> t; naomi.insert(t); }
for(int i: IR(0, N)) { double t; cin >> t; ken.insert(t); }
size_t result_war = calc_war(naomi, ken);
size_t result_dwar = naomi.size() - calc_war(ken, naomi);;
cout << "Case #" << casenum+1 << ": " << result_dwar << ' ' << result_war << endl;
}
return 0;
}</pre>
<h4>まとめ</h4>
<p>TopCoder Open より Google Code Jam の方が相性がいい感じなのですが、なかでも Qualification Round は時間を気にせずに考えたり書けるんで一番楽しいです。本戦考えるとあんまり良くない参加方法ではありますが。今年もどこまでいけるか分かりませんが、Round1 は突破したいなぁ。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-67605163265044724252014-04-08T23:37:00.000+09:002014-04-15T22:54:15.051+09:00EclipseCoder C++ プラグインの拡張<p>競技プログラミング界の雄 TopCoder では競技環境でプラグインの使用が可能ですが、それを利用して Eclipse 上でコーディングできるようにしてしまおうというのが <a href="http://fornwall.net/eclipsecoder/">EclipseCoder</a> です。実際便利ではあるのですが、C++ でやっている場合に特に面倒なのが以下 2 点です。</p>
<ol>
<li>例えば、Windows 上で VC++ が入っている状態だけど Cygwin GCC を使いたい場合などに、毎回ツールチェインの設定が必要だったりする(環境依存)。
<li>C++11 有効にしたりオプション変えるのも毎回設定が必要。
</ol>
<p>ということで、これらの設定が可能なように C++ プラグインを修正しました。<a href="https://github.com/yak1ex/eclipsecoder-cpp/releases/tag/0.2.5y1">GitHub のリリースページ</a>から net.fornwall.eclipsecoder.ccsupport_0.2.5y1.zip をダウンロード、中の net.fornwall.eclipsecoder.ccsupport_0.2.5.jar で Eclipse インストール先フォルダの同名ファイルを上書きしてください。Window -> Preferences -> EclipseCoder -> C++ の設定下側に、コンボボックスが 2 つ増えています。上がツールチェインの設定、下が設定のコピー元プロジェクトです。</p>
<p><a href="https://docs.google.com/drawings/d/1s89CKfbqR7YkYVH6Z-KKNyygmAcTlCMzh3z_NO5MVFU/pub?w=668&h=480"><img src="https://docs.google.com/drawings/d/1s89CKfbqR7YkYVH6Z-KKNyygmAcTlCMzh3z_NO5MVFU/pub?w=334&h=240"></a></p>
<p>設定コピー元プロジェクトについては EclipseCoder で作成されたプロジェクトを元にした方が無難なので、まずはツールチェインについては自分の使用するものを選び(選択必須)、プロジェクトについては空白にしておきます。この状態でいつものように TopCoder に接続、Practice にでも入って問題を開くと新規プロジェクトが作成されます。この時、特に必須ではありませんが作成されたプロジェクトを設定コピー元プロジェクトだと分かるようリネームしておいてもいいかもしれません。このプロジェクトで EclipseCoder でのプロジェクト作成時に適用しておきたい設定を適当に変更します。例えば (Cygwin GCC で) C++11 有効にする場合だと↓の感じになります。</p>
<p><a href="https://docs.google.com/drawings/d/1Zze13IAHqKAhy9CIpe7L2T-YZLMMO_OsEx9klcdzddk/pub?w=824&h=476"><img src="https://docs.google.com/drawings/d/1Zze13IAHqKAhy9CIpe7L2T-YZLMMO_OsEx9klcdzddk/pub?w=412&h=238"></a></p>
<p>これで再度 Window -> Preferences -> EclipseCoder -> C++ を開いて、今度は下側のコンボボックスで先ほど設定を変更したプロジェクトを選びます。上側コンボボックスで選択しているツールチェインと整合していなかったりすると OK 時にメッセージが表示されて適用できません。SRM 615 Div2 250 で作成したプロジェクトを設定コピー元プロジェクトにした場合、↓のようになります。</p>
<p><a href="https://docs.google.com/drawings/d/1HARO0myH3x-WjsgWpkbU1tFJC1KXU8Q2U3UoYDitQlw/pub?w=640&h=480"><img src="https://docs.google.com/drawings/d/1HARO0myH3x-WjsgWpkbU1tFJC1KXU8Q2U3UoYDitQlw/pub?w=320&h=240"></a></p>
<p>後は、普通に問題を開いていくと先ほどの設定コピー元プロジェクトの設定内容が反映されているはずです。注意点として、設定を取得する際にはプロジェクトがオープンされている必要があるため、設定コピー元プロジェクトは必要があればオープンされます。そしてプラグイン側ではクローズしません。毎回オープン・クローズ繰り返すのもどうかな、と思ったのでこういう仕様になっています。</p>
<p>よろしければ使ってみてください。とりあえずしばらくして問題がなさそうであれば upstream に pullreq を出すつもりです。実のところ 1. については <A href="https://github.com/fornwall/eclipsecoder-cpp/pull/1">pullreq</a> がすでに upstream にマージ済みでリリースバージョンまで更新されているのですが、にも関わらずサイトでリリースされていません。作者さんが忘れているだけなんじゃないかな、という気もしますが、pullreq 出したときに「Java 初心者なんでチェックしてね」みたいなことを書いてしまったので確認するのもなんだかなと思っているうちに 1 年が経ってしまいました。</p>
<p>なお、本プラグインを使用したせいで Eclipse が落ちて rating 下がった等、いかなる結果についても責任を負いかねますのでその辺は承知の上でお願いします。【追記】もし使用されてる方がいらっしゃいましたら「問題なく動いてるよ」でも良いのでコメントを付けて頂けると嬉しいです。pullreq の支えになりますので。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-20224227011719652042013-12-17T22:54:00.003+09:002013-12-18T21:44:51.685+09:00main() のすり替え in C++<p><b>[2013/12/18] ptr_umain 経由の呼び出しで引数を付けていなかった点を修正。</b></p>
<p>ある種のライブラリの場合、main() の呼び出し前に処理をしておきたい場合があります。ものすごく真っ当な方法で言うならスタートアップルーチンを書くべきところではありますが、その場合、ライブラリを使う側でもオプション指定が必要になったりしてちょっと面倒になります。こういう時に、ライブラリ側で main() を定義してしまいユーザーコード側では</p>
<pre class="brush:cpp">// main.h
#define main _umain
#ifdef __cplusplus
extern "C" int _umain(int argc, char **argv);
#else
extern int _umain(); // No specification for parameters in C
#endif
// main.c
#include "main.h"
int main(int argc, char **argv) { /* ... */ } // replaced with _umain
</pre>
<p>のようにヘッダを読み込ませることによって main() をすり替えてしまい、ライブラリ側の main() からすり替えた _umain() を呼び出す、といったことが行われる場合があります。例えば SDL (<a href="http://www.libsdl.org/">http://www.libsdl.org/</a>) なんかはこれを使っているようです。</p>
<p>が、問題が一つ。main() は引数が固定されていません。実用的には、以下の3種類くらいあると考えてよいでしょう。</p>
<pre class="brush:c">
int main(void);
int main(int argc, char **argv);
int main(int argc, char **argv, char **envp);
</pre>
<p>C の場合、これでもそんなに問題になりません。すり替え用マクロが有効であるとして、上記コードのように extern int _umain(); としておけば、<b>C 言語では</b>引数に関しては指定がない扱いであり、かつ可変引数関数を実現する C の呼び出し規約上、上記いずれの定義であっても _umain(argc, argc, envp); と呼び出してしまえば、普通の処理系ならまず問題なく動作するはずです。</p>
<p>が、C++ の場合、プロトタイプ宣言が必須であり、また、関数の型チェックが必ず行われます。つまり main() がどの形式で定義されていたかによって呼び分ける必要が出てくるわけです。前述の SDL では main() の型を int main(int, char**) に限定することで回避しているようです。最初から特定ライブラリを使う前提であればそれでもいいのですが、今作成中のライブラリ(<a href="https://github.com/yak1ex/UTF8-Win32API/">UTF-8 Win32 API</a>)は後付けの形での利用を想定しているので限定はちょっとつらいです。</p>
<p>要はユーザーがどの形式で main() を定義したか判別する方法があればいいわけです。そこで(処理系依存ですが) GCC の weak symbol と alias を使用してみました。</p>
<pre class="brush:cpp">int _umain_stub()
{
return 0;
}
// for C
extern "C" int _umain(...) __attribute__((weak, alias("_Z11_umain_stubv")));
// for C++
extern int _umain() __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc) __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc, char ** argv) __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc, char ** argv, char **envp) __attribute__((weak, alias("_Z11_umain_stubv")));
static int(*ptr_umain)(...) = static_cast<int(*)(...)>(_umain);
static int(*ptr_umain0)() = static_cast<int(*)()>(_umain);
static int(*ptr_umain1)(int) = static_cast<int(*)(int)>(_umain);
static int(*ptr_umain2)(int, char**) = static_cast<int(*)(int, char**)>(_umain);
static int(*ptr_umain3)(int, char**, char**) = static_cast<int(*)(int, char**, char**)>(_umain);
template<typename T>
static inline bool is_target(T t)
{
return t != reinterpret_cast<T>(_umain_stub);
}
int main(int argc, char **argv, char **envp)
{
if(is_target(ptr_umain)) return ptr_umain(argc, argv, envp);
if(is_target(ptr_umain0)) return ptr_umain0();
if(is_target(ptr_umain1)) return ptr_umain1(argc);
if(is_target(ptr_umain2)) return ptr_umain2(argc, argv);
if(is_target(ptr_umain3)) return ptr_umain3(argc, argv, envp);
return -1; // Not reached if main() is user-defined
}</pre>
<p>通常、同名の関数定義がある場合、多重定義エラーになります。weak symbol を使うと、他に同名の定義がない場合だけ有効になる定義を作ることができます。デフォルト実装の定義を作っておいて、場合によってはより高速な実装に差し替えることも可能、みたいな使い方が典型的なユースケースです。alias はある関数を別の関数の別名として定義できる機能です。上記コードでは C/C++ の _umain() 系を全て _umain_stub(void) の別名かつ weak symbol としています。ユーザーがある形式の main() を定義した場合、マクロで _umain() にすり替えられていずれかの weak symbol が上書きされます。結果として _umain_stub(void) と値(アドレス)が変わるため、それを is_target() で判別して呼び分けているわけです。</p>
<p>で、話が済んでいれば幸せだったのですが、なぜか StrawberryPerl 5.18.1.1 32bit 中の GCC を使って、↑ main() のあるソースファイルで #include <iostream> や #include <cstdio> すると関数ポインタの値がずれます。Cygwin の i686-w64-ming32-g++ だと問題ありません。両方とも GCC-4.7.3 なんですが。例えば実際のアドレスが、<br>
__Z7_umain_v (ユーザー定義の _umain(void)) -> 0x401560<br>
__Z11_umain_stubv (_umain_stub(void)) -> 0x40195e<br>
である場合に、バイナリ中で参照されるアドレスがそれぞれ、0x40117e, 0x40157c だったりします。両方とも 0x3e2 だけずれています。バグなのか設定がおかしいのかちょっと分かりませんがとりあえず以下のようなコードで無理やり補正すると一応動作はします。ユーザー定義の _umain() と _umain_stub(void) の 2 種類があるだけで、かつ、ユーザー定義は 1 つだけ存在するはず、という前提で多数派が実際には _umain_stub(void) であるとみなしてその差を補正しています。</p>
<pre class="brush: cpp">template<typename T>
static inline unsigned long get_offset(T t)
{
return reinterpret_cast<unsigned long>(_umain_stub) - reinterpret_cast<unsigned long>(t);
}
template<typename T>
static inline void add_offset(T& t, unsigned long offset)
{
t = reinterpret_cast<T>(reinterpret_cast<unsigned long>(t) + offset);
}
void fix_fptr()
{
std::map<unsigned long, int> counter;
++counter[get_offset(ptr_umain)];
++counter[get_offset(ptr_umain0)];
++counter[get_offset(ptr_umain1)];
++counter[get_offset(ptr_umain2)];
++counter[get_offset(ptr_umain3)];
// assert(counter.size() == 2);
unsigned long offset = counter.begin()->second > (++(counter.begin()))->second ? counter.begin()->first : (++(counter.begin()))->first;
add_offset(ptr_umain, offset);
add_offset(ptr_umain0, offset);
add_offset(ptr_umain1, offset);
add_offset(ptr_umain2, offset);
add_offset(ptr_umain3, offset);
}</pre>
<p>ちょっとどうだかなという感じではあるので、とりあえず、#include <iostream> や #include <cstdio> を外して様子見な感じですが謎な状態です。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-78691690103417046742013-11-22T23:04:00.001+09:002013-11-22T23:04:52.818+09:00\L と \U と Perl<p>Perl スクリプトに文字列を渡すのに</p>
<pre class="brush: bash">count -t '\t'</pre>
<p>のような感じでエスケープを使いたいけれど、Perl コアでそのものの機能は提供されていないということで <a href="https://github.com/yak1ex/String-Unescape">String-Unescape</a> というモジュールを作成中です。もちろん eval 使えば済むのは分かってるんですけど、文字列 eval はなるたけ避けたいということで。その中でぶつかった(自分的には)驚きの Perl 仕様について書いてみます。</p>
<p>ダブルクウォート内で \Q と \E で囲った範囲の英数アンダーバー以外をエスケープできる(quotemeta がかかる)というのは Perl 使いではそれなりに知られた事実だと思います。</p>
<pre class="brush: perl">say "\Q[|]\E";
# \[\|\+\]</pre>
<p>同様に範囲で効く変換として \L, \U も存在は知っているという方も多いでしょう(最近は \F と言うのもあります)。で、これらは重ねることができると <a href="http://search.cpan.org/~rjbs/perl-5.18.1/pod/perlop.pod#Quote_and_Quote-like_Operators">perldoc perlop</a> には書いてあります。</p>
<blockquote>\L, \U, \F, and \Q can stack, in which case you need one \E for each. For example:</blockquote>
<pre class="brush: perl"> say"This \Qquoting \ubusiness \Uhere isn't quite\E done yet,\E is it?";
# This quoting\ Business\ HERE\ ISN\'T\ QUITE\ done\ yet\, is it?</pre>
<p>さて、では問題です。以下はどのように出力されるでしょうか。</p>
<pre class="brush: perl">say "\Q[A\U[a\L[A\E[a\E[A\E";</pre>
<p>正解は \[A\[A\[a\[a[A です。この時点で「は?」って感じですが、続いて第 2 問。</p>
<pre class="brush: perl">say "\U[a\Q[a\L[A\E[a\E[a\E";</pre>
<p>正解は [A\[A[a[a[a です。もう訳がわからないという感じですが、真っ当に追っかける気を無くすコードを感覚で読み取ったところ、\U 中の \L や \L 中の \U があると、その前の \U, \L まで(途中に \Q とかがあればそれも)無効になった後で、新しく \L, \U が有効になるようです。\L や \U が一回しか有効にならないように \E が適宜補われると考えると分かりやすいかもしれません。</p>
<pre class="brush: perl">say "\Q[A\U[a\L[A\E[a\E[A\E";
say "\Q[A\U[a\E\L[A\E[a\E[A\E"; # 直前の \U が無効
# \[A\[A\[a\[a[A
# \[A\[A\[a\[a[A</pre>
<pre class="brush: perl">say "\U[a\Q[a\L[A\E[a\E[a\E";
say "\U[a\Q[a\E\E\L[A\E[a\E[a\E"; # \U\Q が無効
# [A\[A[a[a[a
# [A\[A[a[a[a</pre>
<p>\L...\U...\E...\E ってやっても外側の \L しか効かないから無駄じゃねーか、という意図であろうというのは推測できますが、個人的には「いや、書かれたとおりに実行しろよ」と言いたくなる挙動です。</p>
<p>もう一つ、エスケープ関連でお節介じゃないの?という機能として、\L\u と \U\l をそれぞれ \u\L と \l\U に置き換えるというものがあります。</p>
<pre class="brush: perl">say "\L\uaAA\E \U\lAaa\E";
# Aaa aAA</pre>
<p>\u してから \L したら結局 \L だけじゃねーかってのは分かりますが、「勝手に書き換えるな、警告出せ」と思うわけです。</p>
<p>ちょっと気を利かせたつもりで全体として訳が分からなくなる、というのはある意味とても Perl らしいという気もしますが。元々 String-Unescape は Perl の処理と一致させることを目指そうと思っていたわけですが、この 2 つの挙動(特に前者)は無理して再現する必要はないだろうということで実装しないつもりでいます。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-55223403829912134802013-09-26T16:13:00.002+09:002013-09-26T16:13:47.825+09:00YAPC::Asia Tokyo 2013 参加メモ(二日目)<p><a href="http://yak-ex.blogspot.jp/2013/09/yapcasia-tokyo-2013.html">前稿</a>に引き続き、聴講したトークの雑感を箇条書き的に。</p>
<h2>Mojoliciousでつくる!Webアプリ入門 by Yusuke Wada</h2>
<ul>
<li>WAF 自作も楽しいけど、そこは本題じゃないんだからとりあえず WAF 使っとくのが良い、と。</li>
<li>ライブコーディングでさくっと作られてたのですごい簡単感が伝わってたと思います。</li>
<li>「分けることで分かる」「少しづつやる(ことで俺スゲー感を持続)」俺スゲー感はモチベーション持続に有用ですよ、本当。新しいことやると楽しいんですよね。</li>
<li><a href="http://ccf.myhome.cx:5000/ccf.html">CCF</a> は WAF 使ってないんですが、特に model がきちっと分かれてないところは次の大改修前には手直ししたいという気になりました。</li>
</ul>
<h2>Programming AWS with Perl by Yasuhiro Horiuchi</h2>
<ul>
<li>with Perl 要素少なめ。</li>
<li>Python 製 AWS CLI が提供されてるので、Perl での自動処理用にはそれに対する wrapper AWS::CLIWrapper を使えば良いのではないかと、という感じですかね。</li>
<li>CLI と API 直叩きモジュールとどちらが良いという質問がありましたが、自動処理用には CLI 経由でいいでしょうけど、アプリ的にはモジュール使用なんじゃないですかね。</li>
</ul>
<h2>What's new in Carton & cpanm by Tatsuhiko Miyagawa</h2>
<ul>
<li>もちろん cpanm は使ってますけど Carton は使ってないんですよね。個人の趣味の領域だとそこまで必要性を感じないというか。</li>
<li>git URL 可になったのは patch 版指定とかできて嬉しい感じではあるんですけど、Dist::Zilla で github に置くと普通はインストール可にならないんで、その辺どうするのがいいのかな、と思ったりします。</li>
</ul>
<h2>GitHubでつくる、たのしい開発現場 by Hiroki OHTSUKA</h2>
<ul>
<li>どっちかっていうと精神よりというか、本来そういうことの方が重要だとは思うんですが、やっぱり具体的なツールとか Tips の方が分かりやすいんですよね。</li>
</ul>
<h2>可視化のためのPerl by Muddy Dixon</h2>
<ul>
<li>可視化には Explanatory (ストーリー説明) と Exploratory (ストーリー探索) の 2 種類がある。</li>
<li>マイニング技術者はドメイン知識が少ない v.s. ドメイン専門家はマイニングの知識が少ないので可視化してドメイン専門家に見てもらおう、と。</li>
<li><a href="https://github.com/gitpan/DataCube">DataCube</a> の開発止まってるじゃんということで、<a href="https://github.com/muddydixon/data-cube">Data::Cube</a> をリリースされたとのことですが、「僕はこの手の処理はRでやります」という衝撃の結末からは、どうせこのモジュールも開発止まるんでしょ?、感が激しくします。</li>
</ul>
<h2>本当にあったレガシーな話 by Daisuke Maki</h2>
<ul>
<li>livedoor blog のモダン化について。<a href="http://codezine.jp/book/modernperl2">モダン Perl 入門 増補改訂版</a> に書かれるそうです。題名は増補改訂版になっていますが 80% 変わっているとのこと。</li>
<li>発表的にはとりあえず mod_perl dis だったと思っておけば大体合ってるんじゃないでしょうか。</li>
<li>とにかくログをとることがまず最初。設定切り替えには use constant による定数たたみ込み最適化の利用をすると良い。</li>
<li>他色々あったんですが、$0 変えると ps で見たときに分かるというのは Tips は面白かったです。</li>
</ul>
<h2>スマフォアプリ開発を支える認証認可アーキテクチャ by Rieko Suzuki</h2>
<ul>
<li>執筆記事の著者写真の時点でなんかもう色々と違う気がしましたが「糞アプリ」発言で逆に安心しました。</li>
</ul>
<h2>PhantomJSによる多岐にわたる広告枠の確実な表示テスト by Yusuke Yanbe</h2>
<ul>
<li><a href="https://metacpan.org/module/Selenium::Remote::Driver">Selenium::Remote::Driver</a> を使えば headless ブラウザである PhantomJS を操作できるのでそれを使ってテストするという話。</li>
</ul>
<h2>フルテストも50msで終わらせたい 〜 FreakOutの取り組み 〜</h2>
<ul>
<li>最初にさすがに 50ms は無理ですとの潔いお言葉。</li>
<li>一日目の soh335 さんの発表と結構被っていたとのこと。テスト用ユーティリティモジュールも用意されているそうです。</li>
<li>実行順序に依存するテストを避けるために、テスト順序のシャッフルがおすすめとのこと。</li>
<li>File::Find, List::MoreUtils, Parallel::ForkManager, Net::OpenSSH, TAP::Harness といった CPAN モジュールを組み合わせて分散実行することで 2,000 秒 over → 180 秒に短縮。</li>
<li>CPAN モジュールの組み合わせというのがとても Perl らしくていいですね。</li>
<li>「高速なテストは開発文化を変える」手元でやるより push した方が速いのでとりあえず push する文化に→コードが早期共有されてレビューも進み品質も向上。</li>
</ul>
<h2>LT</h2>
<p>とりあえず分かる範囲でメモ。名前が分からない方とかもし抜けてたらすみません。</p>
<ul>
<li>テストカバレッジについて http://coveralls.io/ というサービスがある。</li>
<li>DBIx::* の新しいモジュール。</li>
<li>makamaka さんの同人活動レポート。</li>
<li>HTTP から SMTP 送信ができる Haineko について。</li>
<li>Perl 入学式と近所の Perl Mongers のおかげで初心者でも「つぶやいてないでコード書け」というサービスができました!という話。いい LT だったと思います。</li>
<li>papix さんの Perl 入学式活動レポート。</li>
<li>kamipo さんの mysql-build の話。</li>
<li>もっとネタモジュールを!ということで netacpan.org できました。</li>
<li>kamadango さんのマイクロコミュニケーションの話。</li>
<li>tokuhirom さんの Test::Power っていうか HTTP::Body::Builder 作ったった。</li>
<li>mruby_nginx_module について。</li>
<li>pjf さんの <code>method add_datapoint( Str: $goal!, Int:$timestamp)</code> みたいに書ける Method::Signatures の紹介。</li>
<li>takesako さんの Perl クイズ。近藤嘉雪先生が優勝してました。チート級。識別子が 251 文字以下とかそんな制限あったんですね……</li>
</ul>
<h2>Keynote by Tomohiro Ikebe</h2>
<ul>
<li>「Management and Perl culture」というタイトル。</li>
<li><strike>マネージャーで画像検索するとリア充</strike> マネージャーって管理するというより支える方じゃないの?</li>
<li>できるエンジニアにできるからマネージャーやれ、は最悪。とはいえチーム内のリーダーシップは必要。</li>
<li>社内に対する広報(エンジニアの仕事が意味のある仕事だってことを伝える)ことも大事。</li>
<li>……そんなに年が変わらないということにちょっとショックを受けました。</li>
</ul>
<h2>YAPC::Asia Tokyo 2013 クロージング by Daisuke Maki</h2>
<ul>
<li>牧さん、櫛井さんのツートップによる YAPC::Asia はこれで終了、とのこと。後を継ぐ人が居ないとこれで終わり、ということなんでしょうか?</li>
<li>のべ参加者 1,000 人オーバー。うーむ、すごい。</li>
</ul>
<h2>まとめと余談</h2>
<ul>
<li>今年の YAPC は Perl の話題が多いな、とかいう tweet を見ましたが、確かに Perl 寄りな感じで個人的には嬉しかったです。</li>
<li>本当は今年発表できたらなーと朧気に思っていたのですが(Dist::Zilla の話とか)、Minilla と Milla のトークが応募されてるし、しかも Ricardo SIGNES ご本人来てるしってんで無理ゲーでしたね。LT できたらなーというネタは今年は余裕で間に合わなかったので来年に LT できたらなーと思っています。</li>
<li>今回新しいノート PC (VAIO Pro 13)で参加しました。今まで一台のノート PC をどのシーンでも使い回す感じだったので 2kg 前半まで選択肢に入れていたのですが、重量というよりもバッテリーの持ちからこの手のイベントではちょっときついな、ということでモバイル用として購入。シートバッテリがなかったとしてもイベント中はもってそうでした。重量はあんまり気にしてなかったんですが実際に使ってみると、部屋の移動のときに横に抱えるのも楽だし AC アダプタもなくてそのまま運べるしで良かったと思います。</li>
</ul>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-85660777725093786302013-09-26T16:13:00.000+09:002013-09-26T16:14:29.692+09:00YAPC::Asia Tokyo 2013 参加メモ(一日目)<p>遅ればせながら、<a href="http://yapcasia.org/2013/">YAPC::Asia Tokyo 2013</a> 参加メモ。</p>
<p>目が覚めたらいきなり当初乗るつもりだった電車の時間でしたが、最初の説明にわずかに遅刻する程度の時間で着。いきなり席が埋まってる感じでちょっとびびりました。メインの藤原洋記念ホール 1階席は後ろからの入り口が2ヶ所あるのですが、一度どっちかの入り口から入ってしまうと途中で別の通路側まで行くのは狭い席の間を移動するしかなく(ステージ直前では移動できたかも)手前通路側が埋まりがちになっていた気がします。 以下、聴講したトークの雑感を箇条書き的に。</p>
<h2>Postcards from the Edge: The State of Perl 5 Development by Ricardo SIGNE</h2>
<ul>
<li><a href="http://search.cpan.org/perldoc?Dist%3A%3AZilla">Dist::Zilla</a> でも大変お世話になっている RJBS こと Ricardo SIGNES 氏の Perl5 の今後についての発表。
<li>とりあえず pumpkin というのは Perl 5 のリリースマネージャ(というのが正確か分かりませんが)的な立ち位置の人だ、というのは以前の参加の時に聞いているので知っているのですが、何言ってるのかさっぱり分からない参加者の人とか居たんじゃないかな、というのは少し気になりました。
<li>「Perl5 は Perl5 であり続ける(意訳)」という言葉は印象的でした。
<li>postfix dereferencing <code>@{$hoge}</code> が <code>$hoge->@*</code> と書けるというのは確かにちょっとキモいですが Perl らしいキモさな気がします。実際 <code>$hoge->[3]->{key}</code> とか書いた後、あぁ array dereference しなきゃってんで、カーソル戻して <code>@{ }</code> で囲うとかいうのは超頻出パターンなので便利にはなるはず。
<li>本体開発側では互換性によってはじかれるパッチとか改良とかは少ないかもしれないですが、利用者側で互換性のために使用しない機能、とかは割とある気がします。モジュール書いててもより低いバージョンをサポートするためにより面倒な方法に書き直したりすることもありますし。強制アップデート的なことができれば楽かもしれませんが。
</ul>
<h2>Perlのモジュールを公開するときに気をつけておいた方がよい**個のこと by Kenichi Ishigaki</h2>
<ul>
<li>基本的に <a href="http://cpants.cpanauthors.org/">CPANTS</a> の Kwalitee の説明という感じで、<a href="http://search.cpan.org/perldoc?Test%3A%3AKwalitee%3A%3AExtra">Test::Kwalitee::Extra</a> とか書いてるくらいなので大体のところは既知でした。
<li>バージョンの形式(v0.1.5 だとか 0.1.5 だとか 0.001005 だとか)について聞いてみましたが、「特殊なことしないのであれば 0.01 とか使うのが楽」とのことでした。なんかコンセンサス的なものが欲しいです……
</ul>
<h2>Perl and Riak - 分散データストア Riak を Perl から "爆速" で使うために - by Tatsuro Hisamori</h2>
<ul>
<li>FreakOut さん所属。(前からそうで気付いてなかっただけかもしれないですが) YAPC での存在感が大きくなってる気がします。</li>
<li>内容についてはどうこう言えるほど知らない分野なので割愛。</li>
<li>「継続的に運用していくシステムにおいては"テストができる"ことはマスト要件」これ本当大事。</li>
</ul>
<h2>Inside amon2-livedoor-setup.pl with web application development 2013 by Kazuhiro Osawa</h2>
<ul>
<li>Team Geek 買いました。</li>
<li>溺愛の初期設定スクリプトだと社内事情が考慮されてないので、各社でひな形設定スクリプトを作っておくとよいよ、という話。</li>
<li>コピペを排除するためのひな形スクリプトがコピペ対象に、というのはものすごく有りそうな話。<li>
<li>「開発から本運用に必要なすべてを盛り込む」これは確かに大事だけど抜けやすそうな気がします。</li>
</ul>
<h2>SPDY、HTTP/2.0の使い方 by takesako</h2>
<ul>
<li>使いどころ、というところまでは達してなくて今使うならどうするか、くらいでしょうか。</li>
<li>HTTPS 接続を強制する HSTS (HTTP Strict Transport Secruity) は初めて聞きました。</li>
<li>Outbound Port 80 Blocking は笑ってしまいましたが、でもそれでもいい気がしますね。企業等のフィルタリングが辛いかもしれませんが。MITM 的に中継する HTTPS フィルタ proxy とかは SSL によるセキュリティの根本的なコンセプトを損なう最低の存在だと思っているので許容不可。</li>
</ul>
<h2>Types and Perl Language by Masahiro Honma</h2>
<ul>
<li>人全然居ないんじゃないの?と思ったら座れませんでした。</li>
<li>トラブルがあってデモができなかったり、本論に入る前のところで終わったりした感じで、もっとちゃんと聞きたかったですね。</li>
<li>ひょっとしたらトラブルが無かったらそうだったのかもしれませんがバックグラウンドの説明を廃して Typed Perl の実例側から話す、という流れもありだったんじゃないかと思います。</li>
</ul>
<h2>モダンPerlリファクタリング by Naoya Ito</h2>
<ul>
<li><a href="http://www.amazon.co.jp/dp/477415864X">Perl 徹底攻略</a> 掲載ネタです。毎回全く新しいネタを話すというのはとても難しいことだとは思うのですが、既に書籍を持っている状態で聞くと割と悲しい気分になったりするので、発表→書籍出版の順番になるようにしてもらえると宣伝にもなって双方がハッピーかもしれません。いや、トーク内容にも書いてあるし確認しておけば良かったんですけど。</li>
<li>とにかくまずはテストを作ること、細かいテストをちまちま書いていくという意味ではなく、とにかく大外の I/F 切ってテストを書いて、あとはテストとコード修正を並行していく、という感じでしょうか。</li>
<li><a href="http://search.cpan.org/perldoc?Test%3A%3ABase">Test::Base</a> で DATA セクションに置くとかまではやらないですけど、テストケースをデータにまとめておくってのは良くやりますね。</li>
</ul>
<h2>perl な web application のためのテスト情報 by soh335</h2>
<ul>
<li>テストを書いてもらうために、テスト用の共通モジュール t/Util.pm を作ってテストを書く障壁を下げている、とのこと。</li>
<li>Web application に限らないですし、各種 Test モジュールの簡単な紹介もあるのでさらっとスライド見ておくといいんじゃないでしょうか。</li>
<li>コードだけじゃなく、ファイル命名規則だとか用語チェックだとかもテストすればよい、というのは確かにその通りでわざわざ別の枠組み使わなくても TAP で合わせてしまえばいいですね。</li>
</ul>
<h2>はてなのサーバ管理ツールの話 by Yuuki Tsubouchi</h2>
<ul>
<li>ものすごくざっくりまとめると、運用系のツールは各種あって組み合わせの柔軟度は持っていたいけど設定が分散するので中央のコントローラーは内製といった感じでしょうか。</li>
<li>知見や経験がほとんどないところなんでなんとも言えないですが一通り紹介というよりはポイントに絞って話してもらったほうが良かったかもしれません。</li>
</ul>
<h2>LT</h2>
<p>題目と発表者リストがあるかと思ったらスケジュールの所にないですね……。とりあえず分かる範囲でメモ。名前が分からない方すみません。</p>
<ul>
<li>kazuho さんの prove の発表。prove は汎用 taskrunner である、と。(今後使うか分からない)拡張子限定の解除とか Tips 満載でした。</li>
<li>mobile factory の人。えーと何でしたっけ?モテる台詞でしたっけ?今年のネタ枠。</li>
<li>Tachikoma の話。依存ライブラリ指定を更新して commit して pullreq 出してくれる。n-click から 1-click だと商売になって、1-click から 0-click だと革命という台詞が印象に残りました。</li>
<li>yappo さんの HTTP::Builder::Body が欲しい、という話。</li>
<li>hirose31 さんの inspect running perl process という話。strace とかだと syscall しか見られないし gdb 系だと特定の環境に依存するしということで、inspect-perl-proc を作成。例えば perl プロセスが詰まってるときにどこの関数で詰まってるかとかが分かる。いや、これすごいんじゃないでしょうか。</li>
<li>yusukebe さんの YAPC::NA 行ってきた話。どこから来たの?で話ができるし、こちらから話を切り出せば聞いてくれるよ、とのこと。</li>
<li>eikichi さんの YAPC::Tohoku やりたい、という話</li>
<li>comewalk さんの OSS に対する貢献の話。別にコード書くだけが貢献じゃない、と。規模によるでしょうが、自分のような弱小個人だったりすると単に反応があるだけでも嬉しいですしバグレポだけでも「使ってくれてる人居たんだ(泣)」という気分になります。</li>
<li>bayashi さんの module 紹介。アップロードしたところで自分もすぐに使わなくなるかもしれないですが、ローカルにおいてるだけだと絶対に今の自分にしか使えないですが、上げれば誰かが使えるかもしれないですし、テストやドキュメントを書くので将来の自分にとっても役に立ったりするかもしれません。Milla, Minilla, Dist::Zilla とか使うと簡単にモジュールをアップロードできます。おすすめ。</li>
<li>gfx さんの Power Assert と Emscripten による perl.js の話。</li>
<li>mizuki_r さんの p5-Spica (Web service wrapper) の話。</li>
<li>Songmu さんの Riji (日記) の話。いや、中国語分からないっす。</li>
</ul>
<p>以下<a href="http://yak-ex.blogspot.jp/2013/09/yapcasia-tokyo-2013_26.html">次稿</a></p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-1268948173236516302013-05-04T22:24:00.001+09:002013-05-04T22:24:11.318+09:00Google Code Jam 2013 Round 1A<p>遅ればせながら。</p>
<h3>結果</h3>
<p>ooo-o- 46pts の rank 546 ということで無事 Round1 通過です。どうも TCO より GCJ の方が相性が良い気がします。とりあえず PATH の設定がおかしくて exe 実行時に DLL がないって怒られたり、ブラウザのデフォルトダウンロードパスが gcj2012 になってたりスタートの所で結構いらいらしてましたが通って良かったです。Problem B を short 限定解で割り切ったのが正解だった気がします。テンプレートは前回参照です。なお、Problem Analysis 未読状態です。</p>
<h3>Problem A. Bullseye</h3>
<p>基本二分探索でやるだけ、ですが単純にやると 64 ビットでオーバーフローするようになってるのが味噌でしょうね。式的には n 個目の円を描くのに必要なインクの量は (r+2n-1)<sup>2</sup> - (r+2n-2)<sup>2</sup> = 2r+4n-3 なので c 個目の円まで描くのに必要なインクの量は Σ(2r+4n-3) = 2cr+2c(c+1)-3c = c(2r+2c-1) となります。t ≧ c(2r+2c-1) を満たす最大の c を求めるということで二分探索すればいいわけですが 64 ビットだとオーバーフローしてしまうので、t/c ≧ 2r+2c-1 で計算しています。2r+2c-1 が整数になるので t/c が整数除算(切り捨て)でも > だった場合が = になるだけなので問題有りません。</p>
<p>多倍長をサポートしている言語を使う、GCJ は外部ライブラリの使用も可能なので多倍長ライブラリを使うといった対処もあったのですが面倒だったのでオーソドックスに先に割り算しておく、で対処しました。が、gcc は 4.6 から __int128 をサポートしているようなのでそれを使うのが一番簡単だったかもしれません。</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
ULL r, t;
cin >> r >> t;
ULL l_ = 1ULL, r_ = 2000000000ULL;
REP(i, 50) {
ULL tt = (l_+r_)/2;
if(t/tt >= 2*r+2*tt-1) {
l_ = tt;
} else {
r_ = tt;
}
}
cout << "Case #" << casenum+1 << ": " << l_ << endl;
}
return 0;
}</pre>
<h3>Problem B. Manage your Energy</h3>
<p>しばらく考えていましたが Large 解は見えなさそうだったので Short 限定解として DP で解きました。大抵 DP の時は memoize 的に書く場合が多いのですが、超正統派な DP なのでループで書いてます。今回 Large 解を出せていませんが、一旦 Short 解を作って通しておいて実績を作り、Large 解を作った時の検証に使う、というのはそれなりに有効な戦略だと思うので 1 つの解で Short/Large 両方というのにはそんなに拘わらなくていいと思っています。</p>
<p>終了後のコメント見ると greedy と言っている人がいました。時間中に考えていたことと合わせると、全 Energy は E+(N-1)R で、最大係数に最長時間を割り当てて、それより後では後ろの係数が大きいところは Energy を消費せずに積む、最大係数より前では前の係数が大きいところでより消費させてその場では Energy を消費させない、みたいにずらしていくことでいける、かも?</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI E, R, N; cin >> E >> R >> N;
vector<UI> v(N); for(auto &i : v) { cin >> i; }
vector<vector<UI>> t(N, vector<UI>(E+1, 0));
REP(i, t[N-1].size()) {
t[N-1][i] = i * v[N-1];
}
REP(j_, N-1) {
UI j = N-2-j_;
REP(i, t[j].size()) {
UI temp = 0;
REP(k, i+1) {
UI kk = i-k+R;
if(kk > E) kk = E;
temp = max(temp, k * v[j] + t[j+1][kk]);
}
t[j][i] = temp;
}
}
cout << "Case #" << casenum+1 << ": " << t[0][E] << endl;
}
return 0;
}
</pre>
<h3>Problem C. Good Luck</h3>
<p>いやー、さすが GCJ。出題者側も果敢に挑戦してくるなーと思ったのがこれ。100%の解ではなく一定率以上の正解であれば良い、という問題。実は Small が 1 つだけど複数回可能で、Large が 1 回のみ、というのに特化した Makefile を書いてたりするので今回割と悲しかったりするわけですが、問題読んだ後で「やってくれる」という感じでテンション上がりました。この調子だと近似解を求める問題とかも早晩出てきそうな感じがします。</p>
<p>Small 1 の方は数字が 2, 3, 4, 5 の 4 種類しかないので 3 か 5 が選ばれた場合には確定、2 と 4 の取り扱いをどうするかです。全ての選択パターンから分布をとって判定、とか可能な元の数字の組み合わせから該当するパターンの生起確率をとる、とかが正道な気がしますがベストな解を求める必要はないので手抜きです。素因数分解して 3 と 5 が確定する部分はまず確定。なお情報が全くないところについてはどの数字でも関係ないのでとりあえず 2 で埋める方針です。2<sup>6</sup>, 2<sup>5</sup> がある場合は 4 が 2 つあることが確定。2<sup>4</sup> がある時は 2,2,4 とかも有り得ますけど 4,4 の方が確率が高い(はずな)のでこれも 4 が 2 つ。2<sup>3</sup> がある時は 2,2,2 も有り得ますけど以下同文で 4 が 1 つ。2<sup>2</sup> の時は残り枚数が 1 枚の時は 4 が 1 つで確定。後は、2<sup>1</sup> の場合があれば 4 なし。なければ 4 が 1 つです。少なくともここは最適な戦略じゃない気がします。ただ下表のように分が悪い賭でもない、と思いますが、多分。</p>
<table border="1">
<tr><th> </th><th>積が2</th><th>積が4</th></tr>
<tr><th>2,2</th><td>(0,1)<br>(1,0)</td><td>(1,1)</td></tr>
<tr><th>2,4</th><td>(1,0)</td><td>(0,1)</td></tr>
</table>
<p>一応、これで一回で通っています。ジャッジが正答率出してくれれば良いのにという意見を見ましたが、自分でジャッジ作って試してみるというのが割と良い戦略だったかもしれないですね。</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
cout << "Case #" << casenum+1 << ":" << endl;
UI R,N,M,K; cin >> R >> N >> M >> K;
REP(i, R) {
vector<UI> pr(K); for(auto &val : pr) { cin >> val; }
int mc2 = 0, mc3 = 0, mc5 = 0;
vector<UI> dc2(7);
for(auto val : pr) {
int c2 = 0, c3 = 0, c5 = 0;
while(val % 2 == 0) { ++c2; val /= 2; }
while(val % 3 == 0) { ++c3; val /= 3; }
while(val % 5 == 0) { ++c5; val /= 5; }
++dc2[c2];
mc2 = max(mc2, c2);
mc3 = max(mc3, c3);
mc5 = max(mc5, c5);
}
REP(j, mc3) { cout << 3; }
REP(j, mc5) { cout << 5; }
int p2 = 3 - mc3 - mc5;
int c4 = 0;
if(dc2[6]) c4 = 3;
else if(dc2[5]) c4 = 2;
else if(dc2[4]) c4 = 2; //
else if(dc2[3]) c4 = 1; //
else if(dc2[2]) {
if(p2 == 1) c4 = 1; //
else if(dc2[1] == 0) c4 = 1;
}
REP(j, c4) { cout << 4; }
REP(j, 3-mc3-mc5-c4) { cout << 2; }
cout << endl;
}
}
return 0;
}</pre>
<h3>総評</h3>
<p>どうにか今年も T シャツ争奪権を得られました。もらえるといいなぁ。</p>
yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-90524456693583484122013-04-14T12:16:00.001+09:002013-04-14T12:16:16.555+09:00Google Code Jam 2013 Qualification Round<h3>結果</h3>
<p>D-Large が Timeout した以外は全部提出しましたが、C-Large が両方落ちて結局 100pt 4217 位でした。落ちる前は 3 桁 rank だったので終了後スコア見たときには D-Large 解いた人そんないるの?と思ったりしてしまいました。C-Large は 15 桁くらいまで bruteforce したリストと照らし合わせた上だったので落ちると思っていなかったのです。が、まぁ、最終結果で確認しろってことですね(後述)。</p>
<h3>前振り</h3>
<p>今回も C++11 を使って書く、をコンセプトにしています。開始してから gcc version 4.8.1 20130328 (prerelease) (GCC) をダウンロードしてきて使っています。ついでにとりあえず普段は使わない 64 bit exe にしています。共通コードは以下のようなコードです。Boost も使用。Google Code Jam の規定用に URL とバージョンを明示しています。IR というのは range-base for loop 用のものです(Integer Range のイメージ)。for(auto i : IR(1, 6)) とかやると 1,2,3,4,5 でループされます。</p>
<pre class="brush: cpp;">// gcc version 4.8.1 20130328 (prerelease) (GCC) at http://www.drangon.org/mingw/
// with -std=c++11
#include <iostream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <tuple>
#include <initializer_list>
#include <cmath>
// Boost library can be retrieved from http://www.boost.org/
// 1.52 is used
#pragma GCC diagnostic ignored "-Wconversion"
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
#pragma GCC diagnostic warning "-Wconversion"
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
using namespace std;
template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer last)
{ return boost::irange(first, last); }
</pre>
<h3>Problem A. Tic-Tac-Toe-Tomek</h3>
<p>縦横斜めで各コマの数を数えて判定。Small input の時は↓のように書きましたが、</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases; cin.ignore(numeric_limits<streamsize>::max(), '\n');
REP(casenum, cases) {
string result;
int num = 0;
int counter[4+4+2][3] = { 0 };
REP(i, 4) {
string s;
getline(cin, s);
REP(j, 4) {
if(s[j] == '.') continue;
int t = 0;
++num;
switch(s[j]) {
case 'X': t = 0; break;
case 'O': t = 1; break;
case 'T': t = 2; break;
default: assert(false);
}
++counter[ i][t];
++counter[4+j][t];
if( i == j) ++counter[8][t];
if(3-i == j) ++counter[9][t];
}
}
REP(i, 10) {
if(counter[i][0] + counter[i][2] == 4) result = "X won";
if(counter[i][1] + counter[i][2] == 4) result = "O won";
}
if(!result.size()) {
if(num == 16) result = "Draw";
else result = "Game has not completed";
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << "Case #" << casenum+1 << ": " << result << endl;
}
return 0;
}
</pre>
<p>「C++11で書いてないじゃないですかー」ということから一部修正して large input を submit</p>
<pre class="brush: cpp">
map<char, int> table = { {'X', 0 }, {'O', 1 }, {'T', 2 } };
// 略
int t = table[s[j]]; // swtich のところを置き換え
</pre>
<p>書くだけならこうも書けますが</p>
<pre class="brush: cpp"> int t = map<char, int>{ {'X', 0 }, {'O', 1 }, {'T', 2 } }[s[j]];</pre>
<p>毎回 map 作られるのはどうかと思ったのでやめました。</p>
<h3>Problem B. Lawnmower</h3>
<p>高い方のマスから縦横の高さを確定していく、というコードで1回書いて、別に縦横両方ともその高さで刈る訳じゃないじゃんということで没。実際に提出したコードは↓。縦横で最大の高さをとって(これ以上低く刈ることはできない)、各マスに対して縦横の低い方を取った結果が指定に一致するか、で判定しています。これ C++03 でも通っちゃうんじゃ?と思いましたが、right angle bracket さん(template 指定としての >> の連続)がいるので大丈夫ですね。</p>
<pre class="brush: cpp">int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI N, M; cin >> N >> M;
vector<vector<int>> board(N, vector<int>(M, 0));
vector<int> h(N, 1), v(M, 1);
REP(i, N) {
REP(j, M) {
cin >> board[i][j];
h[i] = max(h[i], board[i][j]);
v[j] = max(v[j], board[i][j]);
}
}
std::string result = "YES";
REP(i, N) {
REP(j, M) {
if(board[i][j] != min(h[i], v[j])) { result = "NO"; break; }
}
if(result == "NO") break;
}
cout << "Case #" << casenum+1 << ": " << result << endl;
}
return 0;
}
</pre>
<h3>Problem C. Fair and Square</h3>
<p>問題のアレです。繰り上がりが発生しないケースで限定しています。abcba の二乗だと、</p>
<table border="1">
<tr><th>8</th><th>7</th><th>6</th><th>5</th><th>4</th><th>3</th><th>2</th><th>1</th><th>0</th></tr>
<tr><td>a<sup>2</sup></td><td>2ab</td><td>2ca+b<sup>2</sup></td><td>2ab+2bc</td><td>2a<sup>2</sup>+2b<sup>2</sup>+c<sup>2</sup></td><td>2ab+2bc</td><td>2ca+b<sup>2</sup></td><td>2ab</td><td>a<sup>2</sup></td></tr>
</table>
<p>abccba の二乗だと、</p>
<table border="1">
<tr><th>10</th><th>9</th><th>8</th><th>7</th><th>6</th><th>5</th><th>4</th><th>3</th><th>2</th><th>1</th><th>0</th></tr>
<tr><td>a<sup>2</sup></td><td>2ab</td><td>2ca+b<sup>2</sup></td><td>2bc+2ca</td><td>2ab+2bc+c<sup>2</sup></td><td>2a<sup>2</sup>+2b<sup>2</sup>+2c<sup>2</sup></td><td>2ab+2bc+c<sup>2</sup></td><td>2bc+2ca</td><td>2ca+b<sup>2</sup></td><td>2ab</td><td>a<sup>2</sup></td></tr>
</table>
<p>と、偶数桁と奇数桁で挙動が違いますが中央桁の 2a<sup>2</sup>+2b<sup>2</sup>+2c<sup>2</sup> あるいは 2a<sup>2</sup>+2b<sup>2</sup>+c<sup>2</sup> が一番効いてきます。結局ほとんど 0 と 1 場合によっては 2 もありうるという感じになります。これをパターン分けして数え上げて最初にリストを作ってしまう、というコードが↓です。</p>
<pre class="brush: cpp">vector<string> fair = { "1", "4", "9", "121", "484" };
struct numeric_less
{
bool operator()(const string &s1, const string &s2) const {
return s1.size() < s2.size() ||
(s1.size() == s2.size() && s1 < s2);
}
};
void mygenerate(int len, const vector<pair<int,int>> &indices)
{
bool valid = true;
vector<int> v(len);
for(auto &val : indices) {
v[val.first * 2] += val.second * val.second;
if(v[val.first * 2] > 9) { valid = false; break; }
}
REP(i, indices.size()) {
for(auto j : IR<UI>(i+1, indices.size())) {
v[indices[i].first+indices[j].first] += 2 * indices[i].second * indices[j].second;
if(v[indices[i].first+indices[j].first] > 9) { valid = false; break; }
}
if(!valid) break;
}
if(valid) {
string s;
for(auto &val : v) {
s.push_back(val+'0');
}
fair.push_back(s);
}
}
void init_fair(size_t max_len)
{
const UI N = (max_len + 1) / 2 + 1;
REP(i_, N) {
int i = i_ + 1; // 1 -> (max_len + 1) / 2
if(i < 3) continue;
if(i & 1) { // odd
// 1xx0xx1 x can have 1 at most 6 positions
// 1.0.1
// 1.1.0.1.1
// 1.1.1.0.1.1.1
// 1.1.1.1.0.1.1.1.1
// 1xx1xx1 x can have 1 at most 6 positions
// 1.1.1
// 1.1.1.1.1
// 1.1.1.1.1.1.1
// 1.1.1.1.1.1.1.1.1
// 1xx2xx1 x can have 1 at most 2 positions
// 1.2.1
// 1.1.2.1.1
// 2.2
// 2.1.2
const int X = (i - 1) / 2;
// 2.2
mygenerate(2*i-1, { {0,2}, {2*X,2} });
// 1.0.1
mygenerate(2*i-1, { {0,1}, {X,0}, {2*X,1} });
// 1.1.1
mygenerate(2*i-1, { {0,1}, {X,1}, {2*X,1} });
// 1.2.1
mygenerate(2*i-1, { {0,1}, {X,2}, {2*X,1} });
// 2.1.2
mygenerate(2*i-1, { {0,2}, {X,1}, {2*X,2} });
for(auto ii : IR(1, X)) {
// 1.1.0.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {X,0}, {2*X-ii,1}, {2*X,1} });
// 1.1.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {X,1}, {2*X-ii,1}, {2*X,1} });
// 1.1.2.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {X,2}, {2*X-ii,1}, {2*X,1} });
}
for(auto ii : IR(1, X)) {
for(auto jj : IR(ii+1, X)) {
// 1.1.1.0.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {X,0}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
// 1.1.1.1.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {X,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
}
}
for(auto ii : IR(1, X)) {
for(auto jj : IR(ii+1, X)) {
for(auto kk : IR(jj+1, X)) {
// 1.1.1.1.0.1.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {X,0}, {2*X-kk,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
// 1.1.1.1.1.1.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {X,1}, {2*X-kk,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
}
}
}
} else { // even
const int X = i / 2;
// 1xxxx1 x can have 1 at most 6 positions
// 1..1
// 1.1..1.1
// 1.1.1..1.1.1
// 1.1.1.1..1.1.1.1
// 2.2
// 1..1
mygenerate(2*i-1, { {0,1}, {2*X-1,1} });
// 2.2
mygenerate(2*i-1, { {0,2}, {2*X-1,2} });
for(auto ii : IR(1, X)) {
// 1.1..1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {2*X-ii-1,1}, {2*X-1,1} });
}
for(auto ii : IR(1, X)) {
for(auto jj : IR(ii+1, X)) {
// 1.1.1..1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {2*X-jj-1,1}, {2*X-ii-1,1}, {2*X-1,1} });
}
}
for(auto ii : IR(1, X)) {
for(auto jj : IR(ii+1, X)) {
for(auto kk : IR(jj+1, X)) {
// 1.1.1.1..1.1.1.1
mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {2*X-kk-1,1}, {2*X-jj-1,1}, {2*X-ii-1,1}, {2*X-1,1} });
}
}
}
}
}
sort(RNG(fair), numeric_less());
#if 0
for(auto & val : fair) {
cout << val << endl;
}
#endif
}
UI solve(const pair<string, string> &iv)
{
auto it1 = lower_bound(RNG(fair), iv.first, numeric_less());
auto it2 = lower_bound(RNG(fair), iv.second, numeric_less());
UI result = it2 - it1;
if(it2 != fair.end() && *it2 == iv.second) ++result;
return result;
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
size_t max_len = 0;
vector<pair<string,string>> iv(cases);
for(auto & val : iv) {
cin >> val.first >> val.second;
max_len = max({max_len, val.first.size(), val.second.size()});
}
init_fair(max_len);
for(auto & val : iv) {
cout << "Case #" << &val - iv.data() + 1 << ": " << solve(val) << endl;
}
return 0;
}
</pre>
<p>で、どこでミスったかというと</p>
<pre class="brush: cpp"> sort(RNG(fair), numeric_less());
#if 0
for(auto & val : fair) {
cout << val << endl;
}
#endif
</pre>
<p>が、こうなってました。</p>
<pre class="brush: cpp">#if 0
sort(RNG(fair), numeric_less());
for(auto & val : fair) {
cout << val << endl;
}
#endif
</pre>
<p>ああああああああ。まぁ Qualification Round なので通ったからいいんですが。不用意な修正には気をつけろってことですね。</p>
<h3>Problem D. Treasure</h3>
<p>lexicographically smallest とか言われているのでこりゃ探索するしかないなってんで、どの chest を開いたかによって鍵の数も決まるので探索済みだったら枝刈りする形のコードが↓。これでも small input は通ります。あ、#include <boost/dynamic_bitset.hpp> の追加が必要です。</p>
<pre class="brush: cpp">deque<int> solve(const vector<int> &required, const vector<vector<int>> &got, set<dynamic_bitset<>> &visited, dynamic_bitset<>& open, vector<int> & keys)
{
if(visited.count(open)) return {};
if(open.count() == required.size()) return { -1 };
//cerr << "OPENED_COUNT: " << open.count() << endl;
REP(i, required.size()) {
if(!open[i] && keys[required[i]] > 0) {
//cerr << "OPEN: " << i << endl;
open.set(i);
--keys[required[i]];
REP(j, got[i].size()) {
++keys[got[i][j]];
}
auto t = solve(required, got, visited, open, keys);
if(t.size()) {
if(t.back() == -1) {
t.back() = i+1;
} else t.push_front(i+1);
return t;
}
REP(j, got[i].size()) {
--keys[got[i][j]];
}
++keys[required[i]];
open.reset(i);
}
}
visited.insert(open);
return {};
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI K, N; cin >> K >> N;
vector<int> keys(200);
REP(i, K) { UI t; cin >> t; ++keys[t-1]; }
vector<int> required(N);
vector<vector<int>> got;
REP(i, N) {
cin >> required[i]; --required[i];
UI t; cin >> t;
vector<int> got_(t);
for(auto &val : got_) {
cin >> val; --val;
}
got.push_back(got_);
}
dynamic_bitset<> open(N);
set<dynamic_bitset<>> visited;
cout << "Case #" << casenum+1 << ":";
auto result = solve(required, got, visited, open, keys);
if(result.size()) {
for(auto &val: result) {
cout << ' ' << val;
}
} else {
cout << " IMPOSSIBLE";
}
cout << endl;
}
return 0;
}
</pre>
<p>IMPOSSIBLE に対する時間がかかりすぎるので、鍵の数が足りない場合と相互(3つ以上含む)に持ち合っている場合を除外「しよう」としたのが↓コードです(※通りません)。@tanakh さん曰く</p>
<blockquote class="twitter-tweet" lang="ja"><p>D-largeは、何とかがんばれば、鍵開けが可能かどうかだけは線形時間で判定できるので、あとは前から順番に埋めていけば、Lexico最小の解が求まります。</p>— Hideyuki Tanakaさん (@tanakh) <a href="https://twitter.com/tanakh/status/323227473821171714">2013年4月14日</a></blockquote>
<blockquote class="twitter-tweet" lang="ja"><p>D問題、線形での判定は、グラフの連結性と、あとは鍵の数があってるかだけ確かめればおkです。</p>— Hideyuki Tanakaさん (@tanakh) <a href="https://twitter.com/tanakh/status/323228429631766528">2013年4月14日</a></blockquote>
<p>ということで、連結してないケース=相互に持ち合ってるケースのイメージなので方針としては間違って無かったようです。手書きメモ上ではグラフみたいなもの書いてたのに(時間もあるのに)適当実装してしまったのが駄目なところですね。</p>
<pre class="brush: cpp">deque<int> solve(const vector<int> &required, const vector<vector<int>> &got, set<dynamic_bitset<>> &visited, dynamic_bitset<>& open, vector<int> & keys)
{
if(visited.count(open)) return {};
if(open.count() == required.size()) return { -1 };
//cerr << "OPENED_COUNT: " << open.count() << endl;
REP(i, required.size()) {
if(!open[i] && keys[required[i]] > 0) {
//cerr << "OPEN: " << i << endl;
open.set(i);
--keys[required[i]];
REP(j, got[i].size()) {
++keys[got[i][j]];
}
auto t = solve(required, got, visited, open, keys);
if(t.size()) {
if(t.back() == -1) {
t.back() = i+1;
} else t.push_front(i+1);
return t;
}
REP(j, got[i].size()) {
--keys[got[i][j]];
}
++keys[required[i]];
open.reset(i);
}
}
visited.insert(open);
return {};
}
bool sanity_check(const vector<int> &required, const vector<vector<int>> &got, const vector<int> &keys_orig)
{
vector<int> req(200);
REP(i, required.size()) {
++req[required[i]];
}
bool flag = false;
REP(i, required.size()) {
vector<int> keys(keys_orig);
REP(j, required.size()) {
if(i != j) {
REP(k, got[j].size()) {
++keys[got[j][k]];
}
}
}
bool flag_one = true;
REP(j, keys.size()) {
if(req[j] > keys[j]) {
flag_one = false;
break;
}
}
if(flag_one) {
flag = true;
break;
}
}
return flag;
}
bool sanity_check2(const vector<int> &required, const vector<vector<int>> &got, const vector<int> &keys)
{
stack<int> q;
dynamic_bitset<> pushed(200);
dynamic_bitset<> open(required.size());
REP(i, keys.size()) { if(keys[i] && !pushed[i]) { pushed.set(i); q.push(i); } }
while(!q.empty()) {
int n = q.top(); q.pop();
REP(i, required.size()) {
if(required[i] == n && !open[i]) {
open.set(i);
for(auto j : got[i]) {
if(!pushed[j]) { pushed.set(j); q.push(j); }
}
}
}
}
return open.count() == required.size();
}
int main(void)
{
ios_base::sync_with_stdio(false);
UI cases; cin >> cases;
REP(casenum, cases) {
UI K, N; cin >> K >> N;
vector<int> keys(200);
REP(i, K) { UI t; cin >> t; ++keys[t-1]; }
vector<int> required(N);
vector<vector<int>> got;
REP(i, N) {
cin >> required[i]; --required[i];
UI t; cin >> t;
vector<int> got_(t);
for(auto &val : got_) {
cin >> val; --val;
}
got.push_back(got_);
}
dynamic_bitset<> open(N);
set<dynamic_bitset<>> visited;
cout << "Case #" << casenum+1 << ":";
if(sanity_check(required, got, keys) && sanity_check2(required, got, keys)) {
auto result = solve(required, got, visited, open, keys);
if(result.size()) {
for(auto &val: result) {
cout << ' ' << val;
}
} else {
cout << " IMPOSSIBLE";
}
} else {
cout << " IMPOSSIBLE";
}
cout << endl;
}
return 0;
}
</pre>
<h3>総評</h3>
<p>C-Large はせっかく合ってたのに感はありますが通過できればいいんです、うん。とにかく楽しかったです。Round 1A も頑張るぞ。</p>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-4756038822435223412012-12-15T15:35:00.002+09:002012-12-15T15:37:35.327+09:00Boost.Context on Cygwin<p>1.51.0 において Boost.Context がリリース入りしました。Boost.Context はコンテキスト切り替えのためのライブラリです。コンテキストの最も一般的な訳語は「文脈」ですが、この場合は実行中のアドレス、CPU のレジスタなど、実行時の状態情報とでもいうべきものです。(プリエンプティブ)マルチタスクは OS がこのコンテキスト情報を切り替えることで成立していますが、これを自前で切り替えられるようにするのが Boost.Context です。あるいは、setjmp/longjmp だと setjmp した時点に戻ることしかできませんが、longjmp した時に同時に setjmp が実行されその場所にまた戻ることが出来ると言っても良いかもしれません(スタックの取り扱いが違いますが)。 これが出来て何が嬉しいかというと、C# の yield みたいなことが実現できるわけですが、それはともかく。CPU のレジスタとか書いていることでお分かりかもしれませんが、Boost.Context は C/C++ の範囲では実現できません。ということでアセンブリ言語で実装されています。Windows だと MASM が要求されるのが面倒だったので gas に移植(というほどのこともないですが)し、Cygwin でビルドできるところまで到達したのですが、example の jump.cpp をコンパイル、動作させてみると、コンテキストを切り替えた先の文字列出力で詰まってしまいました。</p>
<pre class="brush: cpp; highlight: [22]">// Copyright Oliver Kowalke 2009.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <boost/assert.hpp>
#include <boost/context/all.hpp>
namespace ctx = boost::context;
ctx::fcontext_t fcm;
ctx::fcontext_t * fc1 = 0;
ctx::fcontext_t * fc2 = 0;
void f1( intptr_t)
{
std::cout << "f1: entered" << std::endl;
std::cout << "f1: call jump_fcontext( fc1, fc2, 0)" << std::endl;
ctx::jump_fcontext( fc1, fc2, 0);
std::cout << "f1: return" << std::endl;
ctx::jump_fcontext( fc1, & fcm, 0);
}
void f2( intptr_t)
{
std::cout << "f2: entered" << std::endl;
std::cout << "f2: call jump_fcontext( fc2, fc1, 0)" << std::endl;
ctx::jump_fcontext( fc2, fc1, 0);
BOOST_ASSERT( false && ! "f2: never returns");
}
int main( int argc, char * argv[])
{
ctx::guarded_stack_allocator alloc;
void * base1 = alloc.allocate(ctx::guarded_stack_allocator::default_stacksize());
BOOST_ASSERT( base1);
fc1 = ctx::make_fcontext( base1, ctx::guarded_stack_allocator::default_stacksize(), f1);
BOOST_ASSERT( fc1);
BOOST_ASSERT( base1 == fc1->fc_stack.sp);
BOOST_ASSERT( ctx::guarded_stack_allocator::default_stacksize() == fc1->fc_stack.size);
void * base2 = alloc.allocate(ctx::guarded_stack_allocator::default_stacksize());
BOOST_ASSERT( base2);
fc2 = ctx::make_fcontext( base2, ctx::guarded_stack_allocator::default_stacksize(), f2);
BOOST_ASSERT( fc2);
BOOST_ASSERT( base2 == fc2->fc_stack.sp);
BOOST_ASSERT( ctx::guarded_stack_allocator::default_stacksize() == fc2->fc_stack.size);
std::cout << "main: call start_fcontext( & fcm, fc1, 0)" << std::endl;
ctx::jump_fcontext( & fcm, fc1, 0);
std::cout << "main: done" << std::endl;
return EXIT_SUCCESS;
}
</pre>
<p>このコードは本来、</p>
<pre class="brush: text">main: call start_fcontext( & fcm, fc1, 0)
f1: entered
f1: call jump_fcontext( fc1, fc2, 0)
f2: entered
f2: call jump_fcontext( fc2, fc1, 0)
f1: return
main: done
</pre>
<p>と出力されて終了するのですが、main: call start ... の行だけ出力されて詰まってしまう状態です。実際にハイライトされている 22 行目で詰まっていたわけですがこれは Cygwin 内部の仕組みのせいでした。</p>
<p>規格に定義されているわけではありませんが、一般的に、ローカル変数(自動変数)、関数の引数などはスタックと呼ばれる領域に格納されています。関数の呼び出しがネストするごとにスタックは伸びていきます。setjmp/longjmp ならば戻るだけ、なので伸びた先のことは忘れてしまえばいいわけですが、コンテキスト切り替えによってまた戻ってくるためにはスタックの状態が保存されていなければなりません。ということで Boost.Context ではスタック領域自体を別に用意した領域に切り替えます。この時、OS 側で管理している情報である <a href="http://en.wikipedia.org/wiki/Win32_Thread_Information_Block">NT TIB(Thread Information Block)</a> のスタック情報(top と bottom)も切り替えています。一方、Cygwin ではスタックの底に cygtls というスレッド固有の情報を格納しており、NT TIB を経由して参照しています。このため、Boost.Context によるコンテキスト切り替えの結果、NT TIB が指すスタックの底に cygtls が存在しないことになり(恐らく排他制御に失敗して)詰まってしまっていたわけです。<br>
<a href="https://docs.google.com/drawings/pub?id=1yFlfYut0nxvoHr_NVVal6isUeHtarM1JElOl6-iddso&w=963&h=462"><img src="https://docs.google.com/drawings/pub?id=1yFlfYut0nxvoHr_NVVal6isUeHtarM1JElOl6-iddso&w=481&h=231"></a><br>
実際、f1(), f2() 内の出力をコメントアウトすると、正しく切り替え出来 main: done も出力されます(NT TIB が元のスタックの底を指すため)。コンテキスト切り替え先で Cygwin のシステムコールがまともに使えないのはペナルティが大きすぎるので、NT TIB のスタック情報を切り替えをしない版を作ってみたところ正しく動作しているようです(<a href="http://yak3.myhome.cx:8080/junks/index.html#cygwin.libboost">Boost.Context gas on Windows パッチ</a>)。<br>
<a href="https://docs.google.com/drawings/pub?id=1ofQ5iLPDWtnP8WykIJYbDLZkYagV-xwgWP9oJDoARm8&w=963&h=462"><img src="https://docs.google.com/drawings/pub?id=1ofQ5iLPDWtnP8WykIJYbDLZkYagV-xwgWP9oJDoARm8&w=481&h=231"></a><br>スタック領域のチェックをするだとかいったデバッグ系ツールと組み合わせられないでしょうが他は大丈夫だと思っているのですがどうでしょうか。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-46989270018594953992012-12-08T16:56:00.000+09:002012-12-15T13:53:10.782+09:00【C++ Advent Calendar 2012】 8日目 「C++ Compiler Farm の紹介」&「キャストの復習」<p>このエントリは <a href="http://partake.in/events/a02d7049-1473-4b69-b5ad-25ed416c5557">C++ Advent Calendar 2012</a> 8 日目の記事です。</p>
<p>C++ Advent Calendar 2012 というからには普通 C++ のネタを提供するものですが、一応、C++ 関連ではあるのですが言語仕様でもなければライブラリでもないネタです。それだけではなんなので一応小ネタとして「キャストの復習」という内容も書いてみます。</p>
<h3>C++ Compiler Farm の紹介</h3>
<p>既に一度 Twitter 上で流したネタではあるのですが、<a href="http://ccf.myhome.cx:5000/ccf.html">「C++ Compiler Farm」</a> というサイトを作ってみました。</p>
<p>C++ は言語仕様が複雑であり、かつ、標準実装や唯一の実装のようなものが存在しないこともあり処理系によって挙動がまちまちである、というのは C++er は身に染みて良く知っていることだと思います。それでは皆さんの周辺ではコンパイラは何種類くらい利用可能でしょうか?無償利用可能なコンパイラに限っても世の中に結構な数があるわけですがそんなにたくさん常用できる状態にはない、という人も結構いるのではないでしょうか? C++ Compiler Farm はオンラインで複数の C++ コンパイラによるコンパイル結果、実行ファイルの実行結果を確認できるサービスです。</p>
<p>以前 Twitter 上で流した時点ではコンパイル、実行結果の確認はできる、という状態でしたが、結果を後から参照することができませんでした。今回機能強化を果たし、<a href="http://ccf.myhome.cx:5000/result/1">http://ccf.myhome.cx:5000/result/1</a> のようなリンクで実行結果を後から参照することができるようになりました。これでコンパイラによって挙動が違う、などと言った時に他の人に結果を見せやすくなるんじゃないかな、と期待しています。</p>
<p>コンパイラ無選択状態でも実行可能だったり、全ての結果が保存されたり、編集できなかったりまだまだ低機能ですが利用者がちょっとでも居そうであればちょこちょこやっていこうかと思っています。なお関連ソースコードは <a href="https://github.com/yak1ex/ccf">https://github.com/yak1ex/ccf</a> で公開しています。</p>
<p>C++ Advent Calendar で紹介しておきながらあるまじきことですが、ほとんど Perl で実装されています。なので概要だけ構成を説明しておくと以下の図のような構成になっています。</p>
<img src="https://docs.google.com/drawings/pub?id=11qBHxAOPJZs61YvagIZSWg80Hwx9cTaf5E0_uSOGmVw&w=485&h=318">
<p>AWS EC2 上で Windows / Linux サーバ Micro instance 各1台。それぞれでコンパイルサーバが実行されており、Web サーバは Linux 側。ブラウザ上の Javascript と協調しながら処理する感じです。サーバ側では非同期処理フレームワーク AnyEvent を使っていますので、C++er としては Boost.Asio とかで書けると格好いいところなんですが。サンドボックス部分だけ、Google Chrome のオープンソース実装である Chromium の C/C++ コードを一部修正して使用しています。これで system("rm -rf /"); とか入力されても問題ないようになっています(<a href="http://ccf.myhome.cx:5000/result/7">http://ccf.myhome.cx:5000/result/7</a>)。……そのはず、です。Windows 側はメッセージなしで黙って無視される形ですね。実行時間、使用メモリについても制限をかけています。相変わらず Amazon Web Services 無料範囲内での運用で、使用資源を絞った状態ですが以前よりはちょっと緩めました。この辺は調整だと思っていますので使用実績が増えれば考えるための材料も増えるかと思っています。</p>
<p>「C++ Compiler Farm」を紹介させて頂きました。皆様の C++ life に少しでも役立てば幸いです。</p>
<h3>キャストの復習</h3>
<p>ということで小ネタ「キャストの復習」です。最初に言っておきますが、規格上どうか、という話であって、実装上は概ね変わらないとかそういう割と役に立たない話になります。また、アラインメントについて省略したり正確な表現でなかったりします。</p>
<p>さて、C++ キャストは以下の 4 種類あります。</p>
<ul>
<li>const_cast
<li>dynamic_cast
<li>reinterpret_cast
<li>static_cast
</ul>
<p>このうち const_cast は const 外し、dynamic_cast は安全なキャストであるかどうかを判定できる、という点で位置づけは割と明快です(dynamic_cast の使いどころはどこか、というのはそれはそれで議論になりそうですが)。ということでたまに使い分けで議論になる reinterpret_cast と static_cast について、特にポインタの場合について掘り下げてみようと思います。</p>
<p>が、その前に C-style キャストについても確認しておきましょう。C++ においては C-style キャスト (type)value は以下の C++ キャストとして解釈可能なもののうち先にあるものと解釈されます(14882:2011 5.4p4)。</p>
<ul>
<li>const_cast 1回
<li>static_cast 1回
<li>static_cast 1回 + const_cast 1回
<li>reinterpret_cast 1回
<li>reinterpret_cast 1回 + const_cast 1回
</ul>
<p>つまり文脈によってどのように解釈されるかが変わります。</p>
<p>C 言語において割と暗黙のうちに仮定されているんじゃないかという前提として、ポインタのキャストでは指す位置は変わらない(値は変わらず解釈が変わる)、というものがある気がします(注:C 言語においてもchar* への変換以外規格上その保証はありません(9899:1999, 9899:2011 6.3.2.3p7)。ついでに strict aliasing rule 的に char* 系以外の別の型へのポインタ経由でアクセスすると未定義動作です(9899:1999, 9899:2011 6.5p7)。一方で、C++ においてはポインタのキャストでその値(指している場所)が変わる場合が有り得ます。</p>
<p>以下のような継承がされているクラス群がある場合、</p>
<pre class="brush: cpp">struct A { int n; };
struct B { int n; };
struct C : A, B { int n; };</pre>
<p>C 型のオブジェクト内に A 型、B 型のオブジェクトが含まれる形となり、かつ先頭位置を C 型と共有可能なのは A 型か B 型かいずれか一つしかないことになります。規格上定義されていませんが典型的にはメモリレイアウトは以下の図のようになります。</p>
<img src="https://docs.google.com/drawings/pub?id=1uSoexBdiIblN9DDTAiNdf0EYjt2NVG7fyTUtqr1r90M&w=339&h=133">
<p>図のようにA型、B型の順に並んでいるとして、C* を B* に static_cast すると C の中にある B の先頭を指すことになり、つまり、指す位置が変わります。逆に B* を C* に static_cast しても指す位置が変わります。この場合、もともと C 型のオブジェクト中の B 型オブジェクトを指していない場合などは不正な位置を指すことになります。つまりこのキャストはいつでも安全とは言えないのですが、static_cast はstandard conversion として規定されている型変換の逆方向のキャストもできると規定されている(14882:2003 5.2.9p6, 14882:2011 5.2.9p7)ため一律コンパイル可能です(もちろん不正な位置を指す場合には未定義動作ですが)。つまり「static_cast ならば安全なキャストだ」というわけではありません。</p>
<p>では static_cast の立ち位置とはなんでしょう?上の段落で単なる「キャストする」ではなく「static_cast する」と明示したことに気付かれたでしょうか?C++03 以前では、reinterpret_cast でのポインタのキャストについてはヌルポインタがヌルポインタのままであること(14882:2003 5.2.10p8)、T1* → T2* → T1* で元に戻ること(14882:2003 5.2.10p7)以外は未規定(unspecified)であり可搬性のあるコードを書くならば reinterpret_cast は使うな、が基本でした。つまり、上のような B* → C* あるいは C* → B* についても(続けてやれば元に戻ること以外) reinterpret_cast の結果について言えることはありませんでした。つまり(未定義動作の場合もあるけど)結果が規定されている static_cast と規定されていない reinterpret_cast という位置づけだった訳です。</p>
<p>C++03 以前において例えば char* を unsigned char* にキャストする(規格上)可搬性のある方法は、void* を経由して static_cast する方法でした。</p>
<pre class="brush: cpp">
char *pc;
// unsigned char* upc = static_cast<unsigned char*>(pc); // COMPILE ERROR
unsigned char* upc = static_cast<unsigned char*>(static_cast<void*>(pc));
</pre>
<p>void* への変換は指す位置が変わらないという規定があります(14882:2003 4.10p2)。一方、void* へ変換して元の型に戻すと同じ場所を指すという規定もあるため(14882:2003 5.2.9p10)、void* からのキャストも指す位置は変わらないことになります。一方、以下のコードもコンパイルは通りますが、</p>
<pre class="brush: cpp">
char *pc;
unsigned char* upc_bad1 = (unsigned char*)pc;
unsigned char* upc_bad2 = reinterpret_cast<unsigned char*>(pc);
</pre>
<p>この C-style キャストは(static_cast ではキャストできない変換なので)前述の通り reinterpret_cast として解釈されます。これも前述の通り reinterpret_cast では結果が保証されないためこのコードは可搬性がありません(pc と upc_bad* で同じ位置を指している保証がない)。</p>
<p>というのが、C++03 以前の話。C++11 では reinterpret_cast の規定が変わりました(14882:2011 5.2.10p7)。</p>
<blockquote>An object pointer can be explicitly converted to an object pointer of a different type. <b><u>When a prvalue v of type “pointer to T1” is converted to the type “pointer to cv T2”, the result is static_cast<cv T2*>(static_cast<cv void*>(v)) if both T1 and T2 are standard-layout types (3.9) and the alignment requirements of T2 are no stricter than those of T1, or if either type is void.</u></b> Converting a prvalue of type “pointer to T1” to the type “pointer to T2” (where T1 and T2 are object types and where the alignment requirements of T2 are no stricter than those of T1) and back to its original type yields the original pointer value. The result of any other such pointer conversion is unspecified.</blockquote>
<p>太字下線部分が大体追加された規定で、<b>standard-layout type へのポインタ間の場合、</b>void* を経由する static_cast 2回と等価、つまり↑で可搬性がある方法としていたものになります。standard layout type は規格の範囲で(パディング等はあるけど)メモリレイアウトが決まる型のことです。char, unsigned char については standard-layout type なので、C-style キャストの場合も含めて↑で可搬性がないとしていたコードが可搬性があることになりました。世の人々も指す位置が変わらないと思って reinterpret_cast を使ってるし実装も他に選択肢がなくまず間違いなくそうなってるし、という理由で規定が変更されています(<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#658">DR658</a>)。もともとコードの見た目でキャストの位置づけが分かるように、という意図で C++ キャストが分けられていたはずなのですが、まぁ現実には勝てない、というところなのでしょうか。</p>
<p>さて、これを B*, C* の例に適用すると、クラスについては、メンバ・基本クラスに非 standard-layout class がないこと、メンバに参照なし、仮想関数・仮想基本クラスなし、継承階層中非静的メンバをもつクラスは自分自身を含めて高々一つ、が standard layout class となるため、B は standard-layout type ですが、C は standard-layout type ではありません。結果、reinterpret_cast についてはやっぱり何も言えない、ということになります。実際には C++03, C++11 いずれの実装であっても指す位置が変わらない、というのが普通の実装でしょう(指す位置を変える積極的な理由がない)。ということを示そうとしたのが <a href="http://ccf.myhome.cx:5000/result/12">http://ccf.myhome.cx:5000/result/12</a> です。いずれの処理系においても static_cast では指す位置が変わる場合があり、reinterpret_cast では指す位置が変わっていません。なおこのコードでは reinterpret_cast によるポインタと整数との変換をしています。これ自体も(整数のサイズが十分であれば)一周回れば元に戻る、以外はどのような変換が実施されるかは処理系依存です(14882:2003, 14882:2011 5.2.10p5)(そしてアドレスをそのまま整数値とする実装が多いでしょうし、このコードは少なくとも変換が単射であることを期待したコードですので厳密には可搬性はありません)。個人的にはこのポインタと整数の相互変換が C++03 以前で reinterpret_cast を使うべき唯一のケースだと思っています。</p>
<p>さて、「キャストの復習」と題して、static_cast、reinterpret_cast によるポインタの変換について、C++11 での変更を含めてお送りしました。今後 C++ コミュニティにおいて reinterpret_cast の位置づけがどのようになるのか(一部の異なるポインタ型の変換について正当な手段とされるのか、あくまでも処理系依存や未規定なキャストについてのみ使うべきとされるのか)、興味深いところではあります。</p>
<h3>まとめ</h3>
<p>C++ Advent Calendar 2012 8日目として、「C++ Compiler Farm の紹介」と「キャストの復習」をお送りしました。C++ Advent Calendar 2012 明日の担当は <a href="https://twitter.com/Flast_RO">@Flast_RO</a>さんです。お楽しみに→<a href="http://flast.hateblo.jp/">【にゃははー】</a></p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-68762697083151583292012-09-30T23:58:00.001+09:002012-09-30T23:58:27.272+09:00YAPC::Asia Tokyo 2012 参加メモ<p>ブログ書くまでが YAPC::Asia らしいので。/.-j にしようか迷ったけど一応こちらで。</p>
<p>1日目、2日目で参加。1日目は新幹線が 80 分くらい遅れたため残念ながら Larry 氏のセッションは聞けず、その後から参加。YAPC 参加者は Web 界隈の人が多いんじゃないかと思っているが、そういう意味ではそもそも日常業務的に Perl どころがプログラミングも(基本)しないという点で特異な参加者な気もする(1日目は年休取得して参加)。ということで Web サービス寄りよりかは Perl 本体寄りのセッション選択、のはず。以降、各セッションの雑多なメモとか感想とか。</p>
<h1>一日目</h1>
<h3>Acmeism, Pegex and CoffeeScript on CPAN</h3>
<p>40 分の枠に収まらなかった感じ。もうちょいちゃんと聞きたかった。</p>
<h3>リアルタイム通知システムの舞台裏</h3>
<p><a href="http://ccf.myhome.cx:5000/ccf.html">C++ Compiler Farm</a> みたいなものを作っていて通知ではなくバックエンドのコンパイルサーバについてだがこの辺の管理(どのサーバに投げたか)とかどうしようというのと通ずるものがある気がした。メッセージキュー(RabitMQ)で解決したみたいだが、CCF では S3 がその位置に来そう。</p>
<h3>Perl初心者が作ったサーバ運用ツール</h3>
<p>英語での発表。運用ツールそのものについて自分に知見がないけど、テストがある、というのが重要なところか。ただこれ、テスト可能なように設定を綺麗に分離してやるというか、role と blueprint との関係が重要な気がする。</p>
<h3>GitHubを使った開発とデプロイ</h3>
<p>丁度 Perl モジュールの fork とかし始めたところだったのでそういう話なのかなと(勝手に)期待していたけどそうではなく普通にプロジェクトの中心リポジトリとして Github を使う感じだった。</p>
<h3>Distributed Job System. Clutch</h3>
<p>中央サーバを必要とせずクライアント側で振り分ける分散ジョブシステム、だろうか。多分構成次第? 多対多になるなら間に中央管理サーバを置いた方が楽になる気がするし、振り分け先が動的に変化するケースだと難しくなったりするんじゃないだろうか。</p>
<h3>DBD::SQLite: Recipes, Issues, and Plans</h3>
<p>正直一番実用的だったかもしれない。解析の仕方から考えなきゃならないデータに対してとりあえず DB に突っ込んで SQL で色々料理してみるというのはかなり強力なスキームだと思っているが、その上で SQLite は強い味方である。で、DB へのデータ投入とか SQL が苦手な処理をする時に一旦外でやろうとする場合などで DBD::SQLite はお世話になりまくりである。bulk insert は自分も prepare/分割commit/各種pragma on でやってたのでお墨付きをもらった感が。複数レコード insert は今度試してみたい。その他、DBD::SQLite ユーザーは一度軽く資料を眺めておくといいんじゃないかと思う。</p>
<h3>Profiling memory usage of Perl applications</h3>
<p>TreeMap によるメモリ使用量の視覚化デモが格好良かった。使われていたのは <a href="http://thejit.org/">JavaScript InfoVis Toolkit</a> だろうか。Interactive な視覚化をやるのに Javascript を使うというのは環境も(あまり)選ばないし便利な気がする。</p>
<h3>平均レスポンスタイム50msをPerlで捌く中規模サービスの実装/運用</h3>
<p>実際の内容についてはどうこう言えることはないのだが、前振りのアドテック業界について、が非常に分かりやすい導入だったと思う。</p>
<h3>Perlアプリケーションのベンチマークとプロファイリング</h3>
<p>↑のセッションでもそうだがとにかく計測すること、視覚化することがまず重要か。CCF なんかはとりあえず立ち上げてるだけなので試せるといいなぁ。</p>
<h3>LT</h3>
<p>相変わらずネタ満載。</p>
<h1>二日目</h1>
<h3>「新しい」を生み出すためのWebアプリ開発とその周辺</h3>
<p>今回のベストトーク賞受賞セッション。企画の部分は、Web アプリに限らず何か作ろうと思ってる万人に得るものがあるのではないかと。実装については枯れたものを使えば十分というあたり? 11月末~12月発売予定という「Webサービスのつくり方」は期待大。</p>
<h3>Padre - The Perl IDE for Normal People</h3>
<p>Emacs ユーザーと Vim ユーザーが聴取者の大半というのが印象的。自分も Emacs も Vim もプログラミングに使わないけど IDE も(ほとんど)使わないという点で Normal People からは外れてるわけだけど。Perl ユーザーが拡張とかしやすいのは Perl で書かれた IDE というのはそうかもしれないけど Perl のコアユーザー層が IDE 使ってないわけで。Eclipse なんかは企業からの後押しが大きかったわけだし、一般ユーザー層への拡大の需要というかそういうのがないと難しいかもしれない。<p>
<h3>Perl 今昔物語</h3>
<p>日記をさらってみたところ自分は 2008 が初参加の模様。この手のイベント自体が初参加だった。2010 は 2 日目だけ参加、2011 はキャンセル(海外出張)。参加してない部分のタイムテーブルを見ると聞いときゃ良かったというのが結構ある。今後はもう少し参加に貪欲になってもいいかもしれない。内容としてはPerl で書く必然性が薄れてきた、みたいなことを言われていたのが印象的だった。他のセッションの内容にもその辺が出てきているような気がする。</p>
<h3>Perl と SQL のいろいろ</h3>
<p>DBI/DBD についての分かりやすいチュートリアル。周辺モジュールの簡単な紹介もあって参考になった。質問タイムでプレースホルダの強制ができないんで O/R マッパー使ってるみたいなコメントがあって、プレースホルダの使用くらいプログラマとして最低限度の常識じゃないのかと思ったけど現実はそうもいかないんだろうなぁというのが悲しいところ。</p>
<h3>シリコンバレーと世界のPerlエンジニア</h3>
<p>川崎さんがアクティブ過ぎて眩しい。「10年後に食える仕事 食えない仕事」から引用されてた「グローカル」「ジャパンプレミアム」「無国籍ジャングル」「重力の世界」っていうのは興味深い。元々の本だとプログラマは「重力の世界」みたいだけど日本の適当な開発要求とのブリッジングという位置では立ち位置はありそう。それはそれでしんどそうだけど。</p>
<h3>Perlで始める!初めての機械学習の学習</h3>
<p>メモ見たら PRML 同人誌とだけ書いてあったw。とりあえず手に入れたいと思う。perl-kinect は面白そうなので公開されないかなぁ。</p>
<h3>Perl入学式をやってみた!</h3>
<p>期待していなかったのだが(ごめんなさい)、熱い思いを感じられるいいセッションだったと思う。「ハードルを下げることを重視する」「継続して参加できる環境を作る」というのは他のイベント主催の人も参考にできるかもしれないが、このレベルまで頑張るのは相当大変なことだと思う。あと、Perl 入学式参加者の Perl のわかりにくかったところとして、リファレンス(-> が省略できる場合がある)、コンテキストの概念、ファイルハンドルの , の省略、辺りが挙がってたのはそうだよなぁ、と思わざるを得ない。慣れてくると大丈夫だし逆に楽に書ける要因になったりもするんだけど、場合に応じてうまい具合に挙動が変わる、は、むしろ初めての人にはわかりにくい、と。</p>
<h3>Performance Profiling with Devel::NYTProf</h3>
<p>他のセッションでも言われていたけど、まず計測しろ、と。あと、目標達成したらそれ以上余計な事しない。局所的な変更から積み上げる。</p>
<h3>LT</h3>
<p>相変わらずネタ満載。</p>
<h3>How Perl Changed My Life & Closing</h3>
<p>総括感想も含めて。なんだろう、所詮 Perl はプログラミング言語の一つな訳だけど、TMTOWTDI に代表されるその精神というかそういうのがコミュニティにも有ってそれだけ懐が深いというか、Closing で牧さんが the most welcoming conference みたいなこと書いてたけどそういうのが有るんじゃないかな、と。忘れていたけど自分としては初参加のイベントが YAPC::Asia 2008 だった訳で、そこから色々参加(だけは)するようになったのを考えるとそれなりに大きな転機だったのかもしれないとも思う。そういう意味で Perl ってのは自分の中で結構大きい割合を占めているかもしれない。実際「Perl は生活、C++ は趣味」という感じで技術ネタは C++ が多いけど実際書いてたり日常使ってるものは Perl の方が多かったりするし。今現時点で Perl を選ぶ理由ってのはそんなにないのかもしれないけど、でも自分は Perl が好きなんだなぁ、と思う。で、スピーカーの人にはせっかくの YAPC なので別に Perl べったりの内容にする必要はないと思うんだけどもう少し Perl 寄りの発表をして欲しいなぁという気持ちもあったり。まぁとにかく来年も参加したいと思う。</p>
yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-53380225177571031072012-09-08T11:02:00.001+09:002012-09-08T11:02:54.727+09:00小ネタ: Perl の警告: Deep recursion on subroutine ...<p>Perl では再帰呼び出しのネストが深いと警告してくれる機能がある。定石的に <code>use strict; use warnings;</code> していれば有効になっている。</p>
<pre class="brush:perl">use warnings;
sub dfs {
if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);</pre>
<pre class="brush:text">Deep recursion on subroutine "main::dfs" at ... line 3.</pre>
<p><a href="http://perldoc.perl.org/perldiag.html#Deep-recursion-on-subroutine-%22%25s%22">perldiag</a> には "unless you're writing strange benchmark programs, in which case it indicates something else." などと書いてあったりするのだが、閾値が 100 であるためちょっと大きめのグラフに対して再帰で DFS かけたりしたら余裕で突破したりするのである。警告を抑制したい場合、Perl の警告はカテゴリ分けされているため再帰に関する警告だけオフにしてやればいい。</p>
<pre class="brush:perl">use warnings;
no warnings 'recursion';
sub dfs {
if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);
</pre>
<p>が、これだと全体で警告がオフになってしまう。Perl の警告制御は <a href="http://perldoc.perl.org/perllexwarn.html"><b>lexical scope</b></a> である。これは限定した部分で警告をオン・オフできるということだが、</p>
<pre class="brush:perl">use warnings;
sub dfs {
if($_[0] < 101) {
no warnings 'recursion';
dfs($_[0]+1);
} # End of the effect of no warnings
}
dfs(0);
</pre>
<p>もう一つ、dynamic scope ではない、ということも意味している。つまり、以下では警告は抑制されない。</p>
<pre class="brush:perl">use warnings;
sub dfs {
if($_[0] < 101) {
dfs($_[0]+1);
}
}
no warnings 'recursion';
dfs(0);
</pre>
<p>実際に deep recursion が発生するのは dfs(0); の実行中じゃないかと思ってしまうのだが、字面上(lexical)は 4 行目の dfs 呼び出しで発生するからだ。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-3458661734852107702012-09-04T00:17:00.001+09:002012-09-04T00:17:55.633+09:00Variadic Template にまつわる Workaround<p>C++11 は確かに便利、なのだが現状はまだ実装が十分と言えず回避手段(workaround)を取らざるを得ない場合がある。の割には余りそういう説明を見ない、ということでせっかく書いたのでメモってみる。まぁ Boost のソースコードの中にたくさん埋まっているのだろうし、ひょっとしたら C++er は息をするように workaround が書ける人種なのかもしれないが、そこはそれ。</p>
<h3>sorry, unimplemented: use of ‘type_pack_expansion’ in template</h3>
<pre class="brush:c++">#include <utility>
struct B { int operator()(int n) const { return n; } };
template<typename C>
struct A {
#if __GNUC__ == 4 && (__GNUC_MINOR__ <= 5 || __GNUC_MINOR__ == 6 && __GNUC_PATCHLEVEL__ == 0)
template<typename ... Args>
struct deduce {
typedef decltype(C()(std::declval<Args&&>()...)) type;
};
template<typename ... Args>
typename deduce<Args...>::type operator()(Args && ... args) const
{ return C()(std::forward<Args>(args)...); }
#else
template<typename ... Args>
// sorry, unimplemented: use of ‘type_pack_expansion’ in template
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48292
auto operator()(Args && ... args) const -> decltype(C()(std::forward<Args>(args)...))
{ return C()(std::forward<Args>(args)...); }
#endif
};</pre>
<p>このエラーメッセージが出るのは恐らくこの場合には限らないと思うのだが、type pack (Args ... みたいな展開)を tailing return type 中で使った場合。GCC bugzilla にも書いてある通り、別のクラスに切り出すことで回避できる。@iorate さんの記事(<a href="http://d.hatena.ne.jp/iorate/20110612/1307902555">[C++][Boost] C++ で一般化された on を書く</a>)にも workaround の方法を含め書かれている。後は、GCC 4.6.1 から直っている、という情報くらいだろうか。</p>
<h3>sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list</h3>
<pre class="brush:c++">#include <boost/fusion/include/vector.hpp>
#include <boost/fusion/adapted/mpl.hpp>
#include <boost/fusion/include/as_vector.hpp>
#include "variadic_bridge.hpp"
template<typename ... Args>
struct C {
#if __GNUC__ == 4 && __GNUC_MINOR__ <= 6
typename boost::fusion::result_of::as_vector<
typename yak::util::variadic_to_vector<Args...>::type
>::type v;
#else
// sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39653
boost::fusion::vector<Args...> v;
#endif
};</pre>
<p>こっちはエラーメッセージを日本語対象でググっても合っているものは tweet 1件しかヒットしない。……みんな困ってそうなものなのだが。variadic な template parameter を非 variadic な template に渡せない、というものだ。自作ヘルパ <a href="https://github.com/yak1ex/cpp_stuff/blob/master/variadic_bridge.hpp">variadic_bridge.hpp</a> を使って variadic な template parameter を MPL vector に変換して、さらに boost::fusion::vector に変換している。まぁ MPL vector まで持って来られれば後はどうとでもなるとは思うが、一応、固定長引数として Metafunction Class に渡す variadic_to_fixed も用意はしてある。こっちは GCC 4.7.0 から修正。</p>
<h3>まとめ?</h3>
<p>そもそも <a href="http://msdn.microsoft.com/library/vstudio/hh567368">VC は 2012 でも variadic template 対応してねーよ</a>、という時点で PP するしかないという話なのが悲しいところ。</p>
<p>しかし、CSS はブラウザバグとその対処、みたいなものが結構見つかるのだが C++ についてはそういうまとめみたいなものはないのだろうか。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-81614124809166745852012-09-02T13:48:00.002+09:002012-09-03T09:06:18.376+09:00(今更) C++ で拡張メソッド<p>Transactional Memory について予告をしておきながら別ネタ。何で実装しようと思ったのかそのきっかけを忘れてしまっているが、今更 C++ で拡張メソッドである。func(a, x) のようにメンバ関数外のものが a.func(x) で呼べるというやつである。まぁ、「今更」というくらいであって既にやってる方は色々いるわけだが。<a href="http://d.hatena.ne.jp/faith_and_brave/20080529/1212051468">@cpp_akira (faith_and_brave) さん (2008年)</a>、<a href="http://eral.blog.eonet.jp/default/2009/02/c-d55f.html">じくよろさん(でいいのだろうか?)(2009年)</a>、<a href="http://gimkondo.blog98.fc2.com/blog-entry-4.html">@gim_kondo さん(2011年)</a>などが作られているわけである。</p>
<p>もちろん C++ 自体には拡張メソッドは存在しないのでそれっぽいものを実現する仕組みを自前で作ることになるのだが、基本的に C++ で拡張メソッド風なものを実装しようとした場合、拡張するメソッド(関数)以外に大体 3 つの構成要素が必要だと思われる。</p>
<ol>
<li>対象のオブジェクト、あるいは、引数を保持するオブジェクト(以下ラッパと表記)
<li>上記ラッパを作成、値を紐付けする仕組み(以下ラッパ束縛と表記)
<li>紐付けされなかった方と結びつけて実際の呼び出しを行う仕組み(以下ラッパ呼び出しと表記)
</ol>
<p>これで先の方の実装について整理するとこんな感じだろうか。じくよろさんの実装は最終的にフリー関数へ転送しているが「func(a, x) を」という形式に拘らなければ関数オブジェクト内でそのまま拡張メソッドの内容を実装してしまえばいいのでそのように実装した場合として記述している。</p>
<table border="1">
<tr><th>実装</th><th>ラッパ</th><th>ラッパ束縛</th><th>ラッパ呼び出し</th></tr>
<tr><td>@cpp_akira さん</td><td>拡張メソッドの内容を表す関数オブジェクト内に引数も保持</td><td>コンストラクタ</td><td>operator| のオーバーロード(任意の1引数関数オブジェクトを受ける)</td></tr>
<tr><td>じくよろさん</td><td>拡張メソッドの内容を表す関数オブジェクト内に引数も保持</td><td>コンストラクタ</td><td>operator, のオーバーロード(関数オブジェクト限定)</td></tr>
<tr><td>@gim_kondo さん</td><td>拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトへの this ポインタを保持</td><td>対象オブジェクトへのメンバテンプレート埋め込みとマクロ置換によるコンストラクタ呼び出し</td><td>関数オブジェクトの呼び出し</td></tr>
</table>
<p>@gim_kondo さんの実装は . (ドット演算子)で呼び出せるようになっているが拡張メソッド呼び出し側でのマクロ置換発生は代償としてちょっと evil だと思われる。この判断をした時点で基本的に演算子オーバーロードで実装ということになるのだが、今回選んだ演算子は ->* である。ほとんどの C++er は使ったことがないだろうと思われる、というかひょっとしたら存在を知ってる人すら少ないかもしれない。通常の使い方は以下のような形である。</p>
<pre class="brush:c++;highlight:[7]">struct A { void func(void) {} };
int main(void)
{
void (A::*mp)(void) = &A::func;
A a, *pa = &a;
(pa->*mp)();
return 0;
}</pre>
<p>つまりメンバないしメンバ関数へのポインタを参照するためのものである。とりあえず括弧の付け方に注意。知らないとまず間違えると思う。とりあえずこれがなくて困るとは普通ならない(そもそも普通の使い方ならポインタに対して使う)し、メンバアクセスのための演算子なので拡張メソッドとしては意味は近いはず、ということから選定。</p>
<p>で、拡張メソッド的なものが作れるというのは分かっている上でなぜまた<strike>(特に需要もないのに)</strike>別に作るのか。↑で書いたとおり、C++ で拡張メソッドを作ろうとすると本来の拡張メソッドだけでなく他の仕組みも必要になるわけでそれが面倒い。できるだけ拡張メソッド本体以外の余計な部分は勝手に作成させたい。で作ってみたのがこんな感じ。内部実装は <A href="https://github.com/yak1ex/cpp_stuff/blob/master/extender.hpp">https://github.com/yak1ex/cpp_stuff/blob/master/extender.hpp</a> にある。</p>
<pre class="brush:c++">#include <iostream>
#include "extender.hpp"
namespace test { struct A { int n; }; }
namespace ext {
DEFINE_EXTENDER1(test::A, func1, {
typedef test::A& result_type; // MUST follow result_of protocol
result_type operator()(test::A& a, int &n) const {
std::cout << "int&" << std::endl;
return a;
}
result_type operator()(test::A& a, const int &n) const {
std::cout << "const int&" << std::endl;
return a;
}
});
DEFINE_EXTENDER2(test::A, func2, {
typedef test::A& result_type; // MUST follow result_of protocol
result_type operator()(test::A& a, int &n) const {
std::cout << "int&" << std::endl;
return a;
}
result_type operator()(test::A& a, const int &n) const {
std::cout << "const int&" << std::endl;
return a;
}
});
}
int main(void) {
using ext::func1;
using ext::func2;
test::A a = { 0 }; int n = 0;
((a->*func1)(1)->*func1)(n); // Cascading but unintuitive
// NOTE: different from ordinary operator semantics/precedence
a->*func2(1)->*func2(n);
return 0;
}</pre>
<p>実行結果</p>
<pre class= "brush:text">const int&
int&
const int&
int&</pre>
<p>g++ 4.[5678] それぞれで -std=c++0x 有無両方で動作を確認している(いくつか workaround も入っている)。通常の演算子の優先順位の意味論に従ったのが EXTENDER1 の方、使いやすさを優先したのが EXTENDER2。まぁ普通は EXTENDER2 の方だと思う。使う側としてはほぼ書きたい拡張メソッドの内容部分のみだけで実現できている、と言っていいと思う。マクロにしてあるが↓なので直書きでもそんなに変わらない。なお、上記の例では 1 引数同士で const の違いだけでオーバーロードしているが、任意の型で引数の数が違っている場合でもそのまま operator() を書けばオーバーロード可能である。</p>
<pre class="brush:c++">#define DEFINE_EXTENDER1(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender1<BOOST_PP_CAT(name, _functor), target> \
__VA_ARGS__ name
#define DEFINE_EXTENDER2(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender2<BOOST_PP_CAT(name, _functor), target> \
{ \
struct _ __VA_ARGS__; \
} name</pre>
<p>内部実装について簡単に説明すると、<a href="Curiously recurring template pattern">CRTP</a> + <a href="http://en.wikipedia.org/wiki/Barton%E2%80%93Nackman_trick">Barton Nackman trick</a> を使ってラッパと演算子を定義している形。上表と同じ形で書くと次のようになる。</p>
<table border="1">
<tr><th>実装</th><th>ラッパ</th><th>ラッパ束縛</th><th>ラッパ呼び出し</th></tr>
<tr><td>EXTENDER1</td><td>拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトも保持</td><td>operator->* のオーバーロードで関数オブジェクトを返す</td><td>関数オブジェクトの呼び出し</td></tr>
<tr><td>EXTENDER2</td><td>引数を保持するオブジェクトを関数オブジェクトと別に用意</td><td>operator() のオーバーロードでラッパを返す</td><td>operator->* のオーバーロード(ラッパ限定)</td></tr>
</table>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-61132923860483183572012-08-04T20:01:00.002+09:002012-08-04T20:01:34.798+09:00LL Decade 「君ならどう書く Online」 で書いたコード<p>本日(8/4)開催された、LL Decade では<a href="http://ll.jus.or.jp/2012/doukaku-online-main.html">「君ならどう書く Online」</a>という企画がありました(問題の内容はリンク先参照)。14:00 までという短い時間と告知がそれほど強いものではなかったこともあってか参加者は 14 名(+締め切り以降10名)(間違ってるかも)だったそうですが、おかげで商品をゲットすることが出来ました。問題発表前は C++ Template Meta Programming で書いて「コンパイルの必要もない Lightweight です(キリッ」とかやろうかと思ったのですが、文字列の validation ということで断念しました。で、順当に Perl で書いた訳ですがせっかくこういう場で書くんだから多少のひねりが欲しいところです。という訳で書いたのが以下のコード。文字列処理ということで正規表現さんにお出まし願ったわけですが、普段使わない機能を使ってみました。</p>
<pre class="brush:perl; highlight: [9,10,18,25]">#!/usr/bin/perl
# regexp 内でそれなりに頑張る
use utf8;
use strict;
use warnings;
local $/; # slurp
my $t = <STDIN>;
$t =~ s/^(
(?<ipv4>(?&ipv4_))|
(?<ipv6>(?&ipv6_))|
(?<mac>(?&mac_))|
(?<any>.*)
)$
|(?<spc>\s+)
(?(DEFINE)
(?<ipv4_1>1[0-9]{2}|2([0-4][0-9]|5[0-5])|[1-9]?[0-9])
(?<ipv4_>(?:(?&ipv4_1)\.){3}(?&ipv4_1))
(?<ipv6_1>[1-9a-fA-F][0-9a-fA-F]{0,3}|0)
(?<ipv6_>(?:(?&ipv6_1):){7}(?&ipv6_1))
(?<mac_1>[0-9a-fA-F]{2})
(?<mac_>(?:(?&mac_1):){5}(?&mac_1)|(?:(?&mac_1)-){5}(?&mac_1)) # 格好悪い。backreference でいける?
)/@{{
ipv4 => '01',
ipv6 => '10',
mac => '00',
any => '11',
spc => '',
}}{keys %+}/mxge;
print pack('B*', $t);
</pre>
<p>9,10 行目は Perl5 だと悲しい slurp。以降の(一応一つの)正規表現で 0 と 1 の文字列に変換してから pack() で普通の文字列に復元という流れになっています。18行目からの (?(DEFINE) で始まっている部分は正規表現パターンに対して名前を付けている部分です。(?<name>pattern) で pattern に対して name という名前を付け、(?&name) で呼び出している訳です。hoge_1 になっているのがアドレス構成要素 1 要素分、hoge_ になっているのがアドレス全体に対するパターンです。これを (?<name>pattern) で hoge として名前付きキャプチャしています(12行目から)。名前付きキャプチャの結果はハッシュ %+ に設定されるので、keys を使って有効なキャプチャ名(hoge)を取得し、ハッシュで値を置き換えています(25行目)。keys をリストコンテキストで評価したいので(ハッシュリテラルに対する)ハッシュスライスを使っています。わざわざハッシュリテラルを使っているのはその方がなんか格好良さそうだからです。spc 関連は改行削除用のものです。正規表現のオプションとしては、複数行に ^$ をマッチさせるための m、空白等を入れるための x、全体を置き換えるための g、eval するための e を指定しています。こうして変換した後は pack を使って変換して出力するだけです。</p>
<p>perlre とか見ながら即席で書いたにしてはなかなか面白みのあるコードに仕上がったんじゃないかと思います。IP アドレス等にマッチする正規表現そのものがあんまりいけてない感じなのがちょっと残念なところですが。もっと格好良い書き方がある気がします。</p>
<p>ちなみにもらった商品は、iOS プログラミング第2版(ISBN978-4-86401-049-8) なのですが、Mac 持ってないんですよね。iPad も会社支給(貸与)された今、MBP とかを買うべきと言うお告げだったりするのでしょうか。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-15272639973137060072012-08-01T14:24:00.002+09:002012-08-01T14:32:25.631+09:00A bit inside of Transactional Language Constructs for C++ - part.2 Intel TM ABI<p>前回 <a href="http://yak-ex.blogspot.jp/2012/07/a-bit-inside-of-transactional-language.html">Part.1</a> では、<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3341.pdf">Transactional Language Constructs for C++</a> (以下 TM 提案)について Atomic transaction の記述「他のスレッドが transaction の中間結果を観測しない」が、どのようなからくりになっているかを説明しました。Part.2 では、TM 提案と対とも言える文書、<a href="http://software.intel.com/en-us/articles/intel-c-stm-compiler-prototype-edition/#ABI">Intel TM ABI specification</a> を元にコンパイラがどのように C++ TM を実現しようとするかについて覗いてみたいと思います。</p>
<p>TM 提案を実装しているコンパイラはいくつかありますが Intel によるプロトタイプ実装 <a href="http://software.intel.com/en-us/articles/intel-c-stm-compiler-prototype-edition/">Intel C++ STM Compiler, Prototype Edition</a> というものがあります。Intel TM ABI とはこの実装で使用されている ABI です。元々 TM 提案は何が実現されるか(what)についてだけ規定しておりどのように実装するか(how)については規定していません。これはソフトウェア、ハードウェア、ハイブリッドといった区分を含め様々な TM 実装を利用できるようにするためです。コンパイラの実装としてもこの方針に則っており、Tntel TM ABI に則ったライブラリ(libitm)を差し替えることで実装を切り替えられるようになっています。GCC 4.7 以降も TM 提案を試験的に実装していますが、同様に Intel TM ABI に則ったライブラリ(正確には特に例外周りで変更があるみたいですが)への呼び出しに変換されて実現されます。</p>
<p>さて、では TM 提案 に則ったコードをコンパイラがどのように libitm への呼び出しに変換するのかを見てみましょう。以下は TM ABI の例を一部改変しています。</p>
<pre class="brush:c++">int s;
[[transaction_safe]] int f(int);
void foo(void)
{
int i;
for (i=0;i<10;i++)
{
__transaction_atomic {
s += f(i);
if (s > 1000) __transaction_cancel;
}
}
}</pre>
<p>このコードは(例外関係を無視し効率を考えないとして)例えば次のようなコードに変換されます。</p>
<pre class="brush:c++">int s;
int f(int);
static _ITM_srcLocation start_outer_loc = {…};
static _ITM_srcLocation commit_outer_loc = {…};
static _ITM_srcLocation abort_loc = {…};
void foo(void)
{
_ITM_transaction * td = _ITM_getTransaction();
for (i=0;i<10;i++) {
int doWhat = _ITM_beginTransaction (td,pr_instrumentedCode | &start_outer_loc);
if (doWhat & a_restoreLiveVariables) {
/* TM 化していない有効なローカル変数を復元する */
}
if (doWhat & a_abortTransaction) goto txn1_abort_label;
if ((doWhat & a_saveLiveVariables)) {
/* TM 化しない有効なローカル変数を保存する */
}
int sval = (int)_ITM_RU4 (td, (uint32 *)&s);
sval += f_@TXN(i); // TM 化された関数 f の呼び出し
_ITM_WaRU4 (td, (uint32 *)&s, (unit32_t)sval);
if (sval > 1000)
_ITM_abortTransaction(td,userAbort,&abort_loc);
_ITM_commitTransaction(td,commit_outer_loc);
txn1_abort_label:
}
return;
}</pre>
<p>以下では _ITM_ を省略して記述します。srcLocation 関連はデバッグ情報みたいなもので無視して構いません。"instrumented" という表現は TM 対応化された、くらいの意味に取ればいいと思われます。では、簡単に流れに沿って説明してみましょう。</p>
<ul>
<li>まず最初に getTransaction() で transaction descriptor を取得しています。以下の libitm 関数呼び出しで共通して渡されている情報です。内部に libitm で必要な情報が格納されているわけですが、結局は実質スレッドに紐付け可能なわけで libitm 側で管理すればいいんじゃね?という話はあります。この辺りも簡単に ABI spec 3.8 節に触れられており、また、実際 GCC の場合は td が存在しないコードになります。特に本筋に大きな影響はないので spec の記載通りで書いています。
<li>beginTransaction() によって transaction を開始します。これは内部的に setjmp() と同じような処理を含んでおり、commit に失敗した場合や abort された場合に(longjmpと同様の処理が行われ)再びこの関数から戻ってきます。戻り値は次にどのような処理を行うべきか、です。前述の通り abort した場合などもこの関数から戻ってくるためどのような処理をするか戻り値から判別しなければなりません。下表で再実行となっているのは commit に失敗した場合の transaction 再実行です。取り消し不可能云々は本稿では説明しません。さしあたって無視してもらっても大筋は成立します。
<table border="1">
<tr><td colspan="2" style="text-align: center">transaction 開始時</td></tr>
<tr><td>状況</td><td>戻り値</td></tr>
<tr><td>直列で取り消し不可能な transaction (serial irrevocable transaction)を開始<br></td><td>a_runUninstrumentedCode</td></tr>
<tr><td>transaction 開始</td><td>a_saveLiveVariables | a_runInstrumentedCode</td></tr>
<tr><td>transaction 再実行</td><td>a_restoreLiveVariables | a_runInstrumentedCode</td></tr>
<tr><td>直列で取り消し不可能な transaction として transaction 再実行(モード変更)</td><td>a_restoreLiveVariables | a_runUninstrumentedCode</td></tr>
<tr><td>取り消し不可能な transaction として transaction を開始</td><td>a_runInstrumentedCode</td></tr>
<tr><td colspan="2" style="text-align: center">transaction 終了時</td></tr>
<tr><td>状況</td><td>戻り値</td></tr>
<tr><td>transaction が abort</td><td>a_restoreLiveVariables | a_abortTransaction</td></tr>
</table>
<li>a_restoreLiveVariables と a_saveLiveVariables はローカル変数に対するものです。libitm に渡して TM 化する場合オーバーヘッドがかかるため TM 化する変数アクセスは当然出来るだけ絞りたいわけです。transaction 中であればローカル変数は自分のスレッドからしか有効にアクセスできません。ということでローカル変数について保存・復帰によって対処しようというものがこれらのフラグとそれに対応する処理となります。
<li>abort された場合は、a_abortTransaction が返ってくるので(a_restoreLiveVariables によってローカル変数の復帰済み)、以降の transaction 関連コードをスキップします。
<li>RU4() だとか WaRU4() が実際に TM 化するためのメモリアクセスの置き換えです。最初の R or W が読み書きの区別、最後が型です(この場合は U4)。途中の aR 等は読み込みの後(after Read)等の意味を持ち、状況に応じて不要な処理を省くといったことを実現するために分けられています。
<li>f_@TXN は関数 f() の TM 化バージョンという表記です。実際にはコンパイラによって変わってくるでしょう。transaction 中であるかを判別する inTransaction() という関数もあるのでそれを使って関数内で切り替えることも可能だと思いますが、恐らくはゼロオーバーヘッドを考慮して 2 バージョン用意する形を想定して書かれているのだと思います。
<li>abortTransaction() はそのまま transaction の abort で前述のように beginTransaction() の場所に戻ります。
<li>commitTransaction() もそのまま transaction の commit です。commit に失敗した場合、前述のように beginTransaction() に戻って transaction が再実行されます。
</ul>
<p>さて、どうでしょうか? まだ libitm の中まで見ていませんが、begin, abort, commit があって変数アクセスが置き換えられているということから(単一グローバルロックでなくとも)、Transactional Memory が実現できそうかなという感じがするんじゃないでしょうか? part.3 では libitm 実装の一つである <a href="http://code.google.com/p/rstm/">RSTM</a> を参考にして TM がどのように実現されているかを簡単に見てみたいと思います。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-1081496842770278432012-07-31T23:04:00.000+09:002012-07-31T23:07:55.167+09:00A bit inside of Transactional Language Constructs for C++ - part.1 Atomic transaction<p><a href="http://partake.in/events/bd840b2e-77dc-4501-a765-cb581a90c165">Boost.勉強会 #10</a> にて <a href="http://yohhoy.hatenablog.jp/entries/2012/07/29">@yohhoy さんが Transactional Language Constructs for C++ (C++ における Transactional Memory 拡張)について発表</a> されました。丁度自分も<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3341.pdf">提案文書</a>を読んでいるところであり Transactional Memory (以下 TM)というか並列プログラミング全般について知識がないので勉強会駆動の発表ネタになるかなと思っていたところだったので非常にタイムリーでした。発表内容としては現在提案されている TM 拡張の syntax と semantics についての説明で、実装については対象外だったわけですが(もともと提案文書には実装については含まれていない)、その発表の中で</p>
<ul>
<li>(Atomic Transaction で、他の transaction だけでなく)他のスレッドに途中状態を見せないってどう実現するのか分からない
</ul>
<p>というコメントがありました(多分)。その時は、ピンと来なかったのですが色々調べたりするうちにその感覚が分かってきました。その心は</p>
<ul>
<li>ゼロオーバーヘッドか?(TM 有効にしても実際に TM を使用しなければオーバーヘッドはないか?)
</ul>
<p>という質問にも通じます。私は TM 拡張は基本的に transaction 内部のコードだけ変更すればいいと考えていたので実行時にはほぼゼロオーバーヘッドだと思っていたのですが、(transaction 外の)他のスレッドにも途中状態を見せないということは transaction 外のコードに対しても何かガードなりを設ける必要があるのではないか?という懸念があった訳です。</p>
<p>が、なんというか「確かに嘘は書いてないんだけどさぁ」という解釈が可能であることに気付きましたので、本稿ではそのことについて書いてみます。</p>
<p>さて、提案文書では Atomic transaction について以下のように書かれています。</p>
<blockquote>In a data-race-free program, an atomic transaction appears to execute atomically; that is, the compound statement appears to execute as a single indivisible operation whose operations do not interleave with the operations of other threads.</blockquote>
<blockquote>データ競合がないプログラムでは、atomic transaction はアトミックに実行される。(atomic transaction として指定された)複文は他のスレッドの操作とインターリーブされない単一の分割不可能な操作として実行される。</blockquote>
<p>さて、ここでどうしても後半に意識がいってしまうわけですが、この文章で最も重要なのは最初の部分 <b>"In a data-race-free program"</b> です(appear であることも多分重要)。</p>
<p>data-race-free とは何かについては TM 提案の最初の方にも簡単に触れられています。C++11 では 1 スレッド内の実行順序について "sequenced before" という関係で順序が定められているものがあります。またスレッド間の実行順序について "synchronized with" という関係で順序が定められているものがあります。これらをもとに "happens before" という関係が定められています(厳密にはもうちょっと複雑)。</p>
<ul>
<li>A is sequenced before B → A happens before B
<li>A synchronizes with B → A happens before B
<li>A happens before B ∧ B happens before C → A happens before C
</ul>
<p>そして、あるメモリ領域に対する書き込み操作と、別の読み込み操作あるいは書き込み操作が同じメモリ領域に対して行われている時、これらを conflict と称します。以上を元に data race (データ競合) は、次のように規定されています。</p>
<blockquote>The execution of a program contains a data race if it contains two conflicting 2 operations in different threads, at least one of which is not an atomic operation, and neither happens before the other.</blockquote>
<blockquote>異なるスレッドの 2 つの操作が conflict しており、"happens before" の関係になく、かつ、少なくとも一方は atomic ではない場合、data race が発生している。</blockquote>
<p>要するに、「同一メモリ領域に対する書き込みと、読み込みないし書き込み」(=conflict)について順番が定められていないケースを data-race と呼んでいる訳です。</p>
<p>さて、transaction 間については、ある transaction の終了と別の transaction の開始には "synchronized with" の関係があるとされ、実行がインターリーブしません。従って、transaction 間では data-race は発生しません。では、transaction と transaction 外ではどうなるでしょうか?</p>
<p>atomic transaction はロックや atomic など他の同期機構を含むことができません。このため、transaction 内のコードと transaction 外のコードについて "synchronized with" 関係が発生しません。この状況下で data-race-free、つまり順序不定な conflict が存在しないためには、</p>
<ol>
<li>同一スレッド内で sequenced before 関係にあるか、
<li>そもそも conflict が存在しないか、
<li>別の transaction 内に存在しているか、
</ol>
<p>のいずれかである必要があります。結果として別スレッドの transaction 外のコードは transaction の途中状態を見ることがありません。この場合、2 しか有り得ず、そもそも transaction が変更するメモリ領域に対するアクセス、conflict が存在しない訳ですから。</p>
<p>つまり、atomic transaction において他のスレッドが transaction の途中状態を見ないというのは atomic transaction によって保証されているというよりは、その前提、data-race-free なプログラムである、というところに依るところが大きいと言えます。data-race-free であることはプログラマが保証してやらねばなりません。一番簡単なのは conflict があるところを transaction で囲むことでしょう。この場合、atomic transaction である必要はありません(transaction 間であれば relaxed transaction でも順序が規定されるので)。</p>
<p>本記事では A bit inside of Transactional Language Constructs for C++ part.1 として TM 提案 での atomic transaction の記述の解釈について書いてみました。心づもりとしては part.2 では TM 提案の対とも言える文書、<a href="http://software.intel.com/en-us/articles/intel-c-stm-compiler-prototype-edition/#ABI">Intel TM ABI</a> を元にコンパイラがどのように C++ TM を実現しようとするかについての概要、part.3 では Intel TM ABI を実装しているライブラリ <a href="http://code.google.com/p/rstm/">RSTM</a> の実装を簡単に覗いてみたいと思っています。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-14167672399231047152012-07-15T16:10:00.000+09:002012-07-15T16:10:05.613+09:00小ネタ: BOOST_CHECK_CLOSE と BOOST_CHECK_CLOSE_FRACTION<p>Boost.Test は Boost にあるユニットテストフレームワークである。ユニットテストの項目記述用に色々とマクロが定義されているのだが、その中に浮動小数点数比較用のものがある。なぜ浮動小数点数用が別にあるかというと誤差の問題が存在するからで許容範囲を与えるようになっている。</p>
<pre class="brush:c++">
BOOST_CHECK_CLOSE ( 1.00001e-10, 1.00000e-10, 0.00001 ); // FAIL
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK
</pre>
<p>ではこの _FRACTION の有無の違いは何かということで<a href="http://www.boost.org/doc/libs/1_50_0/libs/test/doc/html/utf/testing-tools/reference.html">ドキュメント</a>を見ると、見ると……。違いが分からなかったという貴方は正しい。<b>なぜならドキュメントが間違っているからだ。</b>間違っていることは <a href="https://svn.boost.org/trac/boost/ticket/3964">#3964</a> で指摘されており <a href="http://svn.boost.org/svn/boost/trunk/libs/test/doc/html/utf/testing-tools/reference.html">trunk では修正されている</a>のだが release ブランチにマージされていないようだ。ということで、<a href="https://svn.boost.org/trac/boost/ticket/7136">チケットを切ってみた</a>。状況にもよるがチケット切ると割とすぐに対応してもらえたりするので、見つけた問題点はばんばんチケット切ると良いと思う(もちろん重複確認ぐらいはした上で)。</p>
<p>話を戻すと、BOOST_CHECK_CLOSE はパーセンテージ指定、BOOST_CHECK_CLOSE_FRACTION は比率指定、つまり</p>
<pre class="brush:c++">
BOOST_CHECK_CLOSE ( 1.00001e-10, 1.00000e-10, 0.001 ); // OK
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK
</pre>
<p>が同じ挙動になるということである。</p>
<p>ちなみにパーセンテージ、比率ということからも分かる通り、許容範囲は相対指定である。マクロを使う限りにおいては引数それぞれからの相対で両方を満たしていなければならない(これに関するドキュメントもリリースでは古いので <a href="http://svn.boost.org/svn/boost/trunk/libs/test/doc/html/utf/testing-tools/floating_point_comparison.html">trunk</a> から)。</p>
<pre>|u − v| / |u| ≤ ε ∧ |u − v| / |v| ≤ ε</pre>
<p>つまり以下はいずれも FAIL する。</p>
<pre class="brush:c++">
BOOST_CHECK_CLOSE ( 0.99999e-10, 1.00000e-10, 0.001 ); // FAIL
BOOST_CHECK_CLOSE_FRACTION( 0.99999e-10, 1.00000e-10, 0.00001 ); // FAIL
</pre>
<p>片方からだけでも構わないという場合は第 4 引数を FPC_WEAK として直接 check_is_close を使えば良い。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-15045123768199802932012-07-02T23:53:00.001+09:002012-07-02T23:53:40.417+09:00emplace と aggregate<p>C++11 で rvalue reference による perfect forwarding が実現されたため、STL コンテナに emplace 系の関数が追加されている。insert() や push_back() は value_type 型の値自体を与える必要があるが、emplace 系には生成に必要な引数(コンストラクタの引数等)を渡してやれば良い。</p>
<pre class="brush:c++"> std::vector<std::pair<int, int>> v1;
std::pair<int, int> p{ 0, 0 };
v1.push_back(p);
v1.push_back({ 0, 0 });
v1.emplace_back(0, 0);</pre>
<p>これで無駄な temporary 作成が無くなり万々歳、なのだが。非常によく似た以下の例は実はコンパイルできない。</p>
<pre class="brush:c++"> struct point { int x, y; };
std::vector<point> v2;
point pt{ 0, 0 };
v2.push_back(pt);
v2.push_back({ 0, 0 }); // (g++ 4.5 compilation error
// by ambiguous between const value_type & and value_type &&)
v2.emplace_back(0, 0); // g++ 4.5-4.8 compilation error
// new initializer expression list treated as compound expression
</pre>
<p>g++ 4.5 特有のエラーについては置いとくとして、下側なんでやねんというのは <a href="http://stackoverflow.com/questions/8782895/why-doesnt-emplace-back-use-uniform-initialization">StackOverflow の質問</a> ならびに引用されている <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2089">DR</a> を見てもらえれば良いのだが、問題は emplace 系で呼び出される std::allocator_traits::construct(m, p, args) が最終的に ::new((void *)p) U<b>(</b>std::forward<Args>(args)...<b>)</b> となり、list-initialization ではなく direct-initialization になってしまう、という点にある。単純に list-initialization にする、というのは例えば下記のようなコードの挙動を変えてしまうということで、</p>
<pre class="brush:c++"> std::vector<std::vector<int>> v;
v.emplace_back(3, 4); // v[0] == {4, 4, 4}, not {3, 4} as in list-initialization</pre>
<p>is_constructible<U, Args...> が true かどうか(direct-initialization が有効かどうか)によって、direct-initialization か list-initialization かを呼び分ける方向での修正が提案されている。</p>
<p>こんな単純そうな例ですら落とし穴があるとは、ほんと C++11 難しい。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-35832690216830299702012-03-16T00:30:00.001+09:002012-03-16T00:34:50.290+09:00左シフト演算子と未定義動作<p>指定したビット数だけ下(LSB)からビットが立ったビットマスクを得るために</p>
<pre class="brush:c++">(1U << bits) - 1</pre>
<p>という式を愛用していたのだがはまってしまった。bits == std::numeric_limits<unsigned>::digits つまり全て 1 のマスクにしたい場合、この式は未定義動作をもたらす。14882:2003 5.8/1 には(右シフトも含めて一般に)こうある。</p>
<blockquote>The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.</blockquote>
<p>そして実際に少なくとも x86 上ではまず期待通り(全て 1)にはならない。x86 アセンブリの左シフト命令はシフト数は 5 ビット分だけ有効である。つまり 32 == 100000(2) は 0 ビットシフトと同じになり結果として上の式は 1 - 1 == 0 となってしまう。</p>
<p>左シフトには他にも未定義動作となる場合があるのだがこの記述にも変遷がある。</p>
<p>14882:1998 と 14882:2003 では以下の通りである。つまり undefined behavior という記述がない。E1 が signed な場合はどうなるのが正しいんだよ、という感じである。恐らく未定義動作を意図していない記述だろう。</p>
<blockquote>The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]</blockquote>
<p>一方、14882:2011 (多分。自分の参照文書は n3291 なので違う場合もあり得る)では <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#854">DR854</a> によりこうなっている。</p>
<blockquote>The value of E1 << E2 is E1 <span style="text-decoration:line-through;background-color:#FFA0A0">(interpreted as a bit pattern)</span> left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 <span style="text-decoration:line-through;background-color:#FFA0A0">multiplied by the quantity 2 raised to the power E2</span> <span style="font-weight:bold;background-color:#A0FFA0">× 2<sup>E2</sup></span>, reduced modulo <span style="text-decoration:line-through;background-color:#FFA0A0">ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]</span> <span style="font-weight:bold;background-color:#A0FFA0">one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2<sup>E2</sup> is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.</span></blockquote>
<p>int, long int よりも大きな型も想定した記述となっていること、E1 が signed な場合にも記述が明確となり、負の場合には未定義動作となっている。</p>
<p>そして、既に <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1457">DR1457</a> が出ており以下のように修正される予定である。</p>
<blockquote>if E1 has a signed type and non-negative value, and E1 × 2<sup>E2</sup> is representable in the <span style="font-weight:bold;background-color:#A0FFA0">corresponding unsigned type of the</span> result type, then that <span style="font-weight:bold;background-color:#A0FFA0">value, converted to the result type,</span> is the resulting value; otherwise, the behavior is undefined.</blockquote>
<p>これは、1 << std::numeric_limits<int>::digits のように最大の負数を得るためにビット数-1(=符号ビット分少ないビット数)だけシフト、つまり符号ビットを 1 にするコードを合法にするためである。ただし、これは signed の範囲で表現できない unsigned の値から signed への変換について処理系定義の動作を含む。……しかしだったら signed 全体について全て unsigned にして処理した後 singed に戻すとか規定してしまえばいいじゃないかとも思う。</p>
<p>なお、右シフトについては実質的に記述は変わっておらず(文による表現が式による表現になっただけ)、E1 が負数の場合は処理系定義となっている(以下は n3291 より)。</p>
<blockquote>The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2<sup>E2</sup>. If E1 has a signed type and a negative value, the resulting value is implementation-defined.</blockquote>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-37427504424595378502012-03-14T01:17:00.001+09:002012-03-14T01:17:33.122+09:00図解 MPL Metafunctions<p>Boost ライブラリの中でも Boost.MPL は割と食わず嫌いというかなんとなく敬遠している人も多いライブラリのような気がする。MPL = Meta Programming Library ということで「メタプログラミング?黒魔術?」みたいな受け取り方をされているんじゃないかというか、実際には</p>
<blockquote class="twitter-tweet" lang="ja"><p>Boostは一般人が闇に触れずとも闇の力を使える様にするアーティファクトですが、ちょっと使った程度の事では闇に落ちたりしませんから安心してBoostするといいです・x・ (ックックック #<a href="https://twitter.com/search/%2523bot">#bot</a></p>— 伊藤 兎 (実際にんじん)さん (@USAGI_WRP) <a href="https://twitter.com/USAGI_WRP/status/169063602018451456" data-datetime="2012-02-13T14:21:18+00:00">2月 13, 2012</a></blockquote>
<script src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
<p>という言にふさわしい、コンパイルタイムメタプログラミングを Sequence、Iterator、Algorithm といったランタイム(実行時:コンパイルタイムの対義語として)の語彙で取り扱えるようにする一般人のためのライブラリである。typename ::type 乱舞になりがちなところと、代入や状態の変更ができず関数型言語的に記述する必要があるところだけ気をつければ難しくない。のだがちょっと自分の中で整理しきれていなかったのが Metafunction 関係である。前回 MPL 用再帰的 equal を書く中で大分整理できたのでまとめてみる。</p>
<p>MPL の Metafunction 関係について包含図を書いてみると以下のようになる。</p>
<h3>MPL Metafunctions</h3>
<a href="https://docs.google.com/drawings/pub?id=1MCDuvLW4bAy22ELXkP5PtlXkL29pgTMACWtk_jlR0PY&w=926&h=414"><img src="https://docs.google.com/drawings/pub?id=1MCDuvLW4bAy22ELXkP5PtlXkL29pgTMACWtk_jlR0PY&w=463&h=207"/></a>
<p>Metafunction がランタイム世界での通常の関数にあたる。適用が ::type しないといけないところがちょっと面倒なところだ。Metafunction 以外の Lambda Expression は高階関数にあたるところであり Metafunction Class と Placeholder Expression からなる。Metafunction Class は関数オブジェクト(Functor)にあたると思えばよい。operator() の代わりにメンバテンプレート apply があると考えても良いだろう。さて、ランタイムにおける世界でも毎回毎回関数オブジェクトを書くのは面倒ということで Boost.Lambda や C++11 でのラムダ式がある。これの MPL 版にあたるのが Placeholder Expression だ。良く分からない英語が書いてあるが、placeholder(boost::mpl::_1 等)自身や、テンプレートパラメータのどこかに placeholder ないし Placeholder Expression を含むテンプレートクラスの特殊化(specialization)である。</p>
<pre class="brush:c++">_1
plus<_, int_<2> >
if_< less<_1, int_<7> >, plus<_1,_2>, _1 ></pre>
<p>最後が bind expression である。これは単に bind の特殊化だ。bind はメンバテンプレート apply を持つため必ず Metafunction Class となるが、必ずしも Placeholder Expression とはならない。placeholder なしで bind することも可能だからだ。そのため Placeholder Expression から一部はみ出している。</p>
<pre class="brush:c++">bind< times<>, int_<2>, int_<2> ></pre>
<p>さて、なんとなく Metafunction 族については分かっただろうか。自分もここまでは大体分かっていたのだがそれに作用するもの、具体的に主要なものをあげると apply, lambda, apply_wrap, protect, quote 辺りについて整理ができていなかったので以下に並べてみる。以下の図で青色が引数に取る対象、桃色がある場合はその部分が実際に変換される対象である。</p>
<h3>MPL apply</h3>
<a href="https://docs.google.com/drawings/pub?id=1NHQK9TFkisUda7xopt47Xqtnpzh2cxqoctAR2lmRNxw&w=931&h=444"><img src="https://docs.google.com/drawings/pub?id=1NHQK9TFkisUda7xopt47Xqtnpzh2cxqoctAR2lmRNxw&w=466&h=222"/></a>
<p>apply は Lambda Expression を引数に取り、その Lambda Expression を適用する(呼び出す)。実際には lambda を適用した後で apply_wrap を呼び出す。では、その lambda と apply_wrap がどうなっているかというと、</p>
<h3>MPL lambda</h3>
<a href="https://docs.google.com/drawings/pub?id=1y88BbcJGeXbJgY7tRoHhK4odQ6Tye9QpAnAjHN_yOIs&w=930&h=494"><img src="https://docs.google.com/drawings/pub?id=1y88BbcJGeXbJgY7tRoHhK4odQ6Tye9QpAnAjHN_yOIs&w=465&h=247"/></a>
<p>lambda は任意の型を引数に取るが、その内 Placeholder Expression を Metafunction Class に変換する。他はそのままである。</p>
<h3>MPL apply_wrap</h3>
<a href="https://docs.google.com/drawings/pub?id=1_3XIaZHFxJJZIkn7s6oluErKdp0IOi7vUYgma2d99uU&w=927&h=469"><img src="https://docs.google.com/drawings/pub?id=1_3XIaZHFxJJZIkn7s6oluErKdp0IOi7vUYgma2d99uU&w=464&h=235"/></a>
<p>そして、apply_wrap は Metafunction Class の呼び出しである。実際には ::apply<...> と同等だ。なので、apply は lambda により全て Metafunction Class に変換した後、apply_wrap で呼び出すことになる。</p>
<h3>MPL protect</h3>
<a href="https://docs.google.com/drawings/pub?id=1bNevMWRFNYfewqPC1DNIyoKVfvuihcmqZ0oVnmj_EFM&w=932&h=496"><img src="https://docs.google.com/drawings/pub?id=1bNevMWRFNYfewqPC1DNIyoKVfvuihcmqZ0oVnmj_EFM&w=466&h=248"/></a>
<p>protect は Metafunction Class を受け取るが bind expression しか変換しない。リファレンスマニュアルの例だが以下のように bind 時の placeholder の置き換えを抑止する。protect なしだと入れ子の bind 中の _1, _2 まで置き換えられているが、protect をかけると置き換えされない。</p>
<pre class="brush:c++">struct f
{
template< typename T1, typename T2 > struct apply
{
typedef T2 type;
};
};
typedef bind< quote3<if_>,_1,_2,bind<f,_1,_2> > b1;
typedef bind< quote3<if_>,_1,_2,protect< bind<f,_1,_2> > > b2;
typedef apply_wrap2< b1,false_,char >::type r1;
typedef apply_wrap2< b2,false_,char >::type r2;
BOOST_MPL_ASSERT(( is_same<r1,char> ));
BOOST_MPL_ASSERT(( is_same<r2,protect< bind<f,_1,_2> > > ));</pre>
<h3>MPL quote</h3>
<a href="https://docs.google.com/drawings/pub?id=1xkSwSu-LJ5RQqAH-afJh15WAuyVfx5c4DYWA2ylsQEI&w=925&h=478"><img src="https://docs.google.com/drawings/pub?id=1xkSwSu-LJ5RQqAH-afJh15WAuyVfx5c4DYWA2ylsQEI&w=463&h=239"/></a>
<p>最後に上の protect の例でも使われていた quote である。これは Metafunction を Metafunction Class に変換する。引数の数を指定する必要があり、その際デフォルトパラメータの部分も数えなければならないし、変換された Metafunction Class には全引数を渡してやらなくてはならない。bind 等と併用するくらいなら Placeholder Expression + lambda の方が楽かもしれない。</p>
<h3>まとめ</h3>
<p>どうだろうか。少しでも理解の助けになっただろうか?現実的には以下のルールに従っていれば大体問題ないと思われる。</p>
<ul>
<li>高階関数を受け取る場合は Lambda Expression を受け取ることにする
<ul>
<li>適用(呼び出し)する場合は apply を使う
<li>高階関数として「そのまま」渡したい場合は lambda をかける(protect をかけた状態になる。実際 lambda は Lambda Expression に対しては protect<bind<...> > になる)
</ul>
<li>高階関数として Metafunction を渡したい場合は quote をかける
</ul>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0tag:blogger.com,1999:blog-1285241128314938524.post-68577078238237995252012-03-12T00:50:00.000+09:002012-03-12T00:50:05.320+09:00Boost.MPL 用再帰的 equal<p>Boost.MPL の Sequence はその特性上 is_same を使いにくい。例えば</p>
<pre class="brush:c++">BOOST_MPL_ASSERT((
boost::is_same<
boost::mpl::push_front<
list<>,
int_<1>
>::type,
list<int_<1> >
>));</pre>
<p>は通らない。push_front した結果は list ではなくなっているからだ。このため Boost.MPL には equal というアルゴリズムが用意されている。</p>
<pre class="brush:c++">BOOST_MPL_ASSERT((
boost::mpl::equal<
boost::mpl::push_front<
list<>,
int_<1>
>::type,
list<int_<1> >
>));</pre>
<p>equal は Sequence の種類を気にせずその「要素」が一致しているかを判別するためこれは通る。通るのだが、equal は最上位の Sequence だけしか考慮してくれないため多次元の Sequence だとうまくいかない。equal の第 3 引数は要素を比較する際の Predicate であるため次元に合わせて equal を渡してやればいいのだが割と面倒である。</p>
<pre class="brush:c++">// bind base
BOOST_MPL_ASSERT((
boost::mpl::equal<
vector<vector<int_<1> > >,
list<list<int_<1> > >,
boost::mpl::bind<
boost::mpl::quote3<boost::mpl::equal>,
boost::mpl::_1,
boost::mpl::_2,
boost::mpl::protect<
boost::mpl::bind<
boost::mpl::quote2<boost::is_same>,
boost::mpl::_1,
boost::mpl::_2
>
>
>
>));
// lambda base
BOOST_MPL_ASSERT((
boost::mpl::equal<
vector<vector<int_<1> > >,
list<list<int_<1> > >,
boost::mpl::lambda<
boost::mpl::equal<
boost::mpl::_1,
boost::mpl::_2,
boost::mpl::lambda<
boost::is_same<
boost::mpl::_1,
boost::mpl::_2
>
>::type
>
>::type
>));</pre>
<p>やってることは同じである。というか bind base の方は実質 lambda を展開した結果になっている。二次元でこれだとそれ以上だと絶望しそうだ。ということで再帰的な equal を書いてみた。</p>
<pre class="brush:c++;highlight:[7]">template<typename Arg1, typename Arg2, typename Pred = boost::is_same<boost::mpl::_1, boost::mpl::_2> >
struct equal_deep
{
typedef typename boost::mpl::eval_if<
boost::mpl::and_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
boost::mpl::equal<Arg1, Arg2, equal_deep<boost::mpl::_1, boost::mpl::_2, typename boost::mpl::lambda<Pred>::type> >,
boost::mpl::eval_if<
boost::mpl::or_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
boost::mpl::false_,
boost::mpl::apply<Pred, Arg1, Arg2>
>
>::type type;
};
BOOST_MPL_ASSERT((
equal_deep<
vector<vector<int_<1> > >,
list<list<int_<1> > >,
>));</pre>
<p>やっていることはそれほど難しくない。引数が両方 Sequence である時には equal に対して自分自身(equal_deep)を渡して再帰し、両方が Sequence でない時には渡された Predicate を呼び出す。自分が MPL Metafunction 関係をちゃんと把握していなかったので lambda かけるところと apply で迷ったぐらいである。7 行目の eval_if は if_ だと is_same の場合は大丈夫だが Sequence に対して呼び出せない Predicate (equal_to 等) を渡した場合にコンパイルエラーになるため eval_if でなければならない。また、nullary Metafunction を受け付ける部分は typename ::type を付けずに不要なインスタンス化を避けている。</p>
<p>これを書く際にせっかくなので一度 MPL Metafunction 系について整理してみたのだが以下次号。</p>yak_exhttp://www.blogger.com/profile/00160089623004932890noreply@blogger.com0