PHP小码农

Appearance

DS 扩展概览 ​

概述 ​

DS（Data Structures）扩展为 PHP 提供了一组高性能的专用数据结构，包括 Vector、Deque、Map、Set、Pair、Stack、Queue 和 PriorityQueue。与原生 PHP 数组相比，DS 数据结构在特定场景下具有显著的性能优势。

基础概念 ​

安装 ​

bash
# PECL 安装
pecl install ds

# 或通过包管理器
apt install php-ds  # Debian/Ubuntu

# php.ini 启用
extension=ds.so

DS 数据结构一览 ​

数据结构对标原生数组特点时间复杂度
Ds\Vector索引数组有序序列，自动索引读取 O(1)
Ds\Deque索引数组双端队列首尾操作 O(1)
Ds\Map关联数组键值映射，按键排序读取 O(1)
Ds\Set去重数组唯一值集合查找 O(1)
Ds\Pair两个元素的数组键值对O(1)
Ds\Stackarray_pop 模式后进先出（LIFO）push/pop O(1)
Ds\Queuearray_shift 模式先进先出（FIFO）push/pop O(1)
Ds\PriorityQueue堆排序数组优先级队列insert O(log n)

与原生数组对比 ​

特性原生数组DS 数据结构
类型安全否是（强类型）
内存效率低（HashTable）高（专用结构）
接口统一无实现 Collection 接口
序列化支持支持
foreach支持支持
JSON支持需 toArray()
键类型int + string仅 int 或仅 string

语法与代码 ​

Vector 基本用法 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;

$vector = new Vector([1, 2, 3]);
$vector->push(4, 5);
$vector->pop();       // 移除 5
echo $vector->get(0); // 1
echo $vector->count(); // 4

// 遍历
foreach ($vector as $value) {
    echo $value . ' ';
}

Map 基本用法 ​

php
<?php

declare(strict_types=1);

use Ds\Map;

$map = new Map();
$map->put('name', 'Alice');
$map->put('age', 30);
echo $map->get('name');  // Alice
echo $map->has('email');  // false

Set 基本用法 ​

php
<?php

declare(strict_types=1);

use Ds\Set;

$set = new Set([1, 2, 3, 2, 1]);  // 自动去重
echo $set->count();  // 3

$set->add(4);
$set->remove(2);
$set->has(3);  // true

Collection 接口 ​

php
<?php

declare(strict_types=1);

// 所有 DS 数据结构都实现了 Collection 接口
// Collection 接口提供的方法：
// count(), clear(), isEmpty(), toArray(), jsonSerialize(),
// getIterator(), copy()

use Ds\Vector;

$vector = new Vector([1, 2, 3]);
echo $vector->count();   // 3
echo $vector->isEmpty();  // false
$copy = $vector->copy();  // 副本
$vector->clear();         // 清空

详细说明 ​

性能优势场景 ​

php
<?php

declare(strict_types=1);

// Vector vs 原生数组 - 顺序读写
// Vector 内部使用连续内存，缓存友好

// Set vs array_unique - 去重
// Set 使用哈希表，插入时自动去重，无需 array_unique

// Map vs 原生关联数组 - 键查找
// Map 专为键值映射优化

// Deque vs array_shift/unshift - 首尾操作
// array_shift 是 O(n)，Deque 首尾操作是 O(1)

何时使用 DS

  • 需要高性能数据操作时
  • 需要类型安全的数据结构时
  • 需要专用的栈/队列/集合时
  • 原生数组性能成为瓶颈时

实战示例 ​

数据处理管道 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;
use Ds\Set;

// Vector 作为数据处理管道
$data = new Vector([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

// 筛选偶数
$evens = $data->filter(fn(int $n): bool => $n % 2 === 0);

// 映射平方
$squared = $evens->map(fn(int $n): int => $n ** 2);

// 归约求和
$sum = $squared->reduce(fn(int $carry, int $n): int => $carry + $n, 0);
echo $sum;  // 220（4+16+36+64+100）

// Set 去重
$duplicates = [1, 2, 3, 2, 1, 4, 5, 3];
$unique = new Set($duplicates);
echo $unique->count();  // 5

注意事项 ​

扩展安装

DS 扩展需要通过 PECL 安装或编译安装，不是 PHP 默认启用的扩展。生产环境部署前确保目标服务器已安装。

JSON 序列化

DS 对象不能直接 json_encode()。需要先调用 toArray() 或 jsonSerialize()。

最佳实践 ​

  1. Vector 替代大索引数组：性能敏感的场景
  2. Set 替代 array_unique：需要频繁去重时
  3. Map 替代关联数组：需要类型安全的键值映射
  4. Deque 替代 array_shift/unshift：首尾频繁操作
  5. Stack/Queue 用于算法：需要明确 LIFO/FIFO 语义
  6. toArray() 用于序列化：JSON 输出或持久化时

接口与抽象类 ​

php
<?php

declare(strict_types=1);

use Ds\Collection;

// Collection 接口方法
// count(): int           - 元素数量
// isEmpty(): bool        - 是否为空
// toArray(): array        - 转为原生数组
// jsonSerialize(): mixed - JSON 序列化
// clear(): void          - 清空集合
// copy(): Collection     - 创建副本
// getIterator(): Traversable - 获取迭代器

use Ds\Sequence;

// Sequence 接口（Vector 和 Deque 实现）
// extends Collection
// get(int $index): mixed
// set(int $index, mixed $value): void
// remove(int $index): mixed
// insert(int $index, mixed ...$values): void
// push(mixed ...$values): void
// pop(): mixed
// shift(): mixed
// unshift(mixed ...$values): void
// sort(callable $comparator): void
// reverse(): void
// map(callable $callback): Sequence
// filter(callable $callback): Sequence
// reduce(callable $callback, mixed $initial): mixed
// first(): mixed
// last(): mixed
// contains(mixed ...$values): bool
// join(string $glue): string
// slice(int $offset, int $length): Sequence

// 使用示例
$vector = new \Ds\Vector([3, 1, 2]);
echo $vector->count();       // 3
echo $vector->isEmpty();     // false
$arr = $vector->toArray();   // [3, 1, 2]
$json = json_encode($vector); // [3,1,2]

JSON 序列化 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;
use Ds\Map;
use Ds\Set;

// 所有 DS 集合都实现 JsonSerializable
$vector = new Vector([1, 2, 3]);
$map = new Map(['key' => 'value']);
$set = new Set([1, 2, 3]);

// 直接 json_encode
echo json_encode($vector);  // [1,2,3]
echo json_encode($map);     // {"key":"value"}
echo json_encode($set);     // [1,2,3]

// 从 JSON 恢复（需要手动转换）
$json = '[1,2,3]';
$data = json_decode($json, true);
$vector = new Vector($data);

与原生数组的互操作 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;
use Ds\Map;
use Ds\Set;

// 原生数组 -> DS
$vector = new Vector([1, 2, 3]);
$map = new Map(['a' => 1, 'b' => 2]);
$set = new Set([1, 2, 3, 2, 1]);

// DS -> 原生数组
$arr = $vector->toArray();
$arr = $map->toArray();
$arr = $set->toArray();

// Vector <-> 原生数组互转
$native = [1, 2, 3, 4, 5];
$ds = new Vector($native);

// 处理后转回
$processed = $ds->filter(fn(int $n): bool => $n > 2)
                ->map(fn(int $n): int => $n * 10)
                ->toArray();
// [30, 40, 50]

// Map <-> 关联数组
$conf = ['debug' => true, 'cache' => false];
$dsMap = new Map($conf);

$dsMap->put('timeout', 30);
$result = $dsMap->toArray();
// ['debug' => true, 'cache' => false, 'timeout' => 30]

// Set <-> 去重数组
$dups = [1, 2, 3, 2, 1, 4, 5, 3];
$dsSet = new Set($dups);
$unique = $dsSet->toArray();
// [1, 2, 3, 4, 5]

DS 扩展的安装验证 ​

php
<?php

// 检查 DS 扩展是否已安装
if (!extension_loaded('ds')) {
    echo "DS 扩展未安装\n";
    echo "请运行: pecl install ds\n";
    exit(1);
}

echo "DS 扩展版本: " . phpversion('ds') . "\n";

// 列出可用的 DS 类
$classes = ['Vector', 'Deque', 'Map', 'Set', 'Pair',
            'Stack', 'Queue', 'PriorityQueue'];

foreach ($classes as $class) {
    $fqn = "Ds\\{$class}";
    echo "{$fqn}: " . (class_exists($fqn) ? '可用' : '不可用') . "\n";
}

DS 扩展的性能基准 ​

php
<?php

declare(strict_types=1);

use Ds\Vector;
use Ds\Set;

// 简单性能对比：Vector vs 原生数组 push
$n = 100000;

// Vector push
$start = microtime(true);
$vector = new Vector();
for ($i = 0; $i < $n; $i++) {
    $vector->push($i);
}
$vectorTime = microtime(true) - $start;

// 原生数组 push
$start = microtime(true);
$arr = [];
for ($i = 0; $i < $n; $i++) {
    $arr[] = $i;
}
$nativeTime = microtime(true) - $start;

echo "Vector push: {$vectorTime}s\n";
echo "Native push: {$nativeTime}s\n";
// 在大多数情况下，两者差距不大，但 Vector 在连续内存操作中更有优势

// Set 去重 vs array_unique
$dups = range(1, $n);
$setStart = microtime(true);
$set = new Set($dups);
$setTime = microtime(true) - $setStart;

$uniqueStart = microtime(true);
$unique = array_unique($dups);
$uniqueTime = microtime(true) - $uniqueStart;

echo "Set 去重: {$setTime}s\n";
echo "array_unique: {$uniqueTime}s\n";
// Set 通常更快，因为它在插入时就去重

选择 DS 的场景

DS 数据结构最适合以下场景：(1) 性能敏感的数据操作 (2) 需要明确语义的数据结构（栈、队列、集合）(3) 函数式风格的链式操作 (4) 类型安全的数据处理。

兼容性

DS 扩展不是 PHP 核心扩展，在生产环境部署前必须确保目标服务器已安装。建议在 composer.json 中添加扩展检查。

参考链接 ​