Analyse von DS-Erweiterungsbeispielen in der PHP-Datenstruktur

Der folgende Editor bringt Ihnen ein Klischee über die Datenstruktur in PHP: DS-Erweiterung. Der Herausgeber findet es ziemlich gut, deshalb teile ich es jetzt mit Ihnen und gebe es als Referenz. Folgen wir dem Editor, um einen Blick darauf zu werfen.

Nur PHP 7 oder höher kann diese Datenstrukturerweiterung installieren und verwenden:

1. Führen Sie den Befehl pecl install ds aus

2. Fügen Sie extension=ds.so in php.ini hinzu

3. Starten Sie PHP neu oder laden Sie die Konfiguration neu

Sammlungsschnittstelle:

Eine grundlegende Schnittstelle, die gemeinsame Funktionen für alle Datenstrukturen in dieser Bibliothek enthält. Es garantiert, dass alle Strukturen durchquerbar und zählbar sind und mit json_encode() in JSON konvertiert werden können.

Ds\Collection implements Traversable , Countable , JsonSerializable {
/* 方法 */
abstract public void clear ( void )
abstract public Ds\Collection copy ( void )
abstract public bool isEmpty ( void )
abstract public array toArray ( void )
}

Hashable-Schnittstelle:

die die Verwendung von Objekten als Schlüssel ermöglicht >

Sequenzschnittstelle:

Ds\Hashable {
/* 方法 */
abstract public bool equals ( object $obj )
abstract public mixed hash ( void )
}

Eine Sequenz entspricht einem eindimensionalen digitalen Schlüsselarray, mit der

Ausnahme einiger Merkmale:Werte wird immer als [0, 1, 2, …, Größe - 1] indiziert.

Nur ​​Zugriff auf Werte per Index im Bereich [0, Größe - 1] erlaubt.

Anwendungsfälle:

Überall dort, wo Sie ein Array als Liste verwenden würden (ohne Rücksicht auf Schlüssel).

Eine effizientere Alternative zu SplDoublyLinkedList und SplFixedArray.

Vektorklasse:

Ein Vektor ist eine Folge von Werten in einem kontinuierlichen Puffer, der automatisch wächst und schrumpft. Es handelt sich um die effizienteste sequentielle Struktur, der Index des Werts wird direkt dem Index im Puffer zugeordnet und der Wachstumsfaktor ist nicht an ein bestimmtes Vielfaches oder Exponenten gebunden. Es hat die folgenden Vor- und Nachteile:

Unterstützt Array-Syntax (eckige Klammern).

Benötigt weniger Gesamtspeicher als ein Array für die gleiche Anzahl von Werten.

Wird automatisch freigegeben zugewiesener Speicher, wenn seine Größe niedrig genug ist.

Kapazität muss keine Potenz von 2 sein.

get(), set(), push(), pop() sind alle O (1 ).

Aber Shift(), Unshift(), Insert() und Remove() sind alle O(n).

Deque-Klasse:

Ds\Vector::allocate — Allocates enough memory for a required capacity.
Ds\Vector::apply — Updates all values by applying a callback function to each value.
Ds\Vector::capacity — Returns the current capacity.
Ds\Vector::clear — Removes all values.
Ds\Vector::construct — Creates a new instance.
Ds\Vector::contains — Determines if the vector contains given values.
Ds\Vector::copy — Returns a shallow copy of the vector.
Ds\Vector::count — Returns the number of values in the collection.
Ds\Vector::filter — Creates a new vector using a callable to determine which values to include.
Ds\Vector::find — Attempts to find a value's index.
Ds\Vector::first — Returns the first value in the vector.
Ds\Vector::get — Returns the value at a given index.
Ds\Vector::insert — Inserts values at a given index.
Ds\Vector::isEmpty — Returns whether the vector is empty
Ds\Vector::join — Joins all values together as a string.
Ds\Vector::jsonSerialize — Returns a representation that can be converted to JSON.
Ds\Vector::last — Returns the last value.
Ds\Vector::map — Returns the result of applying a callback to each value.
Ds\Vector::merge — Returns the result of adding all given values to the vector.
Ds\Vector::pop — Removes and returns the last value.
Ds\Vector::push — Adds values to the end of the vector.
Ds\Vector::reduce — Reduces the vector to a single value using a callback function.
Ds\Vector::remove — Removes and returns a value by index.
Ds\Vector::reverse — Reverses the vector in-place.
Ds\Vector::reversed — Returns a reversed copy.
Ds\Vector::rotate — Rotates the vector by a given number of rotations.
Ds\Vector::set — Updates a value at a given index.
Ds\Vector::shift — Removes and returns the first value.
Ds\Vector::slice — Returns a sub-vector of a given range.
Ds\Vector::sort — Sorts the vector in-place.
Ds\Vector::sorted — Returns a sorted copy.
Ds\Vector::sum — Returns the sum of all values in the vector.
Ds\Vector::toArray — Converts the vector to an array.
Ds\Vector::unshift — Adds values to the front of the vector.

Die Abkürzung für „Double-Ended Queue“, die auch in DsQueue verwendet wird, hat zwei Zeiger, Kopf und Schwanz. Die Zeiger können das Ende des Puffers „umschließen“, wodurch die Notwendigkeit vermieden wird, andere Werte zu verschieben, um Platz zu schaffen – etwas, mit dem ein DsVector nicht mithalten kann. Es hat die folgenden Vorteile und Nachteile:

Unterstützt Array-Syntax (eckige Klammern).

Benötigt weniger Gesamtspeicher als ein Array für die gleiche Anzahl von Werten.

Gibt zugewiesenen Speicher automatisch frei, wenn seine Größe erreicht ist fällt tief genug ab.

get(), set(), push(), pop(), shift() und unshift() sind alle O(1).

Aber die Kapazität muss sei eine Potenz von 2.insert() und remove() sind O(n).

Map-Klasse:

Eine kontinuierliche Sammlung von Schlüssel-Wert-Paaren, fast dasselbe wie ein Array. Schlüssel können von beliebiger Art sein, müssen jedoch eindeutig sein. Wenn der Wert mit demselben Schlüssel zur Karte hinzugefügt wird, wird er ersetzt. Es hat die folgenden Vor- und Nachteile:

Schlüssel und Werte können jeden Typ haben, einschließlich Objekte.

Unterstützt Array-Syntax (eckige Klammern).

Einfügereihenfolge ist bleibt erhalten.

Leistung und Effizienz des Speichers sind einem Array sehr ähnlich.

Gibt zugewiesenen Speicher automatisch frei, wenn seine Größe niedrig genug ist.

Kann nicht konvertiert werden zu einem Array, wenn Objekte als Schlüssel verwendet werden.

Paarklasse:

Ein Paar wird von DsMap verwendet, um Schlüssel mit Werten zu koppeln.

Klasse festlegen:

Ds\Pair implements JsonSerializable {
/* 方法 */
public construct ([ mixed $key [, mixed $value ]] )
}

Folge eindeutiger Werte. Diese Implementierung verwendet dieselbe Hash-Tabelle wie DsMap, wobei Werte als Schlüssel verwendet werden und der zugeordnete Wert ignoriert wird. Sie hat die folgenden Vor- und Nachteile:

Werte können jeden Typ haben, einschließlich Objekte.

Unterstützt Array-Syntax (eckige Klammern).

Einfügereihenfolge bleibt erhalten.

Gibt zugewiesenen Speicher automatisch frei, wenn seine Größe niedrig genug ist.

add( ), entfernen() und enthält() sind alle O(1).

unterstützt aber nicht push(), pop(), insert(), shift() oder unshift() . get() ist O(n), wenn vor dem Zugriffsindex gelöschte Werte vorhanden sind, andernfalls O(1)

Stack Class:

„last „In, First Out“-Sammlung, erlaubt nur den Zugriff und die Iteration an der Spitze der Struktur.

Warteschlangenklasse:

Ds\Stack implements Ds\Collection {
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Stack copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

„First in, first out“-Sammlung, die Zugriff und Iteration nur am vorderen Ende der Struktur ermöglicht.

PriorityQueue-Klasse:

Ds\Queue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Queue copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

PrioritätEine Warteschlange ist einer Warteschlange sehr ähnlich, aber Werte werden mit einer angegebenen Priorität in die Warteschlange geschoben, mit der höchste Priorität Der Wert steht immer an der Spitze der Warteschlange und die „First in, first out“-Reihenfolge von Elementen mit derselben Priorität bleibt weiterhin erhalten. Die Iteration auf einer PriorityQueue ist destruktiv und entspricht kontinuierlichen Pop-Vorgängen, bis die Warteschlange leer ist. Implementiert mit einem maximalen Heap.

Das obige ist der detaillierte Inhalt vonAnalyse von DS-Erweiterungsbeispielen in der PHP-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!