標準PHPライブラリ（SPL）-パート1：データ構造

こんにちは、Habr！ この記事は、標準PHPライブラリ（SPL）についてです。 このライブラリに関するライブラリには、バージョン5.3以降のPHPコアの一部になった賢明なマニュアルはまだありません。 このライブラリには、一連のインターフェイス、データ構造のクラス、イテレータ、および関数が含まれており、これらを使用して人生を大幅に簡素化し、コードの品質を向上させることができます。 この記事では、ライブラリのそのような部分をデータ構造と考えています。 また、タスクの代替ソリューションを示し、両方のケースで実行速度を比較します。





だから。 まず第一に、公式ドキュメントへのリンクを提供したい： php.net/manual/en/book.spl.php

SPLライブラリには、次のデータ構造が含まれています。

• SplDoublyLinkedList-二重リンクリスト
• SplStack-スタック
• SplQueue-キュー
• SplHeap-ヒープ
• SplMaxHeap-ヒープの降順ソート
• SplMinHeap-ヒープの昇順ソート
• SplPriorityQueue-優先度キュー
• SplFixedArray-長さが制限された配列
• SplObjectStorage-オブジェクトストレージ

各構造を順番に検討してください。

SplDoublyLinkedList

二重リンクリスト（DLL）は、相互に双方向で接続されているノードのリストです。 ご存じのように、リストから値を抽出する2つの原則があります。FIFO（先入れ先出し-最初に入力された、最初の左）とLIFO（後入れ先出し-最後に入力された、最初の左）です。 SplDoublyLinkedListを使用すると、これらの原則のいずれかによって値を取得できます。 したがって、スタックまたはキューを簡単に整理するために使用できます。

Splstack

このクラスはSplDoublyLinkedListの子孫であり、たとえば次のようにスタックを実装します。

$stack = new SplStack(); //     $stack->push('1'); $stack->push('2'); $stack->push('3'); echo $stack->count(); // 3 echo $stack->top(); // 3 echo $stack->bottom(); // 1 echo $stack->serialize(); // i:6;:s:1:"1";:s:1:"2";:s:1:"3"; //     echo $stack->pop(); // 3 echo $stack->pop(); // 2 echo $stack->pop(); // 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以前は、手続き型のメソッドを使用して作成しました。つまり、array_push関数を使用し、配列の最後に要素を追加し、array_popを使用して最後の要素を抽出しました。 現在、オブジェクトを操作しています。



2つの方法のパフォーマンスを比較します。 テスト条件：PHP 5.3.18、Core 2 Duo P7350、Windows。 スタックに1からnまでの数字を追加し、スタックからすべてを抽出します。

プッシュとポップの数	関数を使用する	SplStackを使用する	態度
1000	0.007686	0.008559	0.898002
100,000	0.793184	0.884979	0.896274375

このテストでは、関数を使用したメソッドは約10〜15％速く動作しました。



楽しみのために、PHP 5.4.8で別のテストを実行しました

プッシュとポップの数	関数を使用する	SplStackを使用する	態度
1000	0.008186	0.008735	0.937149399
100,000	0.732347	0.771456	0.949304951

このテストから、スタックを操作する場合、PHP 5.4.8はPHP 5.3.18よりも約10％高速であり、オブジェクトの操作も改善されていることがわかります。 したがって、このバージョンのPHPで以降のすべてのテストを実施します。



ただし、より複雑なオブジェクトがスタックに追加された場合、結果の違いはすでにエラーのレベルにあります。



このテストでは、スタックから次のオブジェクトを追加および取得しました。

 $obj = array("10", "20", "qwerty", "100", array("one", "two", array("100") ) );
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プッシュとポップの数	関数を使用する	SplStackを使用する	態度
1000	0.007974	0.008301	0.960607156
100,000	0.818596	0.826363	0,990600983

実際のアプリケーションでは、オブジェクトははるかに複雑になるため、SPLのメソッドの側面に大きな利点があると思い込んでいます。

スプリュウエ

この構造は、キューを作成するために使用されます。 すべてがスタックに似ています;ほんの小さな例を考えてみましょう：

 $queue = new SplQueue(); $queue->setIteratorMode(SplQueue::IT_MODE_DELETE); $queue->enqueue('one'); $queue->enqueue('two'); $queue->enqueue('qwerty'); $queue->dequeue(); $queue->dequeue(); echo $queue->top(); // qwerty
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スプヒープ

ヒープはツリー状の構造です。各ノードはその子孫以上であり、比較のために、実装された比較方法が使用されます。これはヒープ全体に共通です。 SplHeapは、ヒープのコア機能を実装し、抽象クラスです。

SplMaxHeapおよびSplMinHeap

SplHeapから2つのクラスが継承されます。SplMaxHeap-値の降順で配列をソートするため、SplMinHeap-昇順で配列をソートするため。

  $heap = new SplMaxHeap(); $heap->insert('111'); $heap->insert('666'); $heap->insert('777'); echo $heap->extract(); // 777 echo $heap->extract(); // 666 echo $heap->extract(); // 111 $heap = new SplMinHeap(); $heap->insert('111'); $heap->insert('666'); $heap->insert('777'); echo $heap->extract(); // 111 echo $heap->extract(); // 666 echo $heap->extract(); // 777
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SplPriorityQueue

この構造は優先キューです。 各要素に対して、その優先度を設定できます。 優先度に従ってソートが行われます。

  $queue = new SplPriorityQueue(); $queue->setExtractFlags(SplPriorityQueue::EXTR_DATA); //     $queue->insert('Q', 1); $queue->insert('W', 2); $queue->insert('E', 3); $queue->insert('R', 4); $queue->insert('T', 5); $queue->insert('Y', 6); $queue->top(); while($queue->valid()) { echo $queue->current(); $queue->next(); } //YTREWQ
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SplFixedArray

構造は、固定数の要素を持つ配列です。 SplFixedArrayは、インデックスを介してアクセス可能な連続した形式でデータを保存し、通常の配列は順序付けられたハッシュテーブルとして実装されます。 このタイプの配列は通常の配列よりも高速に動作しますが、いくつかの制限があります。

• 整数> 0のみがキーとして使用できます
• 長さは変更できますが、これはコストのかかる操作です

この構造は、番号付きリストに適しています。 例を見て、テストを実行しましょう：

  $a = new SplFixedArray(10000); $count = 100000; for($i =0; $i<$count; $i++) { $a[$i] = $i; if ($i==9999) $a->setSize(100000); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プッシュとポップの数	正規配列	SplFixedArrayを使用する	態度
100	8.2 x 10E-5	6.3 x 10E-5	1,301587301
10,000	0.004953	0.003983	1.243535024
100,000	0.053586	0.0385701	1,389314521
1,000,000	0.533003	0.384391	1.386616752

テストにより、事前に決められた数の配列要素でSplFixedArrayがリードすることが確認されました。 ただし、プロセス中に配列のサイズが変更されると、利点はそれほど重要ではなくなります（最初はサイズが10,000に設定され、その後100,000に拡張されました）。

プッシュとポップの数	正規配列	SplFixedArrayを使用する	態度
1,000,000	0.051937	0.049462	1,050038413

SplObjectStorage

この構造はオブジェクトのリポジトリです。 オブジェクトをリポジトリにアタッチ、削除、現在のオブジェクトを受け取ることができます。 公式マニュアルのいくつかの例を見てみましょう。

 $s = new SplObjectStorage(); //   $o1 = new StdClass; $o2 = new StdClass; $o3 = new StdClass; $s->attach($o1); //     $s->attach($o2); var_dump($s->contains($o1)); // bool(true) var_dump($s->contains($o2)); // bool(true) var_dump($s->contains($o3)); // bool(false) $s->detach($o2); //     var_dump($s->contains($o1)); // bool(true) var_dump($s->contains($o2)); // bool(false) var_dump($s->contains($o3)); // bool(false)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

別の例：

 $s = new SplObjectStorage(); $o1 = (object)array('a'=>1); $o2 = (object)array('b'=>2); $o3 = (object)array('c'=>3); $s[$o1] = "data for object 1"; $s[$o2] = array(1,2,3); foreach($s as $i => $key) { echo "Entry $i:\n"; // You get a numeric index var_dump($key, $s[$key]); echo "\n"; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果：

 Entry 0: object(stdClass)#2 (1) { ["a"]=> int(1) } string(17) "data for object 1" Entry 1: object(stdClass)#3 (1) { ["b"]=> int(2) } array(3) { [0]=> int(1) [1]=> int(2) [2]=> int(3) }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、SPLデータ構造を調査しました。 スタック、キュー、リストをすばやく作成する方法を学びました。 SplFixedArrayは、通常の配列よりも高速です。 ただし、これはこのライブラリの使用のごく一部です。 以下の記事では、イテレーター、インターフェース、関数、および例外処理について説明します。