PHP Conference Japan 2024

    Set 類別

    (PECL ds >= 1.0.0)

    簡介

    Set 是一組不重複值的序列。此實作使用與 Ds\Map 相同的雜湊表，其中值被用作鍵，而對應的值則被忽略。

    優點

    • 值可以是任何類型，包括物件。
    • 支援陣列語法（方括號）。
    • 保留插入順序。
    • 當大小降低到足夠低時，會自動釋放已配置的記憶體。
    • add()、remove() 和 contains() 的時間複雜度皆為 O(1)。

    缺點

    • 不支援 push()、pop()、insert()、shift() 或 unshift()。
    • 如果在被訪問索引之前緩衝區中有已刪除的值，則 get() 的時間複雜度為 O(n)，否則為 O(1)。

    類別概要

    class Ds\Set implements Ds\Collection, ArrayAccess {
    /* 常數 */
    const int MIN_CAPACITY = 16;
    /* 方法 */
    public add(mixed ...$values): void
    public allocate(int $capacity): void
    public capacity(): int
    public clear(): void
    public contains(mixed ...$values): bool
    public copy(): Ds\Set
    public diff(Ds\Set $set): Ds\Set
    public filter(callable $callback = ?): Ds\Set
    public first(): mixed
    public get(int $index): mixed
    public intersect(Ds\Set $set): Ds\Set
    public isEmpty(): bool
    公開 join(字串 $glue = ?): 字串
    公開 last(): 混合
    公開 map(可呼叫 $callback): Ds\Set
    公開 merge(混合 $values): Ds\Set
    公開 reduce(可呼叫 $callback, 混合 $initial = ?): 混合
    公開 remove(混合 ...$values): 無
    公開 reverse(): 無
    公開 reversed(): Ds\Set
    公開 slice(整數 $index, 整數 $length = ?): Ds\Set
    公開 sort(可呼叫 $comparator = ?): 無
    公開 sorted(可呼叫 $comparator = ?): Ds\Set
    公開 sum(): 整數|浮點數
    公開 toArray(): 陣列
    公開 union(Ds\Set $set): Ds\Set
    public xor(Ds\Set $set): Ds\Set
    }

    預定義常數

    Ds\Set::MIN_CAPACITY

    更新日誌

    版本 說明
    PECL ds 1.3.0 此類別現在實作 ArrayAccess 介面。
    PECL ds 1.2.7 新增 Ds\Set::map() 方法。

    目錄

    發現問題了嗎？

    了解如何改進此頁面 • 提交拉取請求 • 回報錯誤
    ＋新增註釋

    使用者貢獻的註釋 2 則註釋

    19
    匿名
    6 年前
    集合的查找應該是 O(1)。這適用於任何語言的集合和雜湊表（例如映射）。

    這是可能的，因為集合儲存值的方式與陣列不同。

    在陣列中，值的儲存方式是基於它們在陣列中的位置以及該陣列在記憶體中的位置而依序排列的，因此要找到您的項目，您需要依序掃描整個陣列（除非它是一個已排序的陣列，那麼您可以使用二元搜尋，其時間複雜度為 O(logn)）。

    集合（Set）會宣告一個記憶體區塊，就像陣列一樣，但它並不像陣列那樣依序將項目放入記憶體，而是透過將項目傳入雜湊函式（本質上是一個接受物件並返回均勻分佈的非常大的隨機數的函式）來決定要新增項目的索引，然後將該雜湊函式的結果除以它們擁有的記憶體區塊大小的餘數。

    因此，當您呼叫 contains($needle, $mySetHaystack) 時，PHP 會將 $needle 傳入雜湊函式，該函式會返回一個很大的數字，例如 9283472378，然後它會取得 $mySetHaystack 的長度（假設為 31），並執行 9283472378 % 31 = 28，因此它會檢查 $mySetHaystack 的第 28 個索引，看看 $needle 是否在那裡。此操作列表中的所有操作都與 $mySetHaystack 的大小無關，因此效能為 O(1)。

    如果雜湊函式針對兩個不同的項目返回相同的值（雜湊碰撞，這完全有可能發生），或者如果該值的餘數相同，則會在該索引的集合中儲存一個值陣列。由於集合不允許重複值，因此這種情況很少發生，並且從效能的角度來看可以忽略不計。

    您應該查看維基百科上關於雜湊表（類似於集合）的頁面，因為有很多圖片可以讓您更容易理解這個概念。
    7
    Sébastien
    2 年前
    一個很棒的功能是類型感知。 array_unique() 會遺失值（無論使用何種旗標），而 Ds\Set 會保留它們。

    <?php

    $array     = [true, false, null, '', 0, '0', 123, '123'];
    var_dump(array_unique($array));
    var_dump(new \Ds\Set($array));

    /*

    結果：

    array(4) {
    [0]=> bool(true)
    [1]=> bool(false)
    [4]=> int(0)
    [6]=> int(123)
    }
    object(Ds\Set)#1 (8) {
    [0]=> bool(true)
    [1]=> bool(false)
    [2]=> NULL
    [3]=> string(0) ""
    [4]=> int(0)
    [5]=> string(1) "0"
    [6]=> int(123)
    [7]=> string(3) "123"
    }

    */
    ＋新增註釋
    To Top