WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

"ExtensibleVector" (Data Structure)

"ExtensibleVector"

represents a dynamically extensible vector where the elements are general expressions.

Details

  • An extensible vector is useful for continuously appending and prepending elements, as well as for efficient element extraction and updating.
  • CreateDataStructure[ "ExtensibleVector"]create a new empty "ExtensibleVector"
    CreateDataStructure[ "ExtensibleVector",elems]create a new "ExtensibleVector"containing elems
    Typed[x,"ExtensibleVector"]give x the type "ExtensibleVector"
  • For a data structure of type "ExtensibleVector", the following operations can be used:
  • ds["Append",x]append x to dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["Drop",i]drop the i^(th) part of dstime: O(n)
    ds["DropAll"]drop all the elements from dstime: O(n)
    ds["DropLast"]drop the last element of dstime: O(1)
    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,init]apply fun to the elements of ds, starting with init, accumulating a resulttime: O(n)
    ds["Insert",x,i ]insert x into ds at position itime: O(1)
    ds["JoinBack",elems ]join elems to the back of dstime: O(nelems)
    ds["JoinFront",elems ]join elems to the front of dstime: O(nelems)
    ds["Length",x]the number of elements stored in dstime: O(1)
    ds["Part",i]give the i^(th) part of dstime: O(1)
    ds["Prepend",x]prepend x to dstime: O(1)
    ds["SetPart",i,elem]update the i^(th) part of dstime: O(1)
    ds["SwapPart",i,j]swap the i^(th) and j^(th) parts of dstime: O(1)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    ds["Part",i]=valset i^(th) element of ds to val
    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 allclose all

Basic Examples  (2)Summary of the most common use cases

A new "ExtensibleVector" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ck3oom
Out[1]=1

Elements can be appended:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-84r1md
Out[2]=2

Elements can be prepended:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-k7y0gt
Out[3]=3

Return the length:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-tnm4iz
Out[4]=4

Extract the first element:

In[5]:=5
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-kfcutb
Out[5]=5

Change an element:

In[6]:=6
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-2ymbbr
Out[6]=6

The element has updated:

In[7]:=7
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-3dkxgf
Out[7]=7

Return an expression version of ds:

In[8]:=8
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-gzceda
Out[8]=8

It is fast to append:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-mfljzp

A visualization of the data structure can be generated:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-uvwa1b
Out[2]=2

Sum all the elements:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-volwmf
Out[3]=3

Scope  (1)Survey of the scope of standard use cases

Information  (1)

A new "ExtensibleVector" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-olwaxi
Out[1]=1

Information about the data structure ds:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-5du3om
Out[2]=2

Applications  (11)Sample problems that can be solved with this function

Reverse  (1)

A simple function that carries out an in-place reverse of a "ExtensibleVector":

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-k1geif

A sample data structure to use:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ok3cxr

Reverse the elements:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-v6s7yl
Out[3]=3

Bubble Sort  (1)

Bubble sort is a simple sorting algorithm that is easy to code but typically has poor performance:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-qfxr7a

A sample data structure to use:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-6iij4g

Sort the elements:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ch3pow
Out[3]=3

The data structure is sorted in place:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-jwd12t
Out[4]=4

Insertion Sort  (1)

Insertion sort is a simple sorting algorithm that is easy to code and typically has poor performance for large arrays, but can be useful for small arrays:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-uuea2a

A sample data structure to use:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-rnvca7

Sort the elements:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-qbnzb1
Out[3]=3

The data structure is sorted in place:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-f26i23
Out[4]=4

Quicksort  (1)

Quicksort is an efficient sorting algorithm. This basic implementation uses nested functions:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-0b81qa

A sample data structure to use:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ys4psf

Sort the elements:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-2jbmri
Out[3]=3

The data structure is sorted in place:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-pd9hqf
Out[4]=4

Merge Sort  (1)

Merge sort is an efficient sorting algorithm. This is a simple implementation that uses a workspace:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-8w3b15
In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-gks9ef
In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-8uh2mt

A sample data structure to use:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-jfrp9i

Sort the elements:

In[5]:=5
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-q8dqik
Out[5]=5

The data structure is sorted in place:

In[6]:=6
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-f2jg3j
Out[6]=6

Heapsort  (1)

Heapsort is an efficient sorting algorithm that works in place by constructing a heap:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-lbn5i7
In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-wkx57e

A sample data structure to use:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-0qbb4d

The elements are sorted in place:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-dcq0in
Out[4]=4

Timsort  (1)

Timsort is a hybrid and efficient sorting algorithm:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-utwzvk
In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-xxk8ku
In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-8u8nt2

A sample data structure to use:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-3867c2

The elements are sorted in place:

In[5]:=5
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-e3olpb
Out[5]=5

Fisher–Yates Shuffle  (1)

The Fisher–Yates shuffle generates a random permutation of a finite sequence:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ypbhro

A sample array to use for the shuffle:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-fsx11v

Apply the shuffle:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-p7mn4c
Out[3]=3

Palindrome  (1)

An array is a palindrome if it is symmetric around the middle:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-n6d0i7

This is not a palindrome:

In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-n03e3z
Out[2]=2

This is a palindrome:

In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-ikw268
Out[3]=3

Quickselect  (1)

Quickselect is a selection algorithm related to the Quicksort algorithm. It returns the k^(th) smallest element in a list:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-oem0o9
In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-owe0hl
In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-fn1ton

A sample data structure to use:

In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-wbvmlh

The third smallest element is 7:

In[5]:=5
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-kqha7h
Out[5]=5

Heap  (1)

A heap is a tree-based data structure where the value stored at children is smaller than that stored in their parents (for a min heap). It is commonly used to implement a priority queue and typically implemented with an array rather than a tree.

The following converts an array into a heap:

In[1]:=1
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-qkp2f3
In[2]:=2
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-6gbdr5
In[3]:=3
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-xf77l5
In[4]:=4
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-o02ioi
In[5]:=5
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-5jwtn1

A sample data structure to use:

In[6]:=6
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-xehzyv

This converts the array into a heap; it is hard to see the heap property:

In[7]:=7
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-pp3guy
Out[7]=7

This function generates a tree:

In[8]:=8
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-854ywl

A visualization makes it easier to see the min heap property:

In[9]:=9
✖
https://wolfram.com/xid/0l9u54bv5xcg6m6wyodxn26i-86qyu2
Out[9]=9

Properties & Relations  (2)Properties of the function, and connections to other functions

"FixedArray"  (1)

Many algorithms that work for "ExtensibleVector" also work for "FixedArray".

"DynamicArray"  (1)

Many algorithms that work for "ExtensibleVector" also work for "DynamicArray".