[PHP] MapとSet ～ Data Structures

# 概要

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

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

:::note warn
この記事のコードはPHP**8.1**で試したものです。
:::

# Data Structuresモジュールとは

https://www.php.net/manual/ja/book.ds.php

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

ベンチマーク等はこちらの[ブログ](https://medium.com/p/9dda7af674cd)で詳しく説明されています。（マニュアルからもリンクされてるブログです）
[^1]:Efficient data structures for PHP 7 https://medium.com/p/9dda7af674cd

# インストール

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

https://www.php.net/manual/ja/ds.installation.php

<details><summary>Dockerfileサンプル</summary>

```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
```

</details>

# Mapクラス

https://www.php.net/manual/ja/class.ds-map.php

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

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

> Keys and values can be any type, including objects.

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

```php
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）

ブログ[^1]の情報は古いのでPHP8.1で計測[^2]してみました。
[^2]:Benchmarks https://github.com/php-ds/benchmarks

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

<details><summary>レポート</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/3f199c3f-25fe-c807-f958-4050e461315e.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/1b5a396d-c56e-2e7a-dad7-b362d77c7799.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/dfa91b3e-5a77-1fa1-dada-0af4762c72a5.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/d6399a0d-fc38-69fe-eaab-8e9ea5823a27.png)

</details>

# Setクラス

https://www.php.net/manual/ja/class.ds-set.php

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

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

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

## ベンチマーク（PHP8.1）

こちらもPHP8.1で計測[^2]してみました。

`add`メソッドは[SplObjectStorage](https://www.php.net/manual/ja/class.splobjectstorage.php)よりも優れています。
`array_unique`メソッドとの比較ですが所要時間はランダムデータを扱うためか不規則な結果となりました。メモリ使用率はSetのほうが優れているのが見てとれます。

<details><summary>レポート</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/1700d7da-f9ae-8d91-34f8-72edcea73ec3.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/4a33e9ac-207f-740c-1ceb-ad632c041e59.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/a907bb76-696e-fa40-f2e5-20963e446c85.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595926/cc4d30f6-e061-fcc7-14cf-600f11dc7549.png)

</details>

# Hashableインターフェース

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

```php
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インターフェースを使います。

https://www.php.net/manual/ja/class.ds-hashable.php

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

```php
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も意図した動きになります。

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