FSharpx.DataStructures

GitHub repository of FSharpx.Core.DataStructures

Functional Data Structures in Typed Racket

FSharpx.DataStructures Performance Metrics

BootstrappedQueue


BootstrappedQueue Performance Metrics

Observations

Purely Functional

  1. Generally good create and populate (Init, new(), and AddOne Actions) performance up to scale 106.
  2. AddOne Action performance relative to Init shows marked slowdown at scale 105.

No constructor, but you can use the only type member NonEmptyBootstrappedQueue.create in a non-obvious way to quickly instantiate from a List.

Should be incorporated into an ofList member.

BootstrappedQueue Docs


module members

head : 'a BootstrappedQueue -> 'a

Returns first (head) element.

Complexity: O(1)
Usage: 


isEmpty : 'a BootstrappedQueue -> bool

Queue is empty or not.

Complexity: O(1)
Usage: 


snoc : 'a -> 'a BootstrappedQueue -> 'a BootstrappedQueue

Add an element to the right (snoc is cons spelled backwards).

Complexity: O(Log* n)
Usage: 


tail : 'a BootstrappedQueue -> 'a BootstrappedQueue

Returns tail element.

Complexity: O(Log* n)
Usage: 


tryGetHead : 'a BootstrappedQueue -> BootstrappedQueue<'a> option

Returns option tail element.

Complexity: O(1)
Usage: 


tryGetTail : 'a BootstrappedQueue -> BootstrappedQueue<'a> option

Returns option tail element.

Complexity: O(Log* n)
Usage: 





DList

DList Performance Metrics
Observations

Purely Functional

  1. Init performance always better than AddOne, very noticeable starting at scale 104.

A Difference List, or DList, is an implementation of John Hughes’ append list. This implementation adds an additional parameter to allow a more efficient calculation of the list length.

Note that an alternate form would represent the DList as:
type DList<'a> = DList of ('a list -> 'a list)

DList Docs


Constructors:

DList has no constructors. Instantiate a DList through one of the DList Module operators.
type members


Head : unit -> 'a

Returns first (head) element.

Complexity: O(log n)
Usage: 


IsEmpty : unit -> bool

Returns bool indicating match with Nil.

Complexity: O(1)
Usage: 
let x = DList.empty
let b = x.IsEmpty


Length : unit -> int

Returns the number of items in the collection.

Complexity: O(1)
Usage: 


Tail : unit -> Dlist<'a>

Returns the DList tail (all elements after the first)

Complexity: O(log n)
Usage: 



module members

append : DList<'a> -> DList<'a> -> DList<'a>

Complexity: O(1)
Usage:


cons : 'a Dlist<'a> -> Dlist<'a>

Returns a new DList with element added at head.

Complexity:
Usage:



empty: 'a -> DList<'a>

Empty DList

Complexity: O(1)
Usage:


fold : ('a -> 'b -> 'a) -> 'a -> DList<'b> -> 'a

Complexity: O(n)
Usage:


head : DList<'a> -> 'a

Returns first (head) element.

Complexity: O(log n)
Usage:


isEmpty : DList<'a> -> bool

Complexity: O(1)
Usage: 


length : DList<'a> -> int

Returns the number of items in the collection.

Complexity: O(1)
Usage:


ofSeq : seq<'a> -> DList<'a>

Complexity: O(n)
Usage: 


singleton : 'a -> DList<'a>

Complexity: O(1)
Usage: 


tail : Dlist<'a> -> Dlist<'a>

Returns the DList tail (all elements after the first)

Complexity: O(log n)

Usage:

toList : Dlist<'a> -> list<'a>

Complexity:
Usage:

toArray : Dlist<'a> -> 'a[]

Complexity:

Usage:



See also:


ImplicitQueue

ImplicitQueue Performance Metrics
Observations

Purely Functional

  1. Good scaling performance of AddOne. No native Init or new() Action.


ImplicitQueue Docs

module members

head : 'a ImplicitQueue -> 'a

Returns first (head) element.

Complexity: O(1)
Usage: 


isEmpty : 'a ImplicitQueue -> bool

Queue is empty or not.

Complexity: O(1)
Usage: 


snoc : 'a -> 'a ImplicitQueue -> 'a BootstrappedQueue

Add an element to the right (snoc is cons spelled backwards).

Complexity: O(1)
Usage: 


tail : 'a ImplicitQueue -> 'a ImplicitQueue

Returns tail element.

Complexity: O(1)
Usage: 


tryGetHead : 'a ImplicitQueue -> ImplicitQueue<'a> option

Returns option tail element.

Complexity: O(1)
Usage: 


tryGetTail : 'a ImplicitQueue -> ImplicitQueue<'a> option

Returns option tail element.

Complexity: O(1)
Usage: 





RealTimeQueue

RealTimeQueue Performance Metrics
Observations

Purely Functional

  1. Stack overflow at scale 105 in both 64 and 32-bit systems.
  2. Up to scale 104 AddOne scaling is close to O(1).
  3. No native Init or new() Action.


RealTimeQueue Docs

module members

head : 'a RealTimeQueue -> 'a

Returns first (head) element.

Complexity: O(1)
Usage: 


isEmpty : 'a RealTimeQueue -> bool

Queue is empty or not.

Complexity: O(1)
Usage: 


snoc : 'a -> 'a RealTimeQueue -> 'a BootstrappedQueue

Add an element to the right (snoc is cons spelled backwards).

Complexity: O(1)
Usage: 


tail : 'a RealTimeQueue -> 'a RealTimeQueue

Returns tail element.

Complexity: O(1)
Usage: 


tryGetHead : 'a RealTimeQueue -> BootstrappedQueue<'a> option

Returns option tail element.

Complexity: O(1)
Usage: 


tryGetTail : 'a RealTimeQueue -> RealTimeQueue<'a> option

Returns option tail element.

Complexity: O(1)
Usage: 





Vector

Persitent Vector Performance Metrics
Transient Vector Performance Metrics
Persitent Vector Observations

Purely Functional

  1. AddOne Action performance deteriorates at scale 104 or 105.
  2. Init Action (ofSeq) performance good through scale 105.


Transient Vector Observations

Not Purely Functional

  1. AddOne Action performance good through scale 106.

Ported from the Clojure implementation, a Vector is a collection of values indexed by contiguous integers implemented as an immutable hash array mapped trie.

Vector Docs

Constructors:

The Vector supports constructors for two underlying types, PersistentVector and TransientVector. If only one reference of the Vecor is to be held, TransientVector mutates the underlying data representation rather than copying on every change (i.e. it is not strictly purely functional).

type members


AssocN : int*'a -> IVector<'a>

Returns a new vector (or the modifies the TransientVector) that contains the given value at the index. Index must be <= vector.Count.

Complexity: 
Usage: 


Conj : 'a -> IVector<'a>

Returns a new vector with the element ‘added’ at the end.

Complexity: O(1)
Usage: 
let vP = empty
let vP2 = vP.Conj(4).Conj(5)


Count : unit -> int

Returns the number of items in the collection.

Complexity: O(1)
Usage: 
let vP = empty
let vP2 = vP.Conj(4).Conj(5)
printfn "%i" (vP2.Count())


Item : int -> 'a

Returns the value at the index. If the index is out of bounds it throws an exception.

Complexity: O(log32n)
Usage: 


Peek : unit -> 'a

Returns the last element in the vector. If the vector is empty it throws an exception.

Complexity: O(1)
Usage: 


Pop : unit -> IVector<'a>

Returns a new vector without the last item. If the collection is empty it throws an exception.

Complexity: O(1)
Usage: 



module members

assocN: 'a -> 'a IVector -> 'a IVector

Returns a new vector that contains the given value at the index. Index must be <= vector.Count.

Complexity: 
Usage: 


count : 'a IVector -> int

Returns the number of items in the collection

Complexity: O(1)
Usage: 


empty: <'a> -> 'a PersistentVector

Empty PersistentVector of type ‘a.

Complexity: O(1)
Usage: 


nth: i:int -> 'a IVector -> 'a

Returns the value at the index. If the index is out of bounds it throws an exception.

Complexity: O(1)
Usage: 


cons: 'a -> 'a IVector -> 'a IVector

Returns a new vector with the element ‘added’ at the end.

(Unfortunate operator name inherited from the Clojure implementation. Should be renamed to “conj”.)

Complexity: 
Usage: 


init: count:int -> (f: int -> 'a) -> 'a PersistentVector

Creates a PersistentVector by calling the given generator on each index for the count.

Complexity: O(n)
Usage: 


map: (f:'a -> 'b) -> 'a IVector -> 'b PersistentVector

Creates a new PersistentVector whose elements are the results of applying the given function to each of the elements of the Vector.

Complexity: O(n)
Usage:

ofSeq : 'a seq -> 'a PersistentVector

Creates a new PersistentVector from the given enumerable object.

Complexity: O(n)

Usage:

peek: 'a IVector -> 'a

Returns the last element in the vector. If the vector is empty it throws an exception.

Complexity: O(1)
Usage:


pop: ('a IVector) -> IVector<'a>

Returns a new persistent Vector without the last item, or the same transient vector without the last item. If the collection is empty it throws an exception.

Complexity: O(1)
Usage:



See also:

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>