Skyland Ventures tech ブログ

渋谷のVenture Capital Skyland Venturesのいま一番イケてる投資先、nanameue,IncとKaumoの共同技術ブログ

良いアルゴリズムを作るための数学活用

みなさん、初めまして。 nanameue.Inc でiOSエンジニアをしている千葉です。 先週は、nanameue,Inc メンバーと、Kaumoメンバーがすばらしいブログを書いてくれました。 今日は、このブログメンバーで唯一社員の私が担当します。

まずかるく自己紹介をすると、 私は、 nanameue, Inc.で1月28日からインターンでjoinし、10月1日から卒業と同時に社員になりました。 かれこれ、エンジニア暦10ヶ月、初めてのアプリリリースまでは4ヶ月程度かかりましたが、その後、サブプロジェクトとして、10~15くらいはアプリをリリースしました。(ぶっちゃけ正確な数字は不明です) ちなみに、自分の初めて出したアプリを含め、3,4個はユーザーがいなさすぎて、サービス閉鎖しましたが、何個かは、海外ユーザーも含めある程度の規模感になってきました。最近の仕事は、アップデートや、インターン生の管理をしています。

そんなわけで今日のテーマは、良いアルゴリズムを作るための数学活用です。 我々プログラマーという生き物が最も関心があること、それは、良いアルゴリズムを作ることです。 そもそも良いアルゴリズムとは何か。 プログラマ中級者ならだれもが読むであろう、以下の本には、

良いコードを書く技術 ── 読みやすく保守しやすいプログラミング作法(WEB+DB PRESS plusシリーズ)|gihyo.jp … 技術評論社

・保守性が高い

・すばやく効率的に動作する

・正確に動作する

・無駄な部分がない

と4つの定義があります。

そのようなコードを書くために、時に数学の知識を用いると、便利なことがあります。

例えば、1~1000の整数から、素数だけを取り出した配列を作りたいとしましょう。

素数だけを取り出すにはそもそも素数の定義を知らなくてはいけません。(この時点で数学の知識が必要ですが、まだ本番ではありません。)

素数とは、約数が1とその数字のみの数のことです。 例えば2,3,5,7,11,13のような数ですね。

約数の数に注目すると、素数の約数の数は必ず2個になります。

よって、 コードは以下のように書くことができます。

 int divisorCount = 0;
    NSMutableArray * primeNumberArray = [NSMutableArray new];
    for (int i = 1; i < 1000; i ++ ) {
        
        for (int j = 1; j <= i; j ++) {
            if (i % j == 0) {
                divisorCount ++ ;
            }
        }
        if (divisorCount == 2) {
            [primeNumberArray addObject:[NSNumber numberWithInt:i]];
        }
        divisorCount = 0;
    }

結果は、

    2,
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    127,
    131,
    137,
    139,
    149,
    151,
    157,
    163,
    167,
    173,
    179,
    181,
    191,
    193,
    197,
    199,
    211,
    223,
    227,
    229,
    233,
    239,
    241,
    251,
    257,
    263,
    269,
    271,
    277,
    281,
    283,
    293,
    307,
    311,
    313,
    317,
    331,
    337,
    347,
    349,
    353,
    359,
    367,
    373,
    379,
    383,
    389,
    397,
    401,
    409,
    419,
    421,
    431,
    433,
    439,
    443,
    449,
    457,
    461,
    463,
    467,
    479,
    487,
    491,
    499,
    503,
    509,
    521,
    523,
    541,
    547,
    557,
    563,
    569,
    571,
    577,
    587,
    593,
    599,
    601,
    607,
    613,
    617,
    619,
    631,
    641,
    643,
    647,
    653,
    659,
    661,
    673,
    677,
    683,
    691,
    701,
    709,
    719,
    727,
    733,
    739,
    743,
    751,
    757,
    761,
    769,
    773,
    787,
    797,
    809,
    811,
    821,
    823,
    827,
    829,
    839,
    853,
    857,
    859,
    863,
    877,
    881,
    883,
    887,
    907,
    911,
    919,
    929,
    937,
    941,
    947,
    953,
    967,
    971,
    977,
    983,
    991,
    997
)

確かに素数だけとってこれました。

しかしいまのコードには、かなり問題があり、良いコードとは言えないでしょう。

・保守性が高い △

・すばやく効率的に動作する ×(計算量が多すぎる)

・正確に動作する ◯

・無駄な部分がない ×(無駄な計算が多すぎる)

今回のケースでは、1000程度の範囲なので、支障はありませんが、これが10000000になったら、どうでしょう。 かなりの計算量です。

計算量が多いという問題を解決し、良いコードにするためにはどうすれば良いのか。

数学の知識です

そもそも素数は2以外は必ず奇数です。 偶数もすべて計算するのは、時間の無駄。 よって、 for (int i = 3; i < 1000; i +=2 )

とし、最後に2を加える

そうすると、計算量が半分減ります。

また、素数であるかの判定に約数の数を計算するのは無駄です。 iを2からi-1までで割りひとつも割り切れるものがないのが素数という判定法にすれば、ひとつでも割り切れるものがあらわれた時点で途中でチェックをうちきって次の数のチェックに移れるので効率的です。

割る数についてはどうでしょうか?割る数の範囲はもっとけずれるでしょう。 iは奇数に限定しているので割る数は3から奇数のみにできます。 さらにちょっと考えれば分かりますがルートi以上のiの約数はルートi以下のiの約数と対になっているので範囲はルートiまででいいわけです。

そうすると

NSMutableArray * primeNumberArray = [NSMutableArray new];
//iは奇数だけ回す
    for (int i = 3; i < 1000; i +=2 ) {
        BOOL isDivisible = NO;
        for(int j=3;j<=sqrt(i);j+=2)
        {
            isDivisible = i%j == 0;
            if (isDivisible) {
    //一個でも割り切れたら、処理をとめる
                break;
            }
        }
        if (!isDivisible) {
   //素数
            [primeNumberArray addObject:[NSNumber numberWithInt:i]];
        }
    }
  //最後に2をいれる
    [primeNumberArray insertObject:[NSNumber numberWithInt:2] atIndex:0];

実行結果は

(   2,
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    127,
    131,
    137,
    139,
    149,
    151,
    157,
    163,
    167,
    173,
    179,
    181,
    191,
    193,
    197,
    199,
    211,
    223,
    227,
    229,
    233,
    239,
    241,
    251,
    257,
    263,
    269,
    271,
    277,
    281,
    283,
    293,
    307,
    311,
    313,
    317,
    331,
    337,
    347,
    349,
    353,
    359,
    367,
    373,
    379,
    383,
    389,
    397,
    401,
    409,
    419,
    421,
    431,
    433,
    439,
    443,
    449,
    457,
    461,
    463,
    467,
    479,
    487,
    491,
    499,
    503,
    509,
    521,
    523,
    541,
    547,
    557,
    563,
    569,
    571,
    577,
    587,
    593,
    599,
    601,
    607,
    613,
    617,
    619,
    631,
    641,
    643,
    647,
    653,
    659,
    661,
    673,
    677,
    683,
    691,
    701,
    709,
    719,
    727,
    733,
    739,
    743,
    751,
    757,
    761,
    769,
    773,
    787,
    797,
    809,
    811,
    821,
    823,
    827,
    829,
    839,
    853,
    857,
    859,
    863,
    877,
    881,
    883,
    887,
    907,
    911,
    919,
    929,
    937,
    941,
    947,
    953,
    967,
    971,
    977,
    983,
    991,
    997
)

同じ結果になりました。

このコードは最初のコードに比べて断然良いコードと言えるでしょう。

このようにちょっとした数学の工夫があれば、見違えるほどに良いコードになることがしばしばあります。 それも簡単な数学でです。 何も、理系の数学をバリバリ使うということではなく、 ほんのちょっと知っているだけで、ほんのちょっとの工夫であなたのイケてるプログラマーになることができます。

我々の会社には、 外人3人(もうすぐ4人になる予定)、日本人3人、インターン生3人のプログラマがいますが、 全員イケてるプログラマーです。 それは、良いコードをかけるだけではなく、企画やマーケティングもするからです。 プログラマー全員が提案できる会社nanameue, Inc.にぜひインターンしたいという方は、 skylandtechblog@gmail.comまでメール!

よろしくお願いします。 ではまた来週。

次の更新は月曜日です

お楽しみに!!!