IntArray is a data structure to store and manipulate an array of unsigned integers using as small space as possible.
Each element in the IntArray{w} type is packed using w bits. So you can store integers between 0x00 and 0x03 with 2 bits per element while Array{UInt8} requires 8 bits: the required space is one-quarter!
In [1]:
using IntArrays
Only one type is exported from this package: IntArray.
The IntArray type takes three type parameters:
w: the width (or bits) of integersT: the element type of an arrayn: the number of dimensions of an array.For example, IntArray{2,UInt8,1} is a one-dimensional array (or vector) of UInt8 integers packed in 2 bits.
Like the Vector{T} and Matrix{T} types in the standard library, IntVector{w,T} and IntMatrix{w,T} are type aliases of IntArray{w,T,1} and IntArray{w,T,2}, respectively.
In [2]:
srand(123456);
You can construct an IntArray object from an existing array with given width:
In [3]:
# construct an array
vec = rand(0x00:0x03, 8)
Out[3]:
In [4]:
# convert it to IntVector with 2-bit packing
ivec = IntArray{2}(vec)
Out[4]:
The size is one-quarter of the original array:
In [5]:
sizeof(vec)
Out[5]:
In [6]:
sizeof(ivec)
Out[6]:
You can allocate an IntArray object with given width, element type, and size:
In [7]:
# allocate a vector object
ivec = IntArray{4,UInt8}(4)
Out[7]:
In [8]:
# allocate a matrix object
imat = IntArray{9,UInt16}(4, 5)
Out[8]:
The elements of the allocated matrix are uninitialized, so you should fill them if necessary:
In [9]:
fill!(imat, 0)
Out[9]:
You can also use the IntVector and IntMatrix type aliases to construct a one-/two-dimensional array:
In [10]:
ivec = IntVector{2,UInt8}(6)
Out[10]:
In [11]:
imat = IntMatrix{2,UInt8}(3, 4)
Out[11]:
The IntArray{w,T,n} type inherits from the AbstractArray{T,n} type.
That means an IntArray object behaves like a common array in many ways.
Let's create an IntVector object with 2-bit encoding and see available operations on it.
In [12]:
ivec = IntVector{2}([0x00, 0x01, 0x02, 0x03])
Out[12]:
IntArray supports random access like normal arrays:
In [13]:
ivec[2]
Out[13]:
In [14]:
ivec[2] = 0x03
ivec
Out[14]:
In [15]:
ivec[2] = 1
ivec
Out[15]:
Please keep in mind that elements are truncated to w bits without any warnings:
In [16]:
# 0x05 cannot be encoded in 2 bits!
ivec[1] = 0x05
# in this case, 0x05 is truncated to 0x01 because 0x05 && 0b11 = 0x01
ivec
Out[16]:
IntVector behaves like a Vector:
In [17]:
ivec = IntVector{2}([0x00])
Out[17]:
In [18]:
push!(ivec, 0x01)
Out[18]:
In [19]:
append!(ivec, [0x02, 0x03, 0x00])
Out[19]:
In [20]:
pop!(ivec)
Out[20]:
In [21]:
reverse!(ivec)
Out[21]:
In [22]:
minimum(ivec), maximum(ivec)
Out[22]:
In [23]:
extrema(ivec)
Out[23]:
In [24]:
findnext(ivec, 2)
Out[24]:
In [25]:
findmin(ivec)
Out[25]:
Packing and unpacking integers require several CPU clocks. Therefore, in general, random access operations over IntArray objects are slower:
In [42]:
vec = rand(0x00:0x0f, 100000)
ivec = IntVector{4}(vec);
In [43]:
sort(vec)
@time sort(vec);
In [44]:
sort(ivec);
@time sort(ivec);
In [45]:
vec = rand(0x00:0x03, 10000000)
ivec = IntVector{2}(vec);
In [46]:
sort(vec)
@time sort(vec);
In [47]:
sort(ivec)
@time sort(ivec);
But this performance gap may diminish when a specialized algorithm can be applied. For example, radix sort runs faster when the bit width is small enough:
In [48]:
radixsort(ivec)
@time radixsort(ivec);
In [49]:
versioninfo()