[PHP] MapとSet ～ Data Structures

概要

PHPのData Structuresモジュールに含まれるMapとSetを試してみたので紹介します。

• Data Structuresモジュール
• Mapクラス、SetクラスおよびHashableインターフェース
• ベンチマーク

この記事のコードはPHP8.1で試したものです。

Data Structuresモジュールとは

PHP7から提供されている、配列の代わりに使える効率的なデータ構造です。
この記事でとりあげるMapとSet以外にもVectorやStack、Queueなどが提供されています。
要インストール。

ベンチマーク等はこちらのブログで詳しく説明されています。（マニュアルからもリンクされてるブログです）

インストール

バンドルされていないのでインストールが必要になりますが、PECLで簡単にインストールできます。

Dockerfileサンプル

FROM php:8.1-fpm-alpine

RUN apk update \
    && apk add --update-cache --no-cache \
        autoconf \
        gcc \
        g++ \
        make

RUN pecl install ds \
    && docker-php-ext-enable ds

Mapクラス

Mapはキーと値のペアの連続したコレクションです。JavaScriptや他の言語にも同じものがありますね。
PHPには連想配列があるので積極的に使う機会は少ないのかもしれません。

では何が異なるのかというと、キーに任意のオブジェクトを使うことができる点です。（配列は文字列か数値）

Keys and values can be any type, including objects.

このようにEnumやオブジェクトをキーにすることができます。

enum Suit
{
    case Hearts;
    case Diamonds;
    case Clubs;
    case Spades;
}

class Money
{
    public function __construct(private int $amount)
    {
    }
}

$map = new Ds\Map();
$map->put(Suit::Hearts, 'ハートだよ');
$map->put(new Money(5), '5円だよ');

ベンチマーク（PHP8.1）

ブログ¹の情報は古いのでPHP8.1で計測²してみました。

putについては配列よりわずかに優れる、という感じでしょうか。
removeも処理時間は配列よりわずかに優れる程度ですが、メモリ使用率が大きく異なります。これは「サイズが十分に小さくなると、割り当てられたメモリーを自動的に解放する」という特徴に由来するものです。

レポート

Setクラス

Setは一意な値のコレクションです。こちらも配列をarray_uniqueすれば実現できるので、それで十分なケースが多かもしれません。

しかし、値が増えるほどarray_uniqueよりもSetの方がパフォーマンスは良さそうです。¹

$set = new Set();
$set->add(1);
$set->add(2);
$set->add(3);
$set->add(1); // again
// [1, 2, 3]

ベンチマーク（PHP8.1）

こちらもPHP8.1で計測²してみました。

addメソッドはSplObjectStorageよりも優れています。
array_uniqueメソッドとの比較ですが所要時間はランダムデータを扱うためか不規則な結果となりました。メモリ使用率はSetのほうが優れているのが見てとれます。

レポート

Hashableインターフェース

さて、MapとSetについて紹介しましたがオブジェクトを使うと思うようにいかないことがあります。
次のMoneyクラスは同じ金額であれば同じものとして扱いたいのですが、MapとSetはそのように扱ってくれません。

class Money
{
    public function __construct(private int $amount)
    {
    }
}

// Money(5)はMoney(5)どちらも同じ5円として扱いたい

$map = new Map();
$map->put(new Money(5), '5円');
$map->put(new Money(10), '10円');
$map->put(new Money(100), '100円');
$map->get(new Money(5)); // Key not found 🤔

$set = new Set();
$set->add(new Money(5));
$set->add(new Money(5));
$set->add(new Money(10));
$set->add(new Money(100));
// [Money(5), Money(5), Money(10), Money(100)] 🤔

そんな時にHashableインターフェースを使います。

Hashableはオブジェクトをキーとして使用できるようにするインターフェイスです。
同じオブジェクトであれば同じハッシュ値を返すhashメソッドと、オブジェクトが等しいかどうかを判定するequalsメソッドを実装します。

class Money implements Ds\Hashable
{
    public function __construct(private int $amount)
    {
    }

    public function equals($money): bool
    {
        return $this->amount === $money->amount;
    }

    public function hash()
    {
        return $this->amount;
    }
}

$yen5 = new Money(5);
var_dump($yen5->equals(new Money(5))); // true
var_dump($yen5->equals(new Money(10))); // false

// 残念ながら等価演算子で期待する動作になるわけではない
var_dump($yen5 === new Money(5)); // false

そしてHashableインターフェースを実装したMoneyクラスであれば、MapやSetも意図した動きになります。

$map = new Map();
$map->put(new Money(5), '5円');
$map->put(new Money(10), '10円');
$map->put(new Money(100), '100円');
$map->get(new Money(5)); // '5円' 😀

$set = new Set();
$set->add(new Money(5));
$set->add(new Money(5));
$set->add(new Money(10));
$set->add(new Money(100));
// [Money(5), Money(10), Money(100)] 😀

まとめ

Data Structuresモジュールと、そのモジュールに含まれるMapとSetについて紹介しました。

• 配列よりもパフォーマンスに優れるData Structuresモジュール
• キーと値のコレクションMapクラス
• 一意な値のコレクションSetクラス
• MapとSetでオブジェクトを扱うためのHashableインターフェース

PHPには使い勝手のよい連想配列があるので積極的に使う機会は少ないかもしれませんが、設計やパフォーマンスに課題があるなら選択肢として検討できそうです。

1. Efficient data structures for PHP 7 https://medium.com/p/9dda7af674cd ↩ ↩²

2. Benchmarks https://github.com/php-ds/benchmarks ↩ ↩²