PHP - Spl数据结构

今天在看hyperf源码的时候，看到一个SplPriorityQueue的使用，想起很久以前要学习一下spl库的一些知识，一直没去看，今天就先学习一下spl提供的数据结构

• https://www.php.net/manual/zh/spl.datastructures.php

实践

双向链表

• 当底层结构是 DLL 时, 迭代器的操作、对两端的访问、节点的添加或删除都具有 O (1) 的开销

SplDoublyLinkedList

<?php

$list = new SplDoublyLinkedList();

// 判断链表是否空
var_dump($list->isEmpty()); // bool(true)

// 添加新的节点到链表顶部 (top)
$list->push('2');
$list->push('3');
$list->push('4');
var_dump($list); // bottom ['2', '3', '4'] top

// 在指定索引处添加新值，如果index不存在，异常
$list->add(0, '1');
var_dump($list); // bottom ['1', '2', '3', '4'] top

// 添加新的节点到链表底部（bottom）
$list->unshift('0');
var_dump($list); // bottom ['0', '1', '2', '3', '4'] top

// 获取节点数量
$count = $list->count();
var_dump($count); // int(5)

// 获取顶部的节点
$top = $list->top();
var_dump($top); // string(1) "4"

// 获取底部的节点
$bottom = $list->bottom();
var_dump($bottom); // string(1) "0"

// 将指针重置，指向bottom节点
$list->rewind();

// 获取当前节点指针的index和value
$key = $list->key();
$value = $list->current();
var_dump("key:{$key} value:{$value}"); // string(13) "key:0 value:0"

// 移动指针到下一个
$list->next();
var_dump("key:{$list->key()} value:{$list->current()}"); // string(13) "key:1 value:1"

// 移动指针到上一个
$list->prev();
var_dump("key:{$list->key()} value:{$list->current()}"); // string(13) "key:0 value:0"

// 从top取出一个数据
$pop = $list->pop();
var_dump($pop); // string(1) "4"
var_dump($list); // bottom ['0', '1', '2', '3'] top

// 从bottom取出一个数据
$shift = $list->shift();
var_dump($shift); // string(1) "0"
var_dump($list); // bottom ['1', '2', '3'] top

// 序列化
$serialize = $list->serialize();
var_dump($serialize); // string(31) "i:0;:s:1:"1";:s:1:"2";:s:1:"3";"

// offset
var_dump($list->offsetExists(0)); // bool(true)
var_dump($list->offsetGet(0));
$list->offsetSet(2, '4');
var_dump($list); // bottom ['1', '2', '4'] top
$list->offsetUnset(2);
var_dump($list); // bottom ['1', '2'] top

// 验证当前节点是否有效
$list->rewind();
var_dump("key:{$list->key()} value:{$list->current()} valid:{$list->valid()}"); // string(21) "key:0 value:1 valid:1"
$list->next();
var_dump("key:{$list->key()} value:{$list->current()} valid:{$list->valid()}"); // string(21) "key:1 value:2 valid:1"
$list->next();
var_dump("key:{$list->key()} value:{$list->current()} valid:{$list->valid()}"); // string(19) "key:2 value: valid:"

/**
 * 迭代模式
 * - SplDoublyLinkedList::IT_MODE_LIFO 2 (栈 后进先出)
 * - SplDoublyLinkedList::IT_MODE_FIFO 0 (队列 先进先出 默认)
 * 迭代行为
 * - SplDoublyLinkedList::IT_MODE_DELETE (删除已迭代的节点元素)
 * - SplDoublyLinkedList::IT_MODE_KEEP (保留已迭代的节点元素 默认)
 */
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
$mode = $list->getIteratorMode();
var_dump($mode); // 0

function testMode(int $mode)
{
    $list = new SplDoublyLinkedList();
    $list->setIteratorMode($mode);
    $list->push('a');
    $list->push('b');
    $list->push('c');
    for ($list->rewind();$list->valid();$list->next()) {
        var_dump("key:{$list->key()} value:{$list->current()}");
    }
    var_dump($list);
    echo PHP_EOL;
};

// 先进先出，删除已迭代节点
testMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_DELETE);
/**
 * key:0 value:a
 * key:0 value:b
 * key:0 value:c
 *
 * list: bottom [] top
 */

// 先进先出，保留已迭代节点
testMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP);
/**
 * key:0 value:a
 * key:1 value:b
 * key:2 value:c
 *
 * list: bottom ['a', 'b', 'c'] top
 */

// 后进先出，删除已迭代节点
testMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);
/**
 * key:2 value:c
 * key:1 value:b
 * key:0 value:a
 *
 * list: bottom [] top
 */

// 后进先出，保留已迭代节点
testMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP);
/**
 * key:2 value:c
 * key:1 value:b
 * key:0 value:a
 *
 * list: bottom ['a', 'b', 'c'] top
 */


// 时间复杂度 O (1) 验证
$list = new SplDoublyLinkedList();
for ( $i = 0 ; $i < 2000001 ; $i++ ) {
    $list->push($i);
}

$start = microtime(true);
$list->offsetGet(0);
$end = microtime(true);
var_dump(($end - $start) *  1000); // float(0.0030994415283203125)

$start = microtime(true);
$list->offsetGet(2000000);
$end = microtime(true);
var_dump(($end - $start) *  1000); // float(3.4248828887939453)

SplStack

• 基于SplDoublyLinkedList提供栈的主要功能
• IT_MODE_LIFO | IT_MODE_KEEP 默认模式

<?php

$list = new SplStack();

$mode = $list->getIteratorMode();
var_dump("mode: {$mode}");

$list->push('a');
$list->push('b');
$list->push('c');

$list->rewind();
while($list->valid()){
    var_dump("key:{$list->key()} value:{$list->current()}");
    $list->next();
}
var_dump($list);
/**
 * mode: 6
 *
 * string(13) "key:2 value:c"
 * string(13) "key:1 value:b"
 * string(13) "key:0 value:a"
 *
 * list: bottom ['a', 'b', 'c'] top
 */

SplQueue

• 基于SplDoublyLinkedList提供队列的主要功能
• IT_MODE_FIFO | IT_MODE_KEEP 默认模式
• pop和push看上去像栈的用法，所以额外提供了dequeue和enqueue，功能一样

<?php

$list = new SplQueue();

$mode = $list->getIteratorMode();
var_dump("mode: {$mode}");

$list->enqueue('a');
$list->enqueue('b');
$list->enqueue('c');

$list->rewind();
while($list->valid()){
    var_dump("key:{$list->key()} value:{$list->current()}");
    $list->next();
}
var_dump($list);
/**
 * mode: 4
 *
 * string(13) "key:0 value:a"
 * string(13) "key:1 value:b"
 * string(13) "key:2 value:c"
 *
 * list: bottom ['a', 'b', 'c'] top
 */

堆

• 堆是遵循堆属性的树状结构: 每个节点都大于或等于其子级，使用对堆全局的已实现的比较方法进行比较
• 堆(Heap)就是为了实现优先队列而设计的一种数据结构，它是通过构造二叉堆(二叉树的一种)实现。根节点最大的堆叫做最大堆或大根堆（SplMaxHeap），根节点最小的堆叫做最小堆或小根堆（SplMinHeap）。二叉堆还常用于排序(堆排序)
  extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据

<?php

class MySplHeap extends SplHeap
{
    /**
     * 比较$value1是否大于$value2，如果大于为 正整数，等于为 0，小于为 负整数
     * 通过比较结果来决定在堆中的位置
     */
    protected function compare($value1, $value2): int
    {
//        return ($value1 - $value2); // 最大堆
        return ($value2 - $value1); // 最小堆
    }
}

$heap = new MySplHeap();

$heap->insert(10);
$heap->insert(14);
$heap->insert(25);
$heap->insert(33);
$heap->insert(81);
$heap->insert(82);
$heap->insert(99);

//var_dump($heap); // [10， 14， 25， 33， 81， 82， 99]
/**
 *     10
    14    25
  33 81  82 99
 */

// 获取节点数量
$count = $heap->count();
var_dump($count); // int(7)

// current 始终等于 top，所以rewind没什么用

// 获取顶部节点
$top = $heap->top();
var_dump($top); // int(10)

// 获取当前节点
$current = $heap->current();
var_dump($current); // int(10)

// 下一个节点，这里会删除掉当前节点后，指向top， 重置堆
$heap->next();
var_dump($heap->count()); // int(6)
var_dump($heap->current()); // int(14)

// 把最末端的一个节点置顶后，重新下序
//var_dump($heap); // [14， 33， 25， 99， 81， 82]

// 等同于 current + next，弹出top节点
$extract = $heap->extract();
var_dump($extract); // int(14)

// var_dump($heap); // [25, 33, 82, 99, 81]

while ($heap->valid()) {
    var_dump($heap->extract());
}
/**
 * int(25)
 * int(33)
 * int(81)
 * int(82)
 * int(99)
 */

// 获取数量
$count = $heap->count();
var_dump($count); // int(0)

SplMaxHeap

最大堆

<?php

$maxHeap = new SplMaxHeap();

$maxHeap->insert(4);
$maxHeap->insert(8);
$maxHeap->insert(1);
$maxHeap->insert(0);

foreach ($maxHeap as $item) {
    var_dump($item);
}
// 8,4,1,0

SplMinHeap

最小堆

$maxHeap = new SplMinHeap();

$maxHeap->insert(4);
$maxHeap->insert(8);
$maxHeap->insert(1);
$maxHeap->insert(0);

foreach ($maxHeap as $item) {
    var_dump($item);
}
// 0,1,4,8

SplPriorityQueue

优先队列，通过加权对值进行排序

• SplPriorityQueue是以Heap：堆数据结构实现的，默认为MaxHeap模式，即priority越大越优先出队，同时可以通过重写compare方法来使用MinHeap
• 当我们出队时会拿出堆顶的元素，此时堆的特性被破坏，堆会进行相应的调整至稳定态(MaxHeaporMinHeap)，即会将最后一个元素替换到堆顶，然后进行稳定态验证，不符合堆特性则继续调整，或者我们就得到了一个稳定态的堆，所以当优先级相同，出队顺序并不会按照入队顺序
• SplPriorityQueue的入队方法和出队方法：insert和extract
• extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据

<?php

$objPQ = new SplPriorityQueue();

$objPQ->insert('A',3);
$objPQ->insert('B',6);
$objPQ->insert('C',1);
$objPQ->insert('D',2);

/**
 * 设置元素出队模式
 * SplPriorityQueue::EXTR_DATA 仅提取值
 * SplPriorityQueue::EXTR_PRIORITY 仅提取优先级
 * SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级
 */
$objPQ->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

$top = $objPQ->top();
var_dump($top);
//array(2) {
//    ["data"]=>
//  string(1) "B"
//    ["priority"]=>
//  int(6)
//}

while ($objPQ->valid()) {
    $current = $objPQ->extract();
    echo "data: {$current['data']} priority: {$current['priority']}" . PHP_EOL;
}

//data: B priority: 6
//data: A priority: 3
//data: D priority: 2
//data: C priority: 1

数组

splFixedArray数组相比标准的PHP数组更接近于C语言的数组，而且由于splFixedArray没有使用散列(Hash)存储方式，因此效率更高
SplFixedArray与普通的PHP Array不同，它是以数字为键名的固定长度的数组，它没有使用散列(Hash)存储方式，更接近于C语言的数组，因此效率更高。

<?php

// 定义长度后，初始化的值为null。必须先建立固定长度的数组
$arr = new SplFixedArray(4);

$arr[0] = 'php';
$arr[1] = 1;
$arr[3] = 'go';
var_dump($arr); // arr[2] 为 null

foreach ($arr as $value) {
    var_dump($value);//string(3) "php",int(1),NULL,string(2) "go"
}

// 获取长度
var_dump($arr->getSize()); // int(4)

// 重新设置数组长度，如果是小于目前的，会直接舍弃掉数据，大于目前的，就初始化null的数据
$arr->setSize(6);
var_dump($arr);

// 导入一个PHP普通数组来生成SplFixedArray实例
$arr2 = ['1', '2', '5'];
$arr2 = SplFixedArray::fromArray($arr2);
var_dump($arr2);
//object(SplFixedArray)#4 (3) {
//[0]=>
//  string(1) "1"
//[1]=>
//  string(1) "2"
//[2]=>
//  string(1) "5"
//}

映射

SplObjectStorage

splObjectStorage类提供从对象到数据或忽略数据的对象集的映射。这种双重目的在许多情况下都是有用的，包括需要唯一地标识对象。
用来存储一组对象的，特别是当你需要唯一标识对象的时候
对象存储器

<?php

class Person
{
    public string $name;

    public function __construct(string $name)
    {
        $this->name = $name;
    }
}

$zhangsan = new Person('张三');
$lisi = new Person('李四');
$wangwu = new Person('王五');
$zhaoliu = new Person('赵六');

$container = new SplObjectStorage();

$container->attach($zhangsan);
$container->attach($lisi);
$container->attach($wangwu);

var_dump($container->count()); // int(3)

// 检查是否在对象存储空间里
var_dump($container->contains($zhangsan)); // bool(true)
var_dump($container->contains($zhaoliu)); // bool(false)

// 删除指定对象
$container->detach($lisi);

// 添加一个 末尾
$container->attach($zhaoliu);

// 添加重复值
$zhaoliu1 = new Person('赵六');
$container->attach($zhaoliu1);
$container->attach($zhaoliu); // 只有这个算重复对象，会被替代
$container->attach(new Person('赵六'));

$container->rewind();
while ($container->valid()) {
    /** @var Person $person */
    $person = $container->current();
    echo $container->getHash($person) . ":{$person->name}".PHP_EOL;
    $container->next();
}
// 张三，王五，赵六，赵六，赵六

var_dump($container->count()); // int(5)

应用场景示例

// TODO 待补充