[TOC］

コードチューニングの実践

アルゴリズム設計とコードチューニングを紹介したプログラマー向けの本「Programming Pearls」を読み終えたところですが、じっくり読む価値があります。この投稿では、代わりに、この本で紹介されているランダムサンプリングとコードチューニングのテクニックを含む演習として、確率問題が使われています。この記事で取り上げるトピックは以下の通りです：

問題：A、B、C、D、Eの5枚のカードがあり、2枚引くたびに5回抽選が行われ、抽選されたカードにA、B、C、D、Eがすべて出る確率を求めなさい。

I. 問題解決への数学的アプローチ

まず、この問題を確率論的に解くことが試みられます。順方向確率 PPを 直接計算すると、プロセスは非常に複雑になります。逆事象の確率 Pを 計算し、 P=-P=1-Pで 解けば、処理はずっと単純になります。順事象A,B,C,D,Eがすべて引かれたカードに現れることを事象AAとすると、逆事象 Aは 、A,B,C,D,Eのうち少なくとも1枚が引かれたカードに現れないことです。 $P$ここで、 $\bar{P}$ P =1-P。

最初の5つの抽出は5つの独立した事象であり、すべての可能な事象の数は $\times \times \times \times$C52xC52xC52xC52xC52xC52xC52=105 。

次に、イベント Aの イベント数を考えます。これを5つのケースで考えてみましょう：

• シナリオ 1: 引かれたカードには A、B、C、D しか含まれていません；
• シナリオ2：引かれたカードにはA、B、C、Eしか含まれていません；
• シナリオ3：引かれたカードにはA、B、D、Eしか含まれていません；
• シナリオ4：引かれたカードにはA、C、D、Eしか含まれていません；
• シナリオ5：引かれたカードにはB、C、D、Eしか含まれていません；

A、B、C、Dのデックから一度に引けるカードは2枚だけなので、ケース1のイベント数は ××××C42×C42×C42×C42×C42と なります。

ケース 2 のイベント数は一見 ××××C42×C42×C42×C42×C42 の ように見えますが、ケース 1 のイベントの一部がここに含まれていることを考慮する必要があります。- 引かれたカードには A、B、C しか含まれていないので、これらの重複も差し引く必要があり、 A、B、C から一度に引けるのは 2 枚なので、この種の事象の数は ×××C32×C32 となります。 ×C32×C32×C32 となります。従って、ケース 2 のイベント数は ×××-×××C42×C42×C42×C42-となります。 C32×C32×C32×C32×C32；

3の場合も同様に、繰り返されるイベントの数が考慮され、3しか含まれていないカードの抽選は、以下の4つのケースで発生する可能性があります。

• シナリオ3.1：A、B、Dのみ抽選；
• シナリオ3.2：A、B、Eのみ抽選；
• シナリオ3.3：A、D、Eのみ抽選；
• シナリオ3.4：B、D、Eのみ抽選；

ケース3.1とケース3.2は、ケース1とケース2の事象に既に含まれているので、事象数からも差し引かれます。一見すると、 ×××-××××××C42×C42×C42×C42-2×C32×C32×C32×C32×C32 。ただし，3.1 と 3.2 の場合，引き出されたカードには A と B しか含まれていないため，2 回引かれ，1 回足されることになりますが，幸いなことにその数は 1 回だけ $A$． C42×C42×C42×C42×C42-2×C32×C32× xx C32xC32xC32+1；

ケース4のイベントの数は、繰り返されるイベントの数と同様に考えられ、3つしか含まれていないカードの抽選は、次の4つのケースで発生する可能性があります。

• シナリオ4.1：A、C、Dのみ抽選；
• シナリオ4.2：A、C、Eのみ抽選；
• シナリオ4.3：A、D、Eのみ抽選；
• シナリオ4.4：C、D、Eのみ抽選；

シナリオ 4.1、4.2、4.3 は、すでにシナリオ 1、2、3 に含まれているので、これら 3 つのシナリオのイベント数から、再び余分なイベントが差し引かれたことを考慮して、差し引く必要があります。ケース 4.1 とケース 4.2 には重複するイベントが 1 つあります-引かれたカードには A と C しか含まれていません。ケース 4.3 には、ケース 4.1 と 4.2 と重複するイベントが 2 つあります-引かれたカードには A と D しか含まれていませんし、引かれたカードには A と E しか含まれていません、E. したがって、ケース4のイベント数は、 $\times \times \times \times$×××××++C42×C42×C42×C42×C42×C42×C42-3×C32×C32×C32×C32×C32×C32+1+2;

状況5 イベントの数 同様に、繰り返されるイベントの数を考慮する必要があります。

• シナリオ5.1：B、C、Dのみ抽選；
• シナリオ5.2：B、C、Eのみ抽選；
• シナリオ5.3：B、D、Eのみ抽選；
• シナリオ5.4：C、D、Eのみ抽選；

シナリオ 5.1、5.2、5.3、5.4 は、シナリオ 1、2、3、4 のイベントに含まれるため、これら 4 つのシナリオのイベント数も減算されます。ケース5.1とケース5.2には重複するイベントが1つあります -引かれたカードにはBとCしか含まれていません。ケース5.3にはケース5.1と5.2の重複が2つあります -引かれたカードにはBとDしか含まれていませんし、引かれたカードにはBとEしか含まれていません。シナリオ5.4には、シナリオ5.1、5.2、5.3と重複するイベントが3つあります-引かれたカードにはCとDだけ、引かれたカードにはCとEだけ、引かれたカードにはDとEだけです。したがって、ケース5のイベント数は $\times \times \times \times$××××+++C42×C42×C42×C42×C42-4×C32×C32×C32×C32×C32×C32+1+2+3;

Aの イベント数の最終計算は、ケースI、II、III、IV、Vのイベント数の合計：

××××C42×C42×C42×C42×C42+××××-××××+C42×C42×C42×C42×C42-C32×C32×C32×C32×C32+××××-×××××++C42×C42×C42×C42×C42×C42-2×C32×C32×C32×C32+1$\times \times \times \times$-×××××+++C42×C42×C42×C42×C42-3×C32×c32×c32×c32+1+2+×××-××××++++c42×C42×C42×C42×C42-4×C32×C32×C32×C32×C32+1+2+3=×××××-×××××+=5×C42×C42×C42×C42×C42-10×C32×C32×C32×C32×C32×C32+10=×-×+=5×65-10×35+10==

$\bar{A}$したがって、逆順の事象A,B,C,D,Eのうち少なくとも1つが描かれたカードに現れない確率は、 P=÷=P =÷105=0.46360です。 最終的に正順の事象A,B,C,D,Eがすべて描かれたカードに現れる確率は、 P=- =P=1-0.46360=0.53640 です。

シミュレーション検証のプログラミングアプローチ

結果は計算されていますが、実際に確率的なものに手を出してからずいぶん時間が経っているので、まだ正しいかどうかわかりません。上記の計算結果を検証するにはどうすればいいのでしょうか？それは、事象のサンプリングをシミュレートする手順を踏むことで可能です。事象の繰り返しがある桁に達すると、自然と正しい答えにどんどん収束していきます。そこでこの章では、前章の計算の正しさを検証するためのプログラムを使います。

-(void)testSampling{
 int n = 1e6;
 NSMutableSet* selected = [NSMutableSet new];
 int allFive = 0;
 static NSDate *start, *end;
 start = [NSDate date];
 for(int i = 0; i < n; i++){
 for(int j = 0; j < 5; j++){
 int select1 = arc4random()%5 + 1;
 [selected addObject:@(select1)];
 int select2;
 do {
 select2 = arc4random()%5 + 1;
 }while (select2 == select1);
 [selected addObject:@(select2)];
 }
 if(selected.count == 5){
 allFive++;
 }
 selected = [NSMutableSet new];
 }
 end = [NSDate date];
 NSTimeInterval seconds = [end timeIntervalSinceDate:start];
 double result = 1.0 * allFive / n;
 NSLog(@"シミュレーションの回数%d;  %f;  %f", n, result, seconds);
}

上記の手順の平均実行時間は4.30秒で、結果は0.635485です。第1章で計算した0.635485に近い結果ですが、まだ乖離があり、精度は判断できません。より精度の高い結果を得るためにシミュレーションの回数を増やし、nの値を10億回としたところ、最終的なシミュレーション結果は0.635400989732となり、基本的には第1章の計算結果に限りなく近い結果となりました。

III. アルゴリズムのチューニング

NSMutableSet インスタンスを構築する testSampling メソッドのメモリオーバーヘッ ドを考慮し、描画されたサンプルの値を記録するために 5 ビット長のビットマップを使用します。例えば、1<<0の2進数で1であればカードAが選択されたことを意味し、1<<1の2進数で2であればカードBが選択されたことを意味します。最終的なビットマップが2進数、すなわち31の場合、カードA、B、C、D、Eが選択されます。次の testSampling1 アルゴリズムは、平均実行時間を 3.08 秒に短縮します。

-(NSTimeInterval)testSampling1{
 int n = 1e6;
 char selected = 0;
 int allFive = 0;
 static NSDate *start, *end;
 start = [NSDate date];
 for(int i = 0; i < n; i++){
 for(int j = 0; j < 5; j++){
 int select1 = arc4random()%5;
 selected |= 1<<select1;
 int select2;
 do {
 select2 = arc4random()%5;
 }while (select2 == select1);
 selected |= 1<<select2;
 }
 if(selected == 31){
 allFive++;
 }
 selected = 0;
 }
 end = [NSDate date];
 NSTimeInterval seconds = [end timeIntervalSinceDate:start];
 double result = 1.0 * allFive / n;
 NSLog(@"シミュレーションの回数%d;  %f;  %f", n, result, seconds);
 *onceResult = result;
 return seconds;
}

上記の testSample メソッドでは、乱数生成の安全性から arc4random を使用していますが、その速度はランダム関数よりも 90% 近く遅いため、arc4random をより効率的なランダム関数に置き換えてみると、testSampling2 の平均実行時間は0.29秒に圧縮され、ミリ秒レベルに達します。この時点で、10億スケールの抽出処理をシミュレーションしても290秒しかかかりません。内部ループを分割することで、平均実行時間はさらに0.26秒に圧縮できますが、プログラムコード量が増えるため、この最適化は実施しません。

-(NSTimeInterval)testSampling2{
 int n = 1e6;
 char selected = 0;
 int allFive = 0;
 static NSDate *start, *end;
 start = [NSDate date];
 for(int i = 0; i < n; i++){
 for(int j = 0; j < 5; j++){
 int select1 = random()%5;
 selected |= 1<<select1;
 int select2;
 do {
 select2 = random()%5;
 }while (select2 == select1);
 selected |= 1<<select2;
 }
 if(selected == 31){
 allFive++;
 }
 selected = 0;
 }
 end = [NSDate date];
 NSTimeInterval seconds = [end timeIntervalSinceDate:start];
 double result = 1.0 * allFive / n;
 NSLog(@"シミュレーションの回数%d;  %f;  %f", n, result, seconds);
 return seconds;
}

上のdo-whileループに囲まれたランダム関数は複数回実行される可能性があり、ランダム関数には時間がかかるのでサンプリングを調整しましょう。最初にサンプルが抽選されたときに、2回目もそのサンプルが抽選される確率を他のサンプリングされていないサンプルにも広げることで、do-whileループをなくします。しかし、この最適化は期待したほど強力ではなく、数ミリ秒しか性能が向上しないため、ランダム関数自体はまだ比較的効率的であると結論付けることができます。arcrandomの場合、この最適化はより顕著で、効率が約10%向上します。

-(NSTimeInterval)testSampling3{
 int n = 1e6;
 char selected = 0;
 int allFive = 0;
 static NSDate *start, *end;
 start = [NSDate date];
 for(int i = 0; i < n; i++){
 for(int j = 0; j < 5; j++){
 int select1 = random()%5;
 selected |= 1<<select1;
 // 残りのサンプルの抽選確率を4等分する。
 int select2 = random()%4;
 if(select1 < 4 && select2 >= select1){
 select2++;
 }
 selected |= 1<<select2;
 }
 if(selected == 31){
 allFive++;
 }
 selected = 0;
 }
 end = [NSDate date];
 NSTimeInterval seconds = [end timeIntervalSinceDate:start];
 double result = 1.0 * allFive / n;
 NSLog(@"シミュレーションの回数%d;  %f;  %f", n, result, seconds);
 return seconds;
}

概要

• 確率的トピックの正しさを検証するために使用できるランダムサンプリングアルゴリズム；
• ビットマップは数値の集まりを表現するためによく使われ、非常に便利で高性能なデータ構造です；
• arc4random関数は予測不可能な乱数を生成し、より安全ですが、ランダムよりもはるかに遅いです；
• 無作為抽出アルゴリズムは、各サンプルが同じ確率で抽出されることを厳密に保証しなければなりません。