Invisible <voi### [at] devnull> wrote:
> First of all, in any of the above languages, if you want to store 
> several items of data, an array is usually the first data structure you 
> reach for. It's simple, it's built-in, it's always there, it's 
> moderately efficient, and it's "good enough" to start with.

  The advantages of an array are:

1) It's the most memory-efficient data container possible. Not one single
bit of ancillary data is used per element. All elements are packed in
memory as tightly as possible (well, at least if the size of the element
is a multiple of the natural (half-)word size of the target architecture,
or the element has the size of one byte).

  You can pack certain type of elements even more efficiently than that
when using special data containers, for example radix trees, but even
then you'll have to put the container data inside an array if you want
to beat the memory usage of the "raw" array. In other words, you will
still be using an array (rather than some other data structure), even if
interpreting the contents of the array is a bit more complicated.

2) Accessing an element of the array is fast, as you have random access.
You can access any array in O(1), and moreover the constant factor
involved is very small (in the order of 1 clock cycle if the element
happens to be in the fastest cache; and even if there's a cache miss,
it will still usually be faster than accessing elements in other non-array
data containers).

3) Elements in an array are in contiguous memory locations. This fact is
often dismissed in higher-level languages, but sometimes used to one's
advantage in lower-level languages, sometimes for great speedups.

  The reason why this property can sometimes be used for speed is that
small array elements can be handled in bigger bunches (usually word-sized)
because they are all in contiguous memory locations. For example doing
certain operations to a byte string can be done 4 or 8 bytes at a time
(getting almost that much speedup) with low-level tricks.

  There are many algorithms which are very efficient and fast to perform
on arrays, while inefficient or difficult to do for other types of data
containers (such as linked lists).

  Of course arrays have their disadvantages, which is the reason why other
types of data containers exist in the first place. For example, removing one
element from the middle of the array is a slow operation, while for example
for a linked list it's very fast (assuming you have a handle to the element
to be removed). Adding elements to an array while constantly keeping it sorted
is inefficient, while with other data containers (eg. a balanced binary tree)
it's efficient. Arrays are not very dynamic, and trying to make them dynamic
(while still maintaining efficiency) usually causes overallocation and/or
memory fragmentation.

> One nice touch is that an unboxed array of Bool actually uses 1 bit per 
> element. The library automatically handles all the bit twiddling 
> operations required to pack 8 Bools into one byte, and unpack them again 
> later. (I wonder if the C++ STL can do that?)

  std::vector<bool> uses one bit per element.

  OTOH this actually causes more trouble than it's worth, as it makes
std::vector behave in certain cases rather differently when the element
type is bool compared to any other element type. This is a common complaint.

  The suggested solution is to use a separate, efficient data container for
bit-sized booleans. boost::dynamic_bitset is such a container, and it has
often been suggested to be included in the next C++ standard, and the
std::vector<bool> converted to a 1-byte-per-element container.

  boost::dynamic_bitset is an incredibly efficient data container for
individual bits. For example it can count the number of set bits in the
entire container at something like 0.5 clock cycles per bit in my computer.

-- 
                                                          - Warp

Post a reply to this message