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
— TypeOrderedDict
OrderedDict
s are simply dictionaries whose entries have a particular order. The order refers to insertion order, which allows deterministic iteration over the dictionary.
OrderedCollections.OrderedSet
— TypeOrderedSet
OrderedSet
s 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]...)
OrderedCollections.LittleDict
— TypeLittleDict(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.
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 Tuple
s will not require any copies to create the LittleDict
, so LittleDict(ks::Tuple, vs::Tuple)
is the fastest constructor of all.
OrderedCollections.freeze
— Functionfreeze(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.
OrderedCollections.isordered
— Functionisordered(::Type)
Property of associative containers, that is true
if the container type has a defined order (such as OrderedDict
and SortedDict
), and false
otherwise.