As a data container, what are the main differences

问题:

Say we need a list of numbers, there are two definitions:

(def vector1 [1 2 3])
(def list2 '(1 2 3))

So what are the main differences?

回答1:

The [1 2 3] is a vector, whereas '(1 2 3) is a list. There are different performance characteristics of these two data structures.

Vectors provide quick, indexed random access to its elements (v 34) returns element of vector v at index 34 in O(1) time. On the other hand it is generally more expensive to modify vectors.

Lists are easy to modify at head and/or tail (depending on implementation), but provide linear access to elements: (nth (list 1 2 3 4 5) 3) requires sequential scan of the list.

For more information on the performance tradeoffs you can google "vector vs. list performance" or something similar.

[FOLLOW-UP]

Ok, lets get into some more detail. First of all vectors and lists are concepts that are not specific to Clojure. Along with maps, queues, etc., they are abstract types of collections of data. Algorithms operating on data are defined in terms of those abstractions. Vectors and lists are defined by the behavior that I briefly described above (i.e. something is a vector if it has size, you can access its elements by and index in constant time etc.).

Clojure, as any other language, wants to fulfill those expectations when providing data structures that are called this way. If you'll look at the basic implementation of nth in vector, you'll see a call to arrayFor method which has the complexity of O(log₃₂N) and a lookup in Java array which is O(1).

Why can we say that (v 34) is in fact O(1)? Because the maximum value of log₃₂ for a Java int is around 7. This means that random access to a vector is de facto constant time.

In summary, the main difference between vectors and lists really is the performance characteristics. Additionally, as Jeremy Heiler points out, in Clojure there are logical differences in behaviour, i.e. with respect to growing the collection with conj.

回答2:

There are two main differences between lists and vectors.

1. Lists logically grow at the head, while vectors logically grow on the tail. You can see this in action when using the conj function. It will grow the collection according to the type of collection given to it. While you can grow collections on either side, it is performant to do so in this way.

2. In order to retrieve the nth item in a list, the list needs to be traversed from the head. Vectors, on the other hand, are not traversed and return the nth item in O(1). (It really is O(log32n) but that is due to how the collections are implemented as persistent collections.)

回答3:

vector assess time is not O(1) it's log32N

Vectors (IPersistentVector) A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. count is O(1). conj puts the item at the end of the vector. Vectors also support rseq, which returns the items in reverse order. Vectors implement IFn, for invoke() of one argument, which they presume is an index and look up in themselves as if by nth, i.e. vectors are functions of their indices.

回答4:

• A vector holds all data items in adjacent areas of memory, making transfer of the entire vector easy and insertion or deletion of items expensive when compared with lists.

• Lists hold items is disjoint areas of memory, making transfer of the entire list expensive but insertion and deletion of individual items relatively cheap.

• Classic vectors are also fixed in size, and limited to N items, while lists can dynamically grow and shrink.

• Vectors also offer indexed access to the element items. Lists don't. The classic vector's predecessor is an array.
• Modern implementations of vectors often aim at providing similar characteristic, but the underlying data structure may in fact be a list or a hash, and those vectors typically support dynamic re-sizing.