SSブログ
前の10件 | -

ケーキ分配その２

仮定４から考える方法。

D.によるとどのターンにおいても勝ち負けがランダムであるため、参加者は、
どのターンで勝とうが、全敗しようが、取り分が同じになるように調節する
に違いない。（★仮定４）

続きを読む


2010-09-25 07:47  nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ：テレビ

アルクメデスのケーキ等分問題を難しく考える

NHKのクイズ？番組アルクメデス9月16日回の
resolve dogsというコーナーでのクイズが面白かった。

http://www.nhk.or.jp/medes/quiz/resolve/20100916.html

秤の類を用いずに、５人でケーキを切り分ける平等な方法は何か？というもの。
番組では、
円周方向に角度が少しずつ増えるようナイフを動かし、 各人が欲しいと思ったところでストップをかける。 最初にストップを掛けた人がその時点でのナイフの位置分だけ貰える。

というのを正解としていた。


これを理屈で説明してみようと思った。

続きを読む


2010-09-25 02:38  nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ：テレビ

VS2010に移行してハマる　[プログラミング]

１．ビルド時に使う共通のディレクトリ参照先の設定方法が変わった

ツール→オプション→プロジェクト及びソリューション→VC++ ディレクトリ

でインクルード先や実行ファイルの参照先を設定できてたのが、
プロパティシート管理になったんだそうだ

VS2008などから設定を移行した場合、ユーザ設定値は

<ドライブ>:\Documents and Settings\<ユーザー>\Local Settings\Application Data\Microsoft\MSBuild\v4.0

にコピーされていて、これが規定で参照されるようになります。

詳しくは↓

http://msdn.microsoft.com/query/dev10.query?appId=Dev10IDEF1&l=JA-JP&k=k(VC.PROJECT.VCDIRECTORIES.EXECUTABLEPATH)&rd=true



２．swaptimization関連コードがなくなった

以前の記事で move semantics モドキがあったと書いたんですが
URL → http://nekojiru.blog.so-net.ne.jp/2008-09-06

VS2010にて rvalue reference 機能が入ったため、stlのコードからswaptimization関連コードがごっそり削除されています

例の方法を使ってしまっていた場合は、面倒ですが move semantics となるよう rvalue reference を受け取る move constructor を実装する必要があります

しかし、 move constructor / move assignment operator って勝手には作られないんですかね。親クラスと全メンバ変数 が move constructible なら勝手にやっていいと思うんですけどもね。
2010-05-24 13:52  nice!(0)  コメント(0) 
共通テーマ：パソコン・インターネット

sambaがsymlinkをたどらなくなった

debianを使っているのですが、最近の更新でもって
sambaがsymlinkをたどらなくなってしまいました

エラーログを見ると

Share '(俺のユーザ名)' has wide links and unix extensions enabled. These parameters are incompatible. Wide links will be disabled for this share.


wide links 設定と unix extensions 設定は共存できないそうです。
何だろうこれ。

このメッセージで検索してみると

http://cgi.samba.gr.jp/pipermail/samba-jp/2010-March/002298.html
http://www.samba.org/samba/news/symlink_attack.html

こういう事情があったとのこと
詳細はよくわかりませんが（ハハハ）

とりあえず unix extension は使わない(windowsからしかsambaアクセスしない)のでオフにしたところ動くようになりました。


2010-03-22 22:46  nice!(0)  コメント(0) 
共通テーマ：パソコン・インターネット

X64 で動作している Visual Studio に 64bit版コンパイラを使わせる方法　[プログラミング]

Visual Studio IDE(2005/2008共に)は32bitアプリケーションです。x64(例えばVista64)なOS上でも32bitプロセスです。

以下は2008の話です。2005は知りません。

C/C++コンパイラはx64用が用意されています。正しく言うと、「x64で動き、x64コードを吐くコンパイラ（★１)」です。

（フォルダのキャプチャ画像なんかを貼る）

x64 OSで、x64プロジェクトをビルドすれば、このx64なコンパイラを使うと思っていたのですが・・・

http://msdn.microsoft.com/ja-jp/library/ms246588.aspx
Visual Studio では、Windows 64 ビット コンピュータ上であっても 32 ビット クロスコンパイラを使用します。ただし、devenv コマンドを使用すると、64 ビットでホストされたツールを呼び出すコマンドライン環境を作成できます。

オーマイガー。「x86で動き、x64コードを吐くコンパイラ（★２)」を使っているようです。クロスコンパイラという奴ですね。

ちょっと悔しいので、（★１)を使わせたいと思いました！！！

結論からいうと可能で、こうすればいいようです。

（後で書く）

タスクマネージャで見ると、cl.exeやlink.exeが64bitプロセスになっていることが分かります。

（キャプチャを貼る）

でもよく考えると、★１も★２も最適化のアルゴリズムは同じだろうから、結果生成されるコードに違いはないはずで・・・

コンパイル時間や使用メモリ量に差があるかな？良くなるなら意味あるんですけどね。あとは大きなファイルをコンパイルできるとか。でも32bit版でコンパイルできないなんてどんだけ。

というか、そうでないなら、★１が用意されている理由が分からない。ひょっとしてクロスチェック用？

ただ、同じことをやるなら、32bit版のほうが高速に動くと思うんですよ。要検証　なんでかっていうと、ポインタサイズとsize_tが半分で済むので、その分メモリ消費量が少なくて済む（＝キャッシュミス率が下がる）から。要検証　もしこれが真なら、ほとんどのアプリは32bit版で提供すべきですね！！！


2008-12-05 16:11  nice!(0)  コメント(1) 
共通テーマ：パソコン・インターネット

_BIND_TO_CURRENT_CRT_VERSION はヤバい　[プログラミング]

VS2008 SP1 で導入されたマクロ _BIND_TO_CURRENT_CRT_VERSION　はヤバい。マジで。

あとで書く。

参考リンク

http://msdn.microsoft.com/ja-jp/library/cc664727.aspx

ハマった（ハメられた）方

http://d.hatena.ne.jp/espresso3389/20080820
http://d.hatena.ne.jp/espresso3389/20080821


2008-11-04 19:41  nice!(0)  コメント(0) 
共通テーマ：パソコン・インターネット

DisableThreadLibraryCalls は CRTを静的リンクする場合は呼んではならない　[プログラミング]

http://support.microsoft.com/kb/555563/ja

うほ、機械翻訳は読めん。

http://support.microsoft.com/kb/555563/en-us

を見ましょう。

このKBによると、DLLにCRTを静的リンクする場合(つまり/MTでlibcmt.libなどを使う場合)には、DisableThreadLibraryCalls を呼んではダメらしいです。

ちょっと前の「テクニック集」みたいなものには、とりあえず呼んどけみたいなことが書いてありました。私もそうしてました。

しかし昔ならいざ知らず、今はCRTは動的リンク(msvcrt80.dllを使う)のほうがよろしいので、あんまり問題にはなりそうにありませんが。

オマケ。 /MT と /MD の区別の方法。

マクロに違いが出ます。

/MT : _MT
/MD : _MT と _DLL

となるそうです。参考：http://msdn.microsoft.com/ja-jp/library/2kzt1wy3.aspx

つまり、 _DLL が define されてるときだけ DisableThreadLibraryCalls しろってことです。

_STATIC_CPPLIB なんていうアヤシゲなマクロもありますがこれはまた後ほどほじくろうと思います。
2008-10-22 23:50  nice!(0)  コメント(0) 
共通テーマ：パソコン・インターネット

Swaptimizationでmove先取り？その２　[プログラミング]

続きです。

vectorのresize時に各要素についてコピー操作が発生すると前回書きました。

T* newarea = new T[newsize];
for ( size_t i = 0 ; i < oldsize ; ++i ) {
　newarea[i] = area[i]; // コピー操作
}
delete [] area;
area = newarea;

これをswapにするとこうなります。
T* newarea = new T[newsize];
for ( size_t i = 0 ; i < oldsize ; ++i ) {
　std::swap(newarea[i], area[i]); // swap操作
}
delete [] area;
area = newarea;

新領域(newarea)の各要素は、デフォルトコンストラクタで作成されていますから、最初の確保時点では中身はデフォルト状態です。

これを旧領域の各要素とswapしていくので、結局、新領域の各要素には旧要素の各要素が入り、旧要素の各要素はデフォルト状態になります。

swapでmoveができそうです！

さて、問題は、これを vector::resize() にやってもらう方法です。vectorは当然ながらコピー方式で実装されています。 vector<MyClass> とやったときには swap 方式の resize を使って欲しいのです・・・

(1)stlのヘッダファイルを書き換える・・・やりたくない
(2)自分用vectorクラスを作成する・・・やりたくない（STLのコンテナクラスの要件を満たすのはのは難易度がとても高いです！）

さてどうしたものか。。。と、VC++(VS2005SP1)のvectorヘッダファイルを見ると、こんな定義があります。ま、これを見つけたからこんなエントリ書いてるんですけども。
　// vector implements a performant swap
template <class _Ty, class _Ax>
　class _Move_operation_category<vector<_Ty, _Ax> >
　{
　public:
　　typedef _Swap_move_tag _Move_cat;
　};

これはなにやらキナクサイですぞ・・・！

結論を言いますと、この _Move_operation_category クラスを特殊化し、_Swap_move_tag を _Move_cat として typedef すると、いくつかのコンテナクラスは、moveで済む場合にswapを呼び出すようになります。イヤッホウ！

swapによる最適化だから「Swaptimization」と呼んでいるわけですね！

適用して意味のあるケースを調べたのですが、VS2005 SP1では、vector の resize で領域を再確保したときだけでした。もうちょっとあるかと思ったんですけどね。

ということで、現状では、vectorに直接突っ込むクラスが以下のようなものの場合、「swap使って移動してね」宣言しておくとよさそうです。
  • デカいメモリを動的に確保し、コピー操作ではそれらのコピーが行われる

  • メンバ変数にデカいコンテナを持つ(vector, list, map, basic_string, etc)


    • メンバが全てPOD(intとか)で、コピーがmemcpyで済む場合は、swapでやるとかえって遅くなるかもしれません。swapを要素数だけ呼ぶより、全体をmemcpyするほうがおそらく早いでしょう。

    本当はここでベンチマークするといいんですけどね・・・

    しかし、上記のようなテンプレート（タグ？）の宣言がなくても、swapがあれば勝手にやってよさそうなモンですけどねえ。なぜこのようなまどろっこしい事態になっているのか・・・あんまり書くとボロが出そうなのでやめておきます。

    こんなところで。


    注意１

  • この仕組みはドキュメント化されていません。また、私の理解不足や、実装の不備などにより不都合があるかもしれません。使用は自己責任でオネガイシマス。

  • この機構は標準化されたものではありません。今のところVC専用のようです。アンダースコアで始まってますからね・・・

  • VCの2005と2008にはあるようですが、継続的にサポートされるかどうかは分かりません。


    • 注意２

    要素型についてのstd::swapは、自分で特殊化したものを定義しておく必要があります。こんな感じです。
    namespace std {
    　inline void swap(MyClass& Left, MyClass& Right) {
    　　// 各メンバ変数についてstd::swapを呼ぶか、独自の効率のよいswap処理を書く
    　}
    }

    vector, list, basic_stringなどの標準ライブラリに含まれるタイプについてはあらかじめswapが定義されていますので、通常は各メンバについてstd::swapを呼ぶだけでよいはずです。


    注意３

    _Move_operation_category の特殊化は、おそらく、std名前空間内で行わないとマズいと思います。理由をシャキっと説明できるとカッコイイのですが、ごめんなさいできません。
    2008-09-07 00:14  nice!(0)  コメント(0) 
    共通テーマ：パソコン・インターネット

    Swaptimizationでmove先取り？その１　[プログラミング]

    c++ネタです。

    c++の次期規格がc++0xという名前で検討されています。その中の目玉コンセプトのひとつに move semantics というのがあります。機能名でいうと右辺値参照(Rvalue reference)となります。

    c++で安全なコードを書こうとすると、ポインタやメモリ管理をラッピングすることになります。STL(標準テンプレートライブラリ)にあるvectorやlist、auto_ptr(shared_ptr)がそれです。これらを使うとコードがとても簡潔＆安全になるのですが、時折、無駄なコピーが起こることがあります。もちろん回避可能です、しかし、簡潔さが失われてしまうという問題があります。move semanticsは簡潔さと安全さを失わず、無駄コピーをなるべく回避しようというものです。

    具体的例でいうと、 vector のリサイズ時の動作です。 vectorは長さにあわせてメモリを動的に確保するのですが、長くなったときに新しいメモリ領域に今までのをコピーしてやる必要があります。これは本来「移動」でよいはずですが、c++のオブジェクトには「移動」演算子はありませんので、vectorの各要素についてコピーを繰り返します。

    (1)新しいメモリ領域を確保
    (2)各要素について旧領域から新領域へコピー　　←もったいない！！！
    (3)古いメモリ領域を解放

    コードっぽく書くとこうなります（実際にこんなコードというわけではないです）
    T* newarea = new T[newsize];
    for ( size_t i = 0 ; i < oldsize ; ++i ) {
    　newarea[i] = area[i]; // コピー操作
    }
    delete [] area;
    area = newarea;

    クラスTがメモリをたくさん確保するようなものである場合、コピーのコストはバカになりません。といいますか、ソフトウェアの実行速度の低下要因のうち「無駄なメモリコピー」「無駄なzero fill」が占める割合は、かなり高いと思います。メモリとCPU速度の差が激しい限りこの傾向は変わらないと思います。このネタはまたいずれ・・・

    で、move semanticsはその解決を狙っています。でも、c++0x規格はまだ策定中ですし、実装がそろうのはもっと先です（gccは試験的にやっています）。

    とはいえ、何とかしたい。なんとかならんのか。ということで、目を付けられたのが std::swap です。

    ここまでが前フリです。（ふう）

    std::swapは、STL(標準テンプレートライブラリ)の定義では「２つのオブジェクトの内容を交換する」です。

    デフォルトの定義では、swap(A,B)は、AをテンポラリTにコピーし、BをAにコピーし、BにTをコピーします。
    template<typename T>
    void std::swap(T& lhs, T& rhs) {
    　T tmp;
    　tmp = lhs;
    　lhs = rhs;
    　rhs = tmp;
    }

    主だったSTLの実装では、vectorやlist、basic_stringなどについては、「ポインタの付け替え」実装で特殊化されているようです。例えばlistについては、メンバ変数は「HEAD要素へのポインタ、TAIL要素へのポインタ、現在のサイズ」でしょうから、これら3つのメンバ変数を入れ替えてしまえばいいわけです。

    ここまでの説明でピンと来た方もいらっしゃるかもしれません。

    そう、swapでmoveを代用するのです。

    VisualStudioの開発チームのVCグループでは、これを Swaptimizationと呼んでいるようです。

    http://blogs.msdn.com/vcblog/archive/2008/08/11/tr1-fixes-in-vc9-sp1.aspx

    http://blogs.msdn.com/vcblog/archive/2008/01/08/q-a-on-our-tr1-implementation.aspx

    長くなったので分割します・・・
    2008-09-06 23:02  nice!(0)  コメント(0) 
    共通テーマ：パソコン・インターネット

    .NET Frameworkライブラリのソースコードへのアクセスが可能に　[プログラミング]

    なりました。

    直接ダウンロードするのではなく、Visual Studioのデバッガ上で参照できるようになっただけです。まどろっこしい・・・

    方法はこのあたりを参照してみてください。

    http://www.atmarkit.co.jp/fdotnet/insiderseye/20080222sourcecode/sourcecode.html

    デバッグ時に、オンデマンドでソースサーバからダウンロードするようです。適当にデバッグして、早速ダウンロードフォルダを覗いてみましたが・・・

    フォルダがあるけどソースファイルがない

    イチイチ削除しているようです。ああもう。そこで、デバッグ中に覗くと、お、あった。しめしめ、コピーするか・・・

    共有違反でコピーできない

    イヤガラセですか。

    仕方ないのでIDE上で表示中にctrl+aしてコピーしました。

    あほらしいですね・・・自動コピーするアドオンを書いてやろうか、という気になりましたがやっていません。

    ところでこの方法でのコピーってライセンス違反でしょうか。ダメだったらヤだなあ。

    だって、オフラインでじっくり読みたいじゃないですか。

    本題は以前のエントリで書いた、RSA Keypairの読み込みなんですがまた次回に・・・
    2008-05-31 14:54  nice!(1)  コメント(0) 
    前の10件 | -

    カスタムぺイン1

    この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。