Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
In computer science, a record is an instance of a product of primitive data types called a tuple. In C it is the compound data in a struct. Records are among the simplest data structures. A record is a value that contains other values, typically in fixed number and sequence and typically indexed...
. It keeps a separate, homogeneous array for each field of the record, each having the same number of elements. Then, objects located at the same index in each array are implicitly the fields of a single record. Pointers from one object to another are replaced by array indices. This contrasts with the normal approach of storing all fields of each record together in memory. For example, one might declare an array of 100 names, each a string, and 100 ages, each an integer, associating each name with the age that has the same index.
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
(using a hash of arrays to hold references to each array):
my %data = (
first_name => ['Joe', 'Bob', 'Frank', 'Hans' ],
last_name => ['Smith','Seger','Sinatra','Schultze'],
height_in_cm => [169, 158, 201, 199 ]);
for $i (0..$#{$data{first_name}}) {
printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}
for i in xrange(len(firstName)):
print "Name: %s %s" % (firstName[i], lastName[i])
print "Height in CM: %s" % heightInCM[i]
Parallel arrays have a number of practical advantages over the normal approach:
They can be used in languages which support only arrays of primitive types and not of records (or perhaps don't support records at all).
Parallel arrays are simple to understand and use, and are often used where declaring a record is more trouble than it's worth.
They can save a substantial amount of space in some cases by avoiding alignment issues. For example, one of the fields of the record can be a single bit, and its array would only need to reserve one bit for each record, whereas in the normal approach many more bits would "pad" the field so that it consumes an entire byte or a word.
If the number of items is small, array indices can occupy significantly less space than full pointers, particularly on architectures with large words.
Sequentially examining a single field of each record in the array is very fast on modern machines, since this amounts to a linear traversal of a single array, exhibiting ideal locality of reference
Locality of reference
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
and cache behavior.
However, parallel arrays also have several strong disadvantages, which serves to explain why they are not generally preferred:
They have significantly worse locality of reference when visiting the records sequentially and examining multiple fields of each record, which is the norm.
They obscure the relationship between fields of a single record.
They have little direct language support (the language and its syntax typically express no relationship between the arrays in the parallel array).
They are expensive to grow or shrink, since each of several arrays must be reallocated. Multi-level arrays can ameliorate this problem, but impacts performance due to the additional indirection needed to find the desired elements.
The bad locality of reference is the worst issue. However, a compromise can be made in some cases: if a structure can be divided into groups of fields that are generally accessed together, an array can be constructed for each group, and its elements are records containing only these subsets of the larger structure's fields. This is a valuable way of speeding up access to very large structures with many members, while keeping the portions of the structure tied together. An alternative to tying them together using array indexes is to use reference
Reference (computer science)
In computer science, a reference is a value that enables a program to indirectly access a particular data item, such as a variable or a record, in the computer's memory or in some other storage device. The reference is said to refer to the data item, and accessing those data is called...
s to tie the portions together, but this can be less efficient in time and space. Another alternative is to mock up a record structure in a single-dimensional array by declaring an array of n*m size and referring to the r-th field in record i as element as array(m*i+r). Some compiler optimization
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
A vector processor, or array processor, is a central processing unit that implements an instruction set containing instructions that operate on one-dimensional arrays of data called vectors. This is in contrast to a scalar processor, whose instructions operate on single data items...
s, are able to perform this transformation automatically when arrays of structures are created in the program.
A column-oriented DBMS is a database management system that stores its content by column rather than by row. This has advantages for data warehouses and library catalogues where aggregates are computed over large numbers of similar data items....
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
