【PHP】全ての組み合わせを取得する関数の配列要素数の上限

「【PHP】２進数で全ての組み合わせを取得する」の補足記事です。

この記事のゴール
元配列要素数上限の検討項目
PHPにおける配列要素数の上限
getAllCombinations() の組み合わせ数上限
1. 整数のオーバーフロー ¶
実行環境の使用可能メモリから見た上限
まとめ

この記事のゴール

組み合わせを取得する元の配列の要素数上限が検討できる

元配列要素数上限の検討項目

元配列と呼んでいるのは、この関数の引数の $items です。

$items = ['A', 'B', 'C', 'D', 'E'];

この元配列の要素数の上限については、

次の各観点を総合した検討が必用と思われます。

PHPにおける配列要素数の上限
getAllCombinations() の組み合わせ数上限
実行環境の使用可能メモリから見た上限

PHPにおける配列要素数の上限

PHPで扱える配列要素数の上限ですが、

結論から言うと、配列インデックスとして使用している

整数の上限値です。

検証記事を作成していますので参考にしてみてください。

整数の上限値は実行環境によって変わりますが、

PHPの「定義済みの定数」である PHP_INT_MAX で取得できます。

32bit-system: 2 ^ 31 – 1 === 2147483647
64bit-system: 2 ^ 63 – 1 === 9223372036854775807

これは配列インデックスとなる整数の上限値であり、

配列インデックスは、通常は 0 ～ PHP_INT_MAX となるので、

扱える配列の要素数としては、

32bit-system: 2 ^ 31 === 2147483648 個
64bit-system: 2 ^ 63 === 9223372036854775808 個

と考えることができます。

尚、ちょっと無理して配列インデックスを整数の下限値から始め、

PHP_INT_MIN ～ PHP_INT_MAX　とすれば、

扱える配列の要素数は上記の２倍、つまり、

32bit-ssytem: 2 ^ 32 === 4294967296 個
64bit-syste: 2 ^ 64 === 18446744073709551616 個

となります。

getAllCombinations() の組み合わせ数上限

関数内で組み合わせ総数を計算している箇所があります。

    $numberOfAllPatterns = 2 ** $count;

これは整数値なので、上限値は PHP_INT_MAX です。

が、挙動としてはかなり注意が必用です。

公式ドキュメントの整数のページにあるように、

整数のオーバーフロー ¶

int型の範囲外の数を指定した場合、かわりに floatとして解釈されます。また、結果が int型の範囲外の数となるような計算を行うと floatが代わりに返されます。
PHP: 整数 – Manual

PHP_INT_MAX を超えてもエラーは出ず、

この変数は浮動小数点数を扱うことになります。

この $numberOfAllPatterns の計算を行う前に

元配列の要素数チェックが必用です。

前段の通り、PHP_INT_MAX は次の通りです。

32bit-system: 2 ^ 31 – 1 === 2147483647
64bit-system: 2 ^ 63 – 1 === 9223372036854775807

$numberOfAllPatterns が PHP_INT_MAX を超えないように

するためには、$count が

32bit-system: $count < 31
64bit-system: $count < 63

である必要があります。

つまり、元配列の要素数の上限は、

32bit-system: 30個
64bit-system: 62個

となります。

実行環境の使用可能メモリから見た上限

一応、配列要素数の上限だけを見れば、

かなり膨大な数の配列要素を扱えるように見えますが、

実際には実行環境の使用可能メモリの方が先に尽きるケースが多いと思います。

筆者の環境の場合、PCの搭載メモリは8GB、古いですが、

Windows10 + Ubuntu2.11で環境構築しており、PHPはaptコマンドでインストールしています。

php.ini 等の設定は全てデフォルト状態です。

メモリ上限は次の通り「無し」になっています。

~/work/phptest$ php -i | grep memory_limit
memory_limit => -1 => -1

PHP: コア php.ini ディレクティブに関する説明 - Manual

当関数内の配列 $combination へ要素追加している次の行に

echo memory_get_usage() . "\n";

を追加して、メモリの使用量を追跡したところ、

...(省略)...
5837288352
5837288352
5837288728
5837289104
5837289104
Killed

OSによって実行プロセスが強制終了されてしまいました(T_T)

表示の数値は実行プロセスのメモリの使用バイト数なので、

5837289104 bytes / 1024 / 1024 / 1024 ≒ 5.4 GB

を最後に、それを超えた時点で強制終了となっています。

関数の引数として使用した配列 $items は次の通りです。

$items = [
    'A01', 'A02', 'A03', 'A04', 'A05', 'A06', 'A07', 'A08', 'A09', 'A10',
    'B01', 'B02', 'B03', 'B04', 'B05', 'B06', 'B07', 'B08', 'B09', 'B10',
    'C01', 'C02', 'C03',
];

要素数は２３です。

計算上の組み合わせ総数は、 2 ^ 23 = 8,388,608 個です。

PHPの配列要素数上限には遥かに届かない「微々たる数」です。

要素の値によってメモリの使用量は変わりますし、

この関数でのメモリの使い方に良くない点もあります。

が、結局は前述の配列要素数上限よりは、

メモリ使用量によって組み合わせ数の上限が左右される

と言えると思います。

ちなみに、$items の要素数を２３から２２に減らして実行し

標準出力をファイルに保存したところ、

保存したファイルサイズは１７６MBになりました。

まとめ

無理矢理感はありますが、

上記より、この関数に投入する配列の上限数は、

実行環境にも左右されますが、

筆者と同じような環境であれば、元配列 $items の要素数は

２２個以下にしておくのが無難でしょう。

64bit-systemでの元配列の要素数上限63個に対して

約３分の１ですね。

しかしながら、２２個の要素の組み合わせ総数は、

2 ^ 22 = 4,194,304 個です。

約４百２０万個ですよ。数えたくないですね。

リファクタしてメモリの使用量を節約したらどうなるか？

は今後の課題とさせていただきます。