向末尾添加元素后，PersistentVector与PersistentList的seq性能对比问询

1. seq调用的初始开销差异 #

• 对于PersistentList（即字面量'(1 2 3)）：seq调用几乎无开销，因为PersistentList本身实现了Seq接口，调用seq直接返回列表自身的引用，不需要额外对象创建。
• 对于PersistentVector（即字面量[1 2 3]）：seq会创建一个VectorSeq实例，该实例持有向量引用和初始遍历索引（0）。这个对象创建过程会带来微小但可测的初始开销，因此第一次调用seq [1 2 3]比seq '(1 2 3)稍慢。

2. 添加元素后的seq表现 #

无论向两种集合添加元素（均为不可变操作，返回新集合实例）：

• 新的PersistentList（通过conj向头部添加元素）：seq调用依然直接返回自身，无额外开销。
• 新的PersistentVector（通过conj向尾部添加元素）：seq仍需创建新的VectorSeq实例，开销与原向量的seq调用一致（仅固定的对象创建成本，与向量大小无关）。

3. 遍历阶段的性能差异 #

除了初始seq创建的开销，遍历两者的seq时性能也有区别：

• PersistentList的seq遍历：每次next操作直接获取链表的下一个节点，时间复杂度为O(1)，遍历全程性能稳定。
• VectorSeq的遍历：每次next操作通过索引访问向量元素，向量的索引访问是O(log₃₂N)的时间复杂度（N为向量元素数）。当元素数量较小时，这个差异不明显；但当N很大时，list的seq遍历速度会显著快于vector的seq。

4. 其他细节 #

• 多次调用seq同一向量：每次都会创建新的VectorSeq实例，重复产生初始开销；而多次调用seq同一列表则始终返回同一引用，无重复开销。
• 类型差异之外，两者的seq在功能上等价（都遵循Clojure的Seq协议），但底层实现机制导致了上述性能差异。

内容的提问来源于stack exchange，提问作者rusfrompiter