Garbage Collection

[C++/CLI]Stringの糸口

出水洸太郎 — Fri, 28 Nov 2008 06:11:00 GMT

意外に、C++/CLIで検索する方がいるようなので、
C++/CLIを始めたときに混乱していたネタを投下します。

C++/CLIを始めてから、よくわからない印象を持ったのが文字列の扱いです。
ハンドル型なのに実体のような動きをする存在で、不思議に見えました

System::String ^str1 = gcnew System::String("abc");
System::String ^tmpstr = str1;

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

str1 = gcnew System::String(str1 + "def");

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

初期化はchar*と同じようにできますが、なぜか足し算もできます。
演算子オーバーロードでうまくやっているんでしょうと理解していました。

そして、いちばん混乱したのがこれ。

System::String ^str1 ="abc";
System::String ^tmpstr = str1;

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

str1 += "def";

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

もし、char *のように振舞うのであれば、
2回目のWriteLineでは両方とも"abcdef"が出力されないといけませんが、
実際には、str1は"abcdef"、tmpstrは"abc"と出力されます。

しかし、ハンドル型なので実体を持ち運んでいるわけではないはず。
Stringだけ特殊な扱いを受けている？？

どうにも解せないときに出会ったキーワードが以下の2つ。
・ボックス化
・String不変

キーワードにしたがって、上のソースを書きなおしてみます。

System::String ^str1 = gcnew System::String("abc");
System::String ^tmpstr = str1;

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

str1 = gcnew System::String(str1 + "def");

Console::WriteLine(str1);
Console::WriteLine(tmpstr);

まず最初の変数初期化ですが、ボックス化によりgcnewが付与されます。
ですから、char*のように先頭ポインタだけを指しているわけではありません。

そして、+=演算子。
これがもう一つのString不変です。
Stringの内容が変化を受ける場合、そのつど新しい領域が確保されます。
ですから、後半のstr1とtmpstrでは指しているアドレスが違うわけでです。

String不変の観点でSystem::Stringを調べてみると、
ハンドル型の変数を書き換えられない状況では、ReadOnlyになっています。
（たとえば、[]演算子）

StringはUnicodeを格納するクラスなので、char*やstd::stringとは違い、
固定文字列を持ち運ぶもの、と理解しておくといいでしょう。

あさめしパクパクにゃ～

出水洸太郎 — Fri, 21 Nov 2008 06:38:00 GMT

検索くんを導入してみました。

RSSから見ている人には一度サイトを見てください。
左のところにこんなものが追加されています。

要は、YahooやGoogleから飛んできたユーザーがいた場合、
そのキーワードを拾って、順位を表示するプラグインです。

ちなみに、私のBlogはこんな感じ。
「女装」とか「変態」とかのキーワードで引っかかることもない
非常に健全なBlogとなっているようです。

Blogの設定変更でRefererが収集されなくなったので、
残念だなーと思っている人には導入してみてはどうでしょうか。

11/15LT大集合お疲れ様会

出水洸太郎 — Mon, 17 Nov 2008 20:56:00 GMT

11/15のライトニングトークお疲れ様でした
さすがに50個連続は疲れますね～。

私のLTは「共通鍵暗号とRSA」でした。
そこで使った資料を公開します。
ダウンロード

LTで見かけた便利なんじゃない？と思ったソフトを書いておきます。

zio3さんプロパティ設定に新提案 PropatyMatrix
PropatyMatrix
VisualStudioのフォームエディタのプロパティを
表形式で編集できるプラグインです。
まじでいいですよ、これは！

こくぶんまさひろさん C#で遊んでみた
MIDIYoke
仮想MIDIデバイスソフトです。
この仮想デバイスにメッセージを投げて
シーケンサー側にMIDIインプットの信号として渡すことで
簡単に連携できるようになるわけですね。

本当は、ReWireなんか使えるといいのですが、
個人にはライセンス発行してくれないみたいなので…。

[数学]余りものに福がある

出水洸太郎 — Sat, 15 Nov 2008 00:38:00 GMT

コンピュータで負の数を表そうとすると2の補数表現という方法を良く使います。
たとえば、8bit型の変数に-60という値を入れたいとき、
196という値を代わりに入れて計算します。

この196という値は256-60という計算で出します。
256は8bitでぎりぎり表せない数値です。

数学では、合同式というもので表現します。
先ほどの、-60と196を数式にすると以下になります。

-60 ≡ 196 (mod 256)

256で割った余りの世界では、-60と196は同じという意味です。
＝ではなく合同を意味する≡を使います。

-60と196が同じなのか、足し算で検証します。
90-60 ≡ 90＋196 ≡ 286 ≡ 256＋30 ≡ 30 (mod 256)

合同式の面白い所は、分数を整数で表わすことが出来る点です。
2/3 ≡ 258/3 ≡ 86 (mod 256)
∵ 2 ≡ 258 (mod 256)

ということで、2/3と86が同じという意味になりました。
ちょっと計算してみましょう
60×(2/3) ≡ 60×86 ≡ 5160 ≡ 256×20＋40 ≡ 40 (mod 256)
2/3の代わりに86を使っても同じ40という答えになりました。
これで256の余りの世界では、2/3と86が同じという事がわかると思います。

1/3を整数に直すときは、1の代わりに257を入れても割りきれません。
そこで、次の513を入れて171という整数にできます。
1/3 ≡ 513/3 ≡ 171 (mod 256)

しかし、1/2は整数にすることができません。
1/2 ≡ 257/2 ≡ 513/2 (mod 256)

このように、必ずしもすべての分数が整数に変換できるわけではありません。
1/2のパターンを見れば、整数に出来る分数と出来ない分数の条件が
おぼろげながらわかる気がしますね。

さらに、四則演算だけでなく、階乗についても面白い性質があります。
以下の表を見てください。

右は3乗、左は7乗して11で割った余りです。
それぞれ、お互いの逆関数になっていることに気づくでしょうか。
例えば、n=3のとき、3乗すると5です。
そして、5を7乗すると3になっています。

11の余りの世界では、立法根(3乗根)と7乗した値が同じなのです。
こうやって、n乗根をm乗に変換できるのも合同式の性質です。

この3と7の値を求めるには、こんな式があります。
a×b ≡ 1 (mod (p - 1))　　但し、pは素数

今回、a=3, b=7,p=11です。
当てはめてみましょう
3×7 ≡ 21 ≡ 1 (mod 10)

この式に当てはまれば、別の数でも成り立ちます。
これも分数と同様、すべてのn乗根が変換できるわけではありません。

このように、合同式にはいろいろ面白い世界があります。
その面白い世界を近いうちに紹介します。

[アルゴリズム]クイックソートの広さ

出水洸太郎 — Thu, 13 Nov 2008 23:04:00 GMT

ネタ元>再帰をループに変換

クイックソートとは以下の順序でソートを行うものです。
(1)ある要素を取り出し、その要素より小さいグループと大きいグループで分類する
(2)それぞれのグループに対し、要素の数が1個になるまで(1)を繰り返す
このクイックソートが必要とするメモリ量、すなわち空間計算量を考えてみましょう。

要素を2つに分割した後、両方を同時に処理することはできません。
ですから、一方はいったん置いて他方を処理します。
その処理中にまた2つに分割されるため、いったん置いたうえにさらに置くことになります。
図で表現するとこんな感じですね。

このようにうまく二等分できれば一時領域は10段もあれば十分です。
この一時領域をスタックサイズと呼びます。

別の場合のスタックサイズを考えてみます。
こんな場合はどうでしょうか。

先ほどと違い、うまく分割することが出ていません。
そして、このペースだとスタックサイズは500段必要です。

一体スタックサイズは何段用意しておけばいいのでしょうか。
出来るだけスタックサイズを小さくする方法を考えてみます。

このスタックは処理中のものが終了するまで積まれ続けるわけです。
いつ終了するんでしょうか。
それは、処理中の要素数が2個以下になるまでです。

それならば、早く処理中の要素数を減らせばよいわけです。
2つに分割したとき、どちらをスタックに積み、どちらを処理中にするかは
自由に決められるため、要素が多い方をスタックに積んでしまえばいいのです。

それを図示しました。

いずれも4:1のグループに分かれていますが、左の方はもうすぐ処理が終わりそうです。
このように、アンバランスに別れた方がスタックに積む量が減るため、
最もスタックが必要なパターンは二等分されるパターンです。
そして、二等分された場合、スタックサイズはlog2(N)必要です。

よって、クイックソートの空間計算量は最悪の場合でもO(logN)です。

なお、ピボットに使われた要素は処理済みにするのが好ましいため、
1000個は499個＋1個＋500個のように3つに分けられますが
今回は分かりやすくするため、それを無視しています。

[C++]進数いろいろ

出水洸太郎 — Fri, 07 Nov 2008 22:13:00 GMT

C言語には10進数以外にもいろんな進数表現で数値を指定できます。
それを今回まとめてみました。

#include <iostream>
using namespace std;

int main(){
  // 10進数指定
  cout << 123 << endl;

  // 8進数指定
  cout << 0123 << endl;

  // 16進数指定
  cout << 0x123 << endl;

  // 謎進数指定
  cout << 0e123 << endl;

  return 0;
}

本当にいろんな指定ができますね～。

#片桐さんに感謝しつつ、混乱させるエントリーを書いてみる

告知いろいろ

出水洸太郎 — Fri, 07 Nov 2008 07:20:00 GMT

[東京勉強会#26 LT大集合 (11/15)]
ついに50人スピーカーが実現した東京勉強会です。
こちらで私も5分間何かを話します。

すべて5分ですから、余り重い話はないと思います。
初めての方やプログラム関連はあんまり強くないという方も
安心して参加できる内容だといいな…そんな内容のはずです。

内容/タイトルについては当日あけてお楽しみに！って事なので
正直私も知らないんですよね…。

私の内容も秘密なんで、何を話すかは言えませんが
言葉は知っているけど、仕組みは知らないよな～って事に関する話をしたいと思います。

あ、王子がトリだ！期待してます！！

[大阪勉強会 #25 (12/13)]
こちらはまだ大分先の話ですが、こちらでスピーカーやります。
私にとって初の大阪で、いろいろ楽しみです。
なんでも、普段の勉強会とは違う趣向みたいです。

ここでは、ゲームのあたり判定の話をやります。
複雑な形をしている者同士がぶつかる時や、ロープを使って進んでいくゲームなんかを作る時に
役に立つ話になるんじゃないかと思います。

[コミックマーケット C75]
どーせ当選しないよな～と思いつつ当選してしまったコミケです。
場所は｢12/29(二日目) 西や-15b にじけん｣です。

PSP関連の事をまとめたものを出します。

コミケが入ったことでめちゃくちゃ忙しい…本当に出せるのかしら？
ただいまワードの勉強中…

[PSP]こんにちはアイコン

出水洸太郎 — Mon, 03 Nov 2008 18:34:00 GMT

前回、アイコンの事を書きましたが、実はもっと設定できます。
ですが、ちょっと試すのが面倒とか大変とかで試していないので、
備忘録程度のメモとして残しておきます。

PSP_EBOOT_SND0
ゲームによっては選択すると音楽が流れ始めるものがあります。
その音楽を指定します。

フォーマットはAT3。
一般的なフォーマットではないです。
作成する方法はあるのですが、ちょっと面倒なので割愛します。

PSP_EBOOT_ICON1
これは、アイコンが選択されたとき、
アイコンの中をアニメーションさせる項目です。

フォーマットはPMF。
やはり一般的なフォーマットではありません。
これも作成する方法はあるのですが、やっぱり面倒なので割愛します。

PSP_EBOOT_UNKPNG
透過PNGを指定します。

一部のゲームでは右下の方にゲームの説明が表示されることがあります。
これは、良く見ると背景が表示されたあと一瞬遅れて表示されます。
その指定の項目です。

フォーマットは310x180の透過PNGファイルです。
……それにしても、UNKってなんだろう？UNKNOWN？？

[PSP]出だしが肝心

出水洸太郎 — Mon, 03 Nov 2008 11:44:00 GMT

PSPでそのままプログラムを作ると、XMBではこんな感じで表示されます。

ちょっと殺風景ですね。
今回は、PSPのアイコンを作成する方法です。

まず、アイコンにしたいファイルを作成します。
サイズは140x80でPNG形式で保存します。
こんな感じ。

また、背景も作成し、480x272のPNG形式で保存します。

そして、makefile に以下の二行を入れます。

PSP_EBOOT_ICON = icon.png
PSP_EBOOT_PIC1 = back.png

これで再度実行ファイルを作ります。
makefileを書き換えただけだと、変更なしとして再コンパイルされないので
"make clean all"と入力して再コンパイルしてください。

これらを組み込んだあとはこうなります。

背景を指定した場合、プログラムタイトルが表示されなくなってしまうので、
背景側にプログラムの名前を入れるようにしましょう。

[アルゴリズム]マルチコア

出水洸太郎 — Thu, 30 Oct 2008 06:33:00 GMT

ネタ元＞WindowsとC++：高性能アルゴリズムについて調べる

上記の記事を読むと、マルチコアで動作する時、
同じコアで実行するメモリは近くに配置し、
違うコアで実行するメモリは遠くに配置するべき、と書いています。

さて、以前書いたシェアソートの並列動作なのですが、
横ソートにおいては上記のマルチコア動作に向くメモリ配置になっています。

しかし、縦ソートに至っては並列動作に向かないパターンです。
良くないパターンとして紹介されている物と全く同じです。

今回の場合は”#pragma omp parallel for”を使ったものなので
自分でカリカリ内部動作を書いた場合とは違うのかもしれません。
ただ、キャッシュの読み直しという単語がちらほら見えるので、
ハードウェアの仕様のような感じで、ソフトウェア側でどうにかならない気がします。

シェアソートの縦ソートが遅いとなるといよいよ出番もないですね…。

#ということで、教えて詳しい人！