WOLFRAM

Wolfram Language & System Documentation Center

"ImmutableVector" (Data Structure)

"ImmutableVector"

represents an immutable vector where modifications generate a new data structure and the elements are general expressions.

Details

  • An immutable vector is useful for efficiently adding and removing elements without modifying the data structure in place.
  • An immutable vector uses structural sharing, which results in performance-bound guarantees.
  • CreateDataStructure["ImmutableVector"]create a new empty "ImmutableVector"
    CreateDataStructure["ImmutableVector",elems]create a new "ImmutableVector" containing elems
    Typed[x,"ImmutableVector"]give x the type "ImmutableVector"
  • For a data structure of type "ImmutableVector", the following operations can be used:
  • ds["Append",x]return a new immutable vector with x appended to dstime: O(log n)
    ds["DropLast"]return a new immutable vector with the last element of ds droppedtime: O(log n)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no elementstime: O(1)
    		ds["Fold",fun]apply fun to the elements of ds, accumulating a resulttime: O(n)
    ds["Fold",fun,init]apply fun to the elements of ds, starting with init, accumulating a resulttime: O(n)
    ds["JoinBack",elems]join elems to the back of dstime: O(nelems)
    ds["Length"]the number of elements stored in dstime: O(1)
    ds["Part",i]give the i^(th) part of dstime: O(log n)
    ds["ReplacePart",ix]return a new immutable vector with the i^(th) part replaced by xtime: O(log n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open all close all

Basic Examples  (2)

A new "ImmutableVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["ImmutableVector"]

Elements can be appended:

Wolfram Language code: ds1 = ds["Append", f[1]]

Return the length:

Wolfram Language code: ds1["Length"]

The length of the original vector did not change:

Wolfram Language code: ds["Length"]

Extract the first element:

Wolfram Language code: ds1["Part", 1]

Replace an element:

Wolfram Language code: ds2 = ds1["ReplacePart", 1 -> g[1]]

ds1 remains unchanged:

Wolfram Language code: ds1["Part", 1]

ds2 has the replaced value:

Wolfram Language code: ds2["Part", 1]

Return expression version of ds:

Wolfram Language code: Normal[ds2]

It is efficient to append elements:

Wolfram Language code: ds = CreateDataStructure["ImmutableVector"]; Do[ds = ds["Append", i], {i, 1, 1000}]

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Sum all elements:

Wolfram Language code: ds["Fold", Plus, 0]

Scope  (2)

Efficiency  (1)

"ImmutableVector" is efficient at appending elements:

Wolfram Language code: ds = CreateDataStructure["ImmutableVector"]; Do[ds = ds["Append", i], {i, 1, 50000}]//AbsoluteTiming

Regular list expressions are not as fast for appending:

Wolfram Language code: list = {}; Do[list = Append[list, i], {i, 1, 50000}]//AbsoluteTiming

Association is also fast for appending, but gives a key rather than an index view into the data:

Wolfram Language code: assoc = <||>; Do[assoc = Append[assoc, i -> i], {i, 1, 50000}]//AbsoluteTiming

Information  (1)

A new "ImmutableVector" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["ImmutableVector"]

Information about the data structure ds:

Wolfram Language code: Information[ds]