🀄
PHP配列操作の注意点
はじめに
競技プログラミングの本を解いている時に処理時間がかかりすぎてTLEになってしまいました。原因は配列に要素を追加する時にarray_unshift関数を使っていたことでした。いつもどのように処理されているかまでは考えていない部分があったのでこれを機に少し調べてみようと思いました。もし間違いなどがありましたら指摘していただけるとありがたいです。
実際に試してみる。
array_unshiftの構文は以下のようになっています。
array_unshift(array &$array, mixed ...$values): int
第１引数には要素を追加する配列を第２引数には追加する要素を入力します。
では、実際に簡単なコードを使って試してみたいと思います。
forループを使用して、空の配列に０を１万回追加する実装をします。
- array_unshiftを使用する場合
<?php
$time_start = microtime(true);
$numbers_array = [];
for($i = 0; $i < 10000; $i++){
array_unshift($numbers_array, 0)
}
echo count($numbers_array);
$time = microtime(true) - $time_start;
echo "処理時間：".sprintf("%.20f", $time)."秒";
// 処理時間：0.4079577922821044921
- array_unshiftを使わないで要素を追加する場合
<?php
$time_start = microtime(true);
$numbers_array = [];
for($i = 0; $i < 10000; $i++){
$numbers_array[] = 0;
}
echo count($numbers_array);
$time = microtime(true) - $time_start;
echo "処理時間：".sprintf("%.20f", $time)."秒";
// 処理時間：0.0057468414306640625
だいぶ違いますね。array_unshiftの場合は配列の順番は変更しないように要素を先頭に追加します。そのため、配列の全ての要素を移動させるため、時間がかかってしまうみたいです。
まとめ
私自身、内部関数やフレームワークにあらかじめ備わっている機能に関しては、どのような処理がされているかまで意識していることはあまりありませんでした。これからは内部的な部分を完全には理解しなくてもどんなふうになっているかなど見ていくことは大切だなと感じました。
Discussion