PHPのarrayはすごいです！いろいろできます！奥深い！

PHPのarrayはすごいです。いろいろできます。以前PHPのlist()はタプル展開のための機能 - Qiitaといふ記事を書いて「配列はタプルだったんだよ！！！！」と力説したのですが、それ以外のデータ構造としての特徴について挙げていきます。

タイトルはてきとー。 (原題: All your data structure are belong to ARRAY. は All your base are belong to us - Wikipediaが元ねた。)

PHPのarray

この節の内容は再掲です。

PHPの配列は、その名前に反して、実に多様な機能を併せ持ったデータ型です。

PHP の配列は、実際には順番付けられたマップです。マップは型の一種で、 値をキーに関連付けます。 この型は、さまざまな使い道にあわせて最適化されます。 配列としてだけでなく、リスト (ベクター)、 ハッシュテーブル (マップの実装の一つ)、辞書、コレクション、スタック、 キュー等として使用することが可能です。 PHP の配列には他の PHP 配列を値として保持することができるため、 非常に簡単にツリー構造を表現することが可能です。

php.net, PHP: 配列 - Manual, 2016年8月12日閲覧. 引用は@tadsanによる.

以上のように、PHPにおける配列(array)は、数多くのデータ構造の機能を兼ねて持ちます。大クラス主義を標榜するRubyのArrayよりも、さらに大ざっぱです。

本記事では、arrayの特性を活かして、ここに言及された種々のデータ構造として活用するための方法を紹介します。あと、ややこしいので本記事ではこれ以降、「PHPの配列型(array)」のことを全てarrayと表記します。

配列

そもそもの話になりますが、PHPのarrayは、いはゆるC言語の配列とはまったく別物です。

ちょっとぐぐればWeb上にはC言語の資料はたくさんみつかりますが、ここでは京都産業大学の山田修司先生による配列（array）の資料を参考にします。

C言語の配列の初期化は以下のように、型宣言と要素数を記述する必要があります。C言語の配列のように要素数が固定化された配列を特に「固定長配列」と呼びます。

// 要素数10の配列
int a[10];
// 要素数10の配列 (変数宣言と同時に代入するときは要素数を省略できる)
int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

ご存じのようにPHPのarray(配列)は要素数の設定は必要ありませんし、型を固定する必要もありません。

また、C言語の配列でも「配列の配列」(二次元配列または多次元配列)を扱ふことができますが、その場合すべての配列のサイズが揃ってる必要があります。当然、PHPのarrayにそのような制約はありません。

#include <stdio.h>

int main(void) {
    int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    for (int i = 0; i < (sizeof b / sizeof b[0]); i++) {
        printf("%d\n", b[i]);
    }
    return 0;
}

このCのコードをPHPで書くと以下のようになります。

<?php

$b = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

for ($i = 0; $i < count($i); $i++) {
    printf("%d\n", $b[$i]);
}
exit(0);

// for より foreach を使った方がかんたん
foreach ($b as $i) {
    echo $n, "\n";
}

C言語から派生した要素が強いC++とかJavaでは生配列なまはいれつと呼ばれ、必要に迫られなければ触れるべきではないものだと見做されてる感がありますね。私はC++もJavaも書かないので実際どうなのか知りませんが。

あとPHPの標準ライブラリには固定長配列の実装としてSplFixedArrayクラスがありますが、筆者は実用したことはないです。arrayでいいじゃｎ

ちなみにC言語版のコードについてまめちしきを申し上げますと、C言語のsizeofは函数ではなく演算子なので、sizeof(b)ではなくsizeof bと書いて問題ありません。一方でPHPにもsizeof()はあるのですが、これはcount()のエイリアスで、ただの函数です。(つまりPHPでsizeof $bとは書けません)

リスト

プログラミングの分野でも「リスト」の持つ意味は多義的で、まあデータを順番に並べたもの程度の意味です。もちろんPHPのarrayもデータを順番にいっぱい並べられるので、リストです。

「リスト」の名前でよく知られたデータ構造としては連結リストがありますが、PHPのarrayとは特に関係ありません。 (とても簡単に実装できるので、PHPの練習がてら実装してみるのはおもしろいです)

Wikipedia日本語版には以下のようにあります。

リストの実装方法には主に2つある。連結リスト（片方向または双方向）と動的配列である。

(リスト (抽象データ型) - Wikipedia 2016-01-23T15:19:55‎の版より引用)

され、我らがPHPのarrayの実装はといふと、PHP 5時代は「ハッシュテーブル」、PHP 7では「動的配列(可変長配列)とハッシュテーブル」(処理系が自動的に選択する)になります。(詳しくは@hnwさんのPHP7の内部実装から学ぶ性能改善テクニックが参考になります)

ベクター

PHPマニュアルにはしれっとリスト(ベクター)とかセットでしれっと書いてあるんですが、リストとベクトルでは言葉の範囲がだいぶ異なるような… さておき、コンピュータの世界ではリストに負けず劣らずいろんな意味がありますね。

それはさておいて、PHPマニュアルの著者はC++のstd::vectorについて言及したかったのではないでせうか。これはStandard Template Libraryと呼ばれるC++の標準ライブラリに含まれるデータ構造で、可変長配列のことです。

PHPではメモリ確保などは自動でやってくれるので、ユーザーは深く考へず適当に書いてればPHP処理系がいい感じにしてくれます。

私は中学校の算数と理科で挫折した人間なのでおそらくベクトルについては読者のみなさまの方が詳しいと思ふのですが、世の中では「ベクトル」の対義語とは「スカラー」だとのことです。

PHPでスカラー値と呼ばれるのはbool/int/float/stringの四つの型の値です。is_scalar()函数でチェックすることができます。resourceとnullはスカラーではない、特別な型です。ではarrayとobjectは「ベクター」なのかといふと違って、「複合型(compound types)」と申します。

ハッシュテーブル(マップ)

ここでの「マップ」とは連想配列*(associative array)*のことで、array_mapのようなmap函数とは関係ありません。通常の配列が数値のインデックスしか利用できないのに対して、連想配列は数値以外のデータをインデックスにできるようにしたものです。

ハッシュテーブルは連想配列を実現する効率的なデータ構造として知られます。この名前はインデックスから生成したハッシュ値を利用することからこの名前で呼ばれます。

PerlやRubyでは連想配列のことをHashと呼びますが、ハッシュ値やハッシュ函数と混同されかねず、あまり良い名付けではないと思ひます。また、PHPマニュアルのPHP: Hash 関数 - Manualはもちろん連想配列についての函数ではなく、ハッシュ函数です。

PHPのarrayは連想配列がベースであるために、「連番の数字のみインデックスにした配列」と「文字列インデックスを使った連想配列」の区別を付けにくい問題があります。あるarrayを連想配列ではない配列に変換するにはarray_values()を利用することができます。

また、マップの実現方法は別にハッシュテーブルだけではありません。Lispでは単方向リストを応用した「連想リスト(Association list)」がしばしば用ゐられます。これはデータ構造がとにかく簡単で、PHPでも非常に簡単に実装できます。

辞書(ディクショナリ)

連想配列と同じような意味なので個別に説明するようなことはあまりありません。Pythonの連想配列はdict(辞書)と呼ばれます。

あと、竹内郁雄先生の「初めての人のためのLISP[増補改訂版]」って本では環境(変数のリストのようなもの)を「辞書」と表現されてましたね。

PHPのarrayの問題点としては、intとstringの値しかインデックスに利用できない問題があります。もしどうしてもオブジェクトや配列をインデックスにした辞書を実現したくなった場合、上で紹介した連想リストを自作してみるのもひとつ有効な手段かもしれませんね。

コレクション

これも「データを集めたもの」程度の意味です。ただ、リストと違って「順番に並べた」みたいなニュアンスは含まれません。コレクション概要 - アルゴリズムとデータ構造 | ++C++; // 未確認飛行 Cなどを眺めると、はあ世のなかにはいろんなコレクションがあるんだなあ、といふ気持ちになりますね。

その中でも目を引くのはセットですかね。これは、集合を表現するデータ構造の総称です。

集合

集合とは何かと考へはじめると僕のような数学音痴は秒速で頭がばくはつしかねないのですが、ぱそこんの世界では「重複のないデータの集まり」のような機能が一般的です。

arrayを使って擬似的に集合を表現する方法としては、「arrayのインデックスを利用する方法」と「array_unique()で重複を排除する方法」などがあります。ただし、これらの手法は文字列として表現可能な値にしか適用できないことも気をつけてください。

また、PHPの標準函数には配列を使って集合っぽい操作をするための機能がいくつもあります。

• 差集合
  • array_diff() / array_udiff()
  • array_diff_assoc() / array_diff_uassoc()
  • array_diff_key() / array_diff_ukey()
  • array_udiff_assoc() / array_udiff_uassoc()
• 共通集合 (積集合)
  • array_intersect() / array_uintersect()
  • array_intersect_assoc() / array_intersect_uassoc()
  • array_intersect_key() / array_intersect_ukey()
  • array_uintersect_assoc() / array_uintersect_uassoc()

果たしてこんなに標準函数は必要なのかと疑問をおぼえるほど大量にありますね… あと和集合(union)についての標準函数がないのはarray_unique(array_merge($a, $b))とかやっていい感じにしろってことなんですかね。

スタック

スタックもデータを順番に並べるデータ構造ですが、特徴はデータを後入れ先出し(LIFO: Last In First Out)することです。

スタックに対する基本的な操作はpushとpopです。これに対応する標準函数、配列の末尾にデータを追加するarray_push()と配列の末尾からデータを取り出すarray_pop()です。ただし、array_push($array, $d)は$array[] = $dと書くことができるので、ふつうあまり利用されません。

また、SPL(標準PHPライブラリ)にはシンプルなスタックの実装としてSplStackクラスがあります。

キュー

キューもスタックと同じように、データを順番に並べるデータ構造です。キューは日本語で「待ち行列」とも呼ばれ、お行儀よく順番に処理するのが特徴です。ただしPHPでは先頭と末尾のどちらにデータを追加することも、取り出すことも支障がないため、両端キューに相当します。

シンプルなキューにデータを詰める操作をenqueue、取り出す操作をdequeueといって、これはそれぞれarray_shift()とarray_push()が相当します。また、array_unshift()は配列の先頭にデータをつっこみます。

また、SPL(標準PHPライブラリ)にはシンプルなキューの実装としてSplQueueクラスと、優先度付きキューの実装としてSplPriorityQueue クラスがあります

ツリー(木構造)

木 (数学)と木構造 (データ構造)を読んでください… 身近にあるいろんなもののデータの構造は木構造です。たとへばディレクトリの階層構造とか、HTMLのタグの階層構造だとかが言及しやすい例です。

あとはプログラミング言語で書かれたソースコードは基本的に処理の過程でなんらかの形で木構造に落とし込まれることがあります。PHP 7ではコンパイル時にASTを構築するようになったことが話題になりましたね¹。

タプル

PHPのlist()はタプル展開のための機能 - Qiitaに書きました。

まとめ

みなさまもarrayのポテンシャルを発揮して楽しいPHPライフを！

脚注

1. ここに長いポエムがあったけど、削った ↩