斯卡拉方法的漸近行爲

Question

是否有某處我可以找到預期的時間和空間像HashSet，TreeSet，List等集合上的操作的複雜性？

是否有人希望從抽象數據類型本身的屬性中知道這些？

我知道Performance characteristics for Scala collections，但這隻提到一些非常基本的操作。也許這些集合的其餘操作純粹是從一個小的基礎集合中構建的，但是，那麼我只是希望知道他們已經以這種方式實現了它們？

Answer 1

其他方法的性能特徵很難斷言。考慮以下幾點：

• 這些方法都是基於foreach或iterator全部實現，並且通常在非常高的水平的層次結構。例如，Vector的map在collection.TraversableLike上實現。 若要添加侮辱傷害，使用哪種方法實現取決於類繼承的線性化。這也適用於任何稱爲助手的方法。之前發生的變化造成了無法預料的性能問題。 由於foreach和iterator都是O(n)，任何改進的性能取決於其他方法的專業化，如size和slice。
• 對於其中許多人來說，進一步依賴於所提供的構建器的性能特徵，這取決於調用站點而不是定義站點。

所以結果是，方法被定義並記錄在案的地方沒有足夠的信息來陳述其性能特徵，並且可能不僅取決於繼承如何實現其他方法集合，但是即使是通過從CanBuildFrom獲取的對象Builder的構建器的性能特徵，也可以通過調用站點傳遞。

充其量，任何這樣的文檔都會用其他方法來描述。這並不意味着它是不值得的，但這並不容易 - 開源項目上的艱鉅任務取決於志願者，他們通常以他們喜歡的方式工作，而不是需要什麼。

Answer 2

其他方法的指南應該是 - 只要想一下有效的實現應該是什麼樣子。

集合上的大多數其他批量操作（處理集合中每個元素的操作）爲O(n)，因此它們在此處未提及。例子是filter，map，foreach，indexOf，reverse，find ...

方法返回的迭代器或流像combinations和permutations通常O(1)。

涉及2個藏品的方法通常是O(max(n, m))或O(min(n, m))。這些都是zip，zipAll，sameElements，corresponds，...

方法union，diff，並intersect是O(n + m)。

排序變體自然是O(nlogn)。在當前實現中，groupBy是O(nlogn)。 indexOfSlice使用KMP算法並且是O(m + n)，其中m和n是字符串的長度。

方法如+:，:+或patch通常O(n)，除非你正在處理的不可變集合爲所討論的操作是更有效的特定情況下 - 例如，在官能List前面加上一個元件或將元素附加到Vector。

方法toX通常是O(n)，因爲他們必須遍歷所有元素並創建一個新的集合。 toStream是一個例外，它懶洋洋地構建了這個集合 - 因此它是O(1)。此外，無論何時X是集合的類型toX只是返回this，是O(1)。

迭代器實現應該有一個O(1)（攤銷）next和hasNext操作。迭代器創建應該是最差情況O(logn)，但在大多數情況下是O(1)。