こんにちは、エンジニアの @hanhan1978です。
2018/09/26（水）GMO Yoursにて開催された第130回 PHP勉強会＠東京 - PHP勉強会@東京 | Doorkeeperにおきまして、「Laravel Collectionの計算量を調べてみた」というタイトルでLTしてきました。
Laravel Collectionとは？
公式で用意されている配列のラッパークラスです。Webサイトで頻繁に利用するような便利なメソッドが多数用意されていて、データベース検索結果の加工・表示が簡単に出来るようになっています。
登壇内容
Speaker Deckにアップしてあります。
計算量一覧
スライド内に計算量の一覧を写真で貼り付けたのですが、文字が潰れて判読不能でした。 というわけで、下記に改めて一覧でまとめました。
なお、調査対象のLaravelバージョンは5.7です。
https://laravel.com/docs/5.7/collections#available-methods
| メソッド名 | 計算量 | メソッド名 | 計算量 |
|---|---|---|---|
| all | O(1) | nth | O(n) |
| average | O(n) | only | O(n) |
| avg | O(n) | pad | O(1) |
| chunk | O(n) | partition | O(n) |
| collapse | O(n2) | pipe | - |
| combine | O(n) | pluck | O(n) |
| concat | O(n) | pop | O(1) |
| contains | O(n) | prepend | O(n) |
| containsStrict | O(n) | pull | O(n) |
| count | O(1) | push | O(1) |
| crossJoin | O(n3) | put | O(1) |
| dd | O(n) | random | O(n) |
| diff | O(nt) | reduce | O(n) |
| diffAssoc | O(nt) | reject | O(n) |
| diffKeys | O(n) | reverse | O(n) |
| dump | O(n) | search | O(n) |
| each | O(n) | shift | O(n) |
| eachSpread | O(n) | shuffle | O(n) |
| every | O(n) | slice | O(n) |
| except | O(n) | sort | O(n) |
| filter | O(n) | sortBy | O(n) |
| first | O(1) | sortByDesc | O(n) |
| firstWhere | O(n) | sortKeys | O(n) |
| flatMap | O(n2) | sortKeysDesc | O(n) |
| flatten | O(n2) | splice | O(1) or O(n) |
| flip | O(n) | split | O(n) |
| forget | O(n) | sum | O(n) |
| forPage | O(n) | take | O(1) or O(n) |
| get | O(1) or O(n) | tap | - |
| groupBy | O(n2) | times | O(n) |
| has | O(n) | toArray | O(n) |
| implode | O(n) | toJson | O(n) |
| intersect | O(n2) | transform | O(n) |
| intersectByKeys | O(n) | union | O(n) |
| isEmpty | O(1) | unique | O(n) |
| isNotEmpty | O(1) | uniqueStrict | O(n) |
| keyBy | O(n) | unless | - |
| keys | O(n) | unwrap | O(1) |
| last | O(n) | values | O(n) |
| macro | - | when | - |
| make | - | where | O(n) |
| map | O(n) | whereStrict | O(n) |
| mapInto | O(n) | whereIn | O(n) |
| mapSpread | O(n) | whereInStrict | O(n) |
| mapToGroups | O(n) | whereInstanceOf | O(n) |
| mapWithKeys | O(n) | whereNotIn | O(n) |
| max | O(n) | whereNotInStrict | O(n) |
| median | O(n) | wrap | O(1) |
| merge | O(n) | zip | O(n) |
| min | O(n) | ||
| mode | O(n) |
参考文献
#phpstudy で『数学ガール／乱択アルゴリズム』が紹介された模様です（O記法と計算量の話📈）。ありがとうございます😊 https://t.co/s6QDx0Tx1T
— 結城浩 (@hyuki) September 26, 2018
御本人に反応して頂けてすごく嬉しかったです。プログラミングでご飯を食べていくなら、本当にオススメですので是非！
その他補足
色々なご意見頂けたのですが、計算量を気にされている方は Laravel Collectionの中でも基本的なループ処理しか使っていないということでした。
実際に自分も仕事においては、今回注意喚起したような計算量が多いメソッド（diff, collapse,flatMap等）は未使用でした。
ただし、実例でも示したようにO(n)オーダーでもループ内で組み合わせて使うことで、計算量爆発を起こすコードを簡単に記述することができます。1000件程度のCollectionでも充分な速度劣化を起こすことが出来ます。
計算量の多いメソッドに注意しつつ、今後もデータ量の増加を見込んだ上で効率の良いプログラミングを目指したいところです。
