OrderedCollections.jl

This package implements associative containers that preserve the order of insertion:

OrderedDict
OrderedSet
LittleDict

OrderedSets

OrderedSets are sets whose entries have a particular order. Order refers to insertion order, which allows deterministic iteration over the set:

using Base.MathConstants
s = OrderedSet((π,e,γ,catalan,φ))
for x in s
   println(x)
end
#> π = 3.1415926535897...
#> ℯ = 2.7182818284590...
#> γ = 0.5772156649015...
#> catalan = 0.9159655941772...
#> φ = 1.6180339887498...

All Set operations are available for OrderedSets.

Note that to create an OrderedSet of a particular type, you must specify the type in curly-braces:

# create an OrderedSet of Strings
strs = OrderedSet{AbstractString}()

OrderedDicts

Similarly, OrderedDict are simply dictionaries whose entries have a particular order.

d = OrderedDict{Char,Int}()
for c in 'a':'d'
    d[c] = c-'a'+1
end
for x in d
   println(x)
end
#> 'a' => 1
#> 'b' => 2
#> 'c' => 3
#> 'd' => 4

The insertion order is conserved when iterating on the dictionary itself, its keys (through keys(d)), or its values (through values(d)). All standard Associative and Dict functions are available for OrderedDicts

LittleDict

d = LittleDict{Char,Int}()
for c in 'a':'d'
    d[c] = c-'a'+1
end
for x in d
   println(x)
end
#> 'a' => 1
#> 'b' => 2
#> 'c' => 3
#> 'd' => 4

The LittleDict acts similarly to the OrderedDict. However for small collections it is much faster. Indeed the preceeding example (with the io redirected to devnull), runs 4x faster in the LittleDict version as the earlier OrderedDict version.

OrderedCollections.OrderedDict — Type

OrderedDict

OrderedDicts are simply dictionaries whose entries have a particular order. The order refers to insertion order, which allows deterministic iteration over the dictionary.

source

OrderedCollections.OrderedSet — Type

OrderedSet

OrderedSets are simply sets whose entries have a particular order. The order refers to insertion order, which allows deterministic iteration over the set.

Note: To create an OrderedSet of a particular type, you must specify the type, such as,

os = OrderedSet{Int}(3)
push!(os, [1,2]...)

source

OrderedCollections.LittleDict — Type

LittleDict(keys, vals) <: AbstractDict

An ordered dictionary type for small numbers of keys. Rather than using hash or some other sophisticated measure to store the vals in a clever arrangement, it just keeps everything in a pair of lists.

While theoretically this has expected time complexity O(n) (vs the hash-based OrderedDict/Dict's expected time complexity O(1), and the search-tree-based SortedDict's expected time complexity O(log(n))), in practice it is really fast, because it is cache & SIMD friendly.

It is reasonable to expect it to outperform an OrderedDict, with up to around 30 elements in general; or with up to around 50 elements if using a LittleDict backed by Tuples (see freeze) However, this depends on exactly how long isequal and hash take, as well as on how many hash collisions occur etc.

Note

When constructing a LittleDict it is faster to pass in the keys and values each as seperate lists. So if you have them seperately already, do LittleDict(ks, vs) not LittleDict(zip(ks, vs)). Furthermore, key and value lists that are passed as Tuples will not require any copies to create the LittleDict, so LittleDict(ks::Tuple, vs::Tuple) is the fastest constructor of all.

source

OrderedCollections.LittleSet — Type

LittleSet([itr]) <: AbstractSet

Constructs an ordered set optimized for a small number of elements, given the iterable itr. The underlying data is stored as either an AbstractVector or a Tuple and is optimal for 30-50 elements, similar to LittleDict.

source

OrderedCollections.freeze — Function

freeze(dd::AbstractDict)

Render a dictionary immutable by converting it to a Tuple-backed LittleDict. The Tuple-backed LittleDict is faster than the Vector-backed LittleDict, particularly when the keys are all concretely typed.

source

OrderedCollections.isordered — Function

isordered(::Type)

Property of associative containers, that is true if the container type has a defined order (such as OrderedDict and SortedDict), and false otherwise.

source