FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Array" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Array
Linear data structures

Array
Deque
Linked list
Queue
Stack
Example of an approximately 40,000 probe spotted oligo microarray with enlarged inset to show detail. ... A binary tree, a simple type of branching linked data structure. ... In computer science, a deque (short for double-ended queue) is a data structure for which elements can be added to or removed from the front or back. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...

In computer science an array is a data structure consisting of a group of elements that are accessed by indexing. In most programming languages each element has the same data type and the array occupies a contiguous area of storage. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A binary tree, a simple type of branching linked data structure. ... In mathematics, an element (also called a member) is an object contained in a set (or more generally a class). ... Index has two distinct meanings in computer science: an integer which identifies an array element, and a data structure which enables sublinear-time lookup. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... In programming languages a data type defines a set of values and the allowable operations on those values[1]. For example, in the Java programming language, the int type represents the set of 32-bit integers ranging in value from -2,147,483,648 to 2,147,483,647, and... The terms storage (U.K.) or memory (U.S.) refer to the parts of a digital computer that retain physical state (data) for some interval of time, possibly even after electrical power to the computer is turned off. ...


Most programming languages have a built-in array data type, although what is called an array in the language documentation is sometimes really an associative array. Conversely, the contiguous storage kind of array discussed here may alternatively be called a vector,[1] list,[2] or table.[3] An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... Tables is a generic name given to a class of board games similar to Backgammon. ...


Some programming languages support array programming (e.g., APL, newer versions of Fortran) which generalises operations and functions to work transparently over arrays as they do with scalars, instead of requiring looping over array members. Array programming languages (also known as vector or multidimensional languages) generalize operations on scalars to apply transparently to vectors, matrices, and higher dimensional arrays. ... APL (for A Programming Language) is an array programming language based on a notation invented in 1957 by Kenneth E. Iverson while at Harvard University. ... Fortran (previously FORTRAN[1]) is a general-purpose[2], procedural,[3] imperative programming language that is especially suited to numeric computation and scientific computing. ...


Multi-dimensional arrays are accessed using more than one index: one for each dimension.


Arrays can be classified as fixed-sized arrays (sometimes known as static arrays) whose size cannot change once their storage has been allocated, or dynamic arrays, which can be resized. A dynamic array, growable array, resizable array, dynamic table, or array list is a data structure, an array which is automatically expanded to accommodate new objects if filled beyond its current size. ...

Contents

Properties

Fixed-size arrays permit efficient (constant time, O(1)) random access. They are compact data structures, having a constant memory overhead. And, on CPUs which support caches, sequential iteration over an array has good locality of reference because its elements occupy contiguous memory locations. However, when an array is randomly accessed, for example when probing a hash table, locality of reference may be lost. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... Random access compared to sequential access. ... In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to be utilized or expended to enable a particular goal. ... CPU can stand for: in computing: Central processing unit in journalism: Commonwealth Press Union in law enforcement: Crime prevention unit in software: Critical patch update, a type of software patch distributed by Oracle Corporation in Macleans College is often known as Ash Lim. ... For other uses, see cache (disambiguation). ... It has been suggested that this article or section be merged with Memory locality. ... Random access compared to sequential access. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...


Applications

Because of their performance characteristics, arrays are used to implement other data structures, such as heaps, hash tables, deques, queues, stacks, strings, and VLists. Example of a complete binary max heap In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computer science, a deque (short for double-ended queue) is a data structure for which elements can be added to or removed from the front or back. ... A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... If you are seeking the town in the Netherlands, see Vlist. ...


Some algorithms store a variable number of elements in part of a fixed-size array, which is equivalent to using dynamic array with a fixed capacity. See dynamic array for details. A dynamic array, growable array, resizable array, dynamic table, or array list is a data structure, an array which is automatically expanded to accommodate new objects if filled beyond its current size. ... A dynamic array, growable array, resizable array, dynamic table, or array list is a data structure, an array which is automatically expanded to accommodate new objects if filled beyond its current size. ...


Associative arrays provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. Specialized associative arrays with integer keys include Patricia tries and Judy arrays. An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... In computer science, a Patricia trie (also known as a radix tree) is a simple form of compressed trie which merges single child nodes with their parents. ... In computer science and software engineering, a Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. ...


Indexing

The valid index values of each dimension of an array are a bounded set of integers. Programming environments that check indexes for validity are said to perform bounds checking. Index has two distinct meanings in computer science: an integer which identifies an array element, and a data structure which enables sublinear-time lookup. ... In computer programming, bounds checking is the name given to any method of detecting whether or not an index given lies within the limits of an array. ...


Index of the first element

The index of the first element (sometimes called the "origin") varies by language. There are three main implementations: zero-based, one-based, and n-based arrays, for which the first element has an index of zero, one, or a programmer-specified value. The zero-based array is more natural in the root machine language and was popularized by the C programming language, in which the abstraction of array is very weak, and an index n of a one-dimensional array is simply the offset of the element accessed from the address of the first (or "zeroth") element (scaled by the size of the element). One-based arrays are based on traditional mathematics notation for matrices and most, but not all, mathematical sequences. n-based is made available so the programmer is free to choose the lower bound, which may even be negative, which is most naturally suited for the problem at hand. A system of codes directly understandable by a computers CPU is termed this CPUs native or machine language. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... The word matrix (plural matrices) has several meanings. ... For other senses of this word, see sequence (disambiguation). ...


The Comparison of programming languages (array), indicates the base index used by various languages. Size can be chosen on initialization/declaration after which it is fixed. ...


Supporters of zero-based indexing sometimes criticize one-based and n-based arrays for being slower. Often this criticism is mistaken when one-based or n-based array accesses are optimized with common subexpression elimination (for single dimensioned arrays) and/or with well-defined dope vectors (for multi-dimensioned arrays). However, in multidimensional arrays where the net offset into linear memory is computed from all of the indices, zero-based indexing is more natural, simpler, and faster. Edsger W. Dijkstra expressed an opinion in this debate: Why numbering should start at zero. In compiler theory, common subexpression elimination (CSE) is the practice of finding repeated redundant expression evaluations, and replacing them with a single computation assigned to a temporary variable. ... In computer programming, a dope vector is a data structure used to hold information about an array, especially its memory layout. ... Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ...


The 0-based/1-based debate is not limited to just programming languages. For example, the ground-floor of a building is elevator button "0" in France, but elevator button "1" in the USA.


Indexing Methods

When the Array is implemented as continuous storage, the index-based access, e.g. to element n, is simply done (for zero-based indexing) by using the address of the first element and adding n · sizeof(one element). So this is a Θ(1) operation.


But there are cases, where continuous storage might be a bad idea:

  • Insertion and deletion should also be a common operation, but continuous storage requires Θ(n) time for them. Here a balanced tree can be used, giving Θ(log n) for both index access and inserting/deleting. [4][5] For example the TextBuffer of GTK+ is implemented on top of a B-Tree, which has lower overhead compared to a binary tree like the AVL Tree.
  • Allowing non-integer indices, which is also called an Associative array. PHP Arrays are indexed by integers, but can also be accessed by string keys.

GTK+, or the GIMP Toolkit, is one of the two most popular widget toolkits for the X Window System for creating graphical user interfaces. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ... An example of an unbalanced non-AVL tree In computer science, an AVL tree is a self-balancing binary search tree, and the first such data structure to be invented. ... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... For other uses, see PHP (disambiguation). ...

Multi-dimensional arrays

Ordinary arrays are indexed by a single integer. Also useful, particularly in numerical and graphics applications, is the concept of a multi-dimensional array, in which we index into the array using an ordered list of integers, such as in a[3,1,5]. The number of integers in the list used to index into the multi-dimensional array is always the same and is referred to as the array's dimensionality, and the bounds on each of these are called the array's dimensions. An array with dimensionality k is often called k-dimensional. One-dimensional arrays correspond to the simple arrays discussed thus far; two-dimensional arrays are a particularly common representation for matrices. In practice, the dimensionality of an array rarely exceeds three. Mapping a one-dimensional array into memory is obvious, since memory is logically itself a (very large) one-dimensional array. When we reach higher-dimensional arrays, however, the problem is no longer obvious. Suppose we want to represent this simple two-dimensional array: For the square matrix section, see square matrix. ...

mathbf{A} = begin{bmatrix} 1 & 2 & 3  4 & 5 & 6  7 & 8 & 9 end{bmatrix}.

It is most common to index this array using the RC-convention, where elements are referred in row, column fashion or A_{row,col},, such as:

A_{1,1}=1, A_{1,2}=2, ldots, A_{3,2}=8, A_{3,3}=9.,

Common ways to index into multi-dimensional arrays include:

  • Row-major order. Used most notably by statically-declared arrays in C. The elements of each row are stored in order.
1 2 3 4 5 6 7 8 9
  • Column-major order. Used most notably in Fortran. The elements of each column are stored in order.
1 4 7 2 5 8 3 6 9
  • Arrays of arrays. Multi-dimensional arrays are typically represented by one-dimensional arrays of references (Iliffe vectors) to other one-dimensional arrays. The subarrays can be either the rows or columns.

A two-dimensional array stored as a one-dimensional array of one-dimensional arrays. Row-major order describes a way to store a multidimensional array in linear memory. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Fortran (previously FORTRAN[1]) is a general-purpose[2], procedural,[3] imperative programming language that is especially suited to numeric computation and scientific computing. ... This article is about a general notion of reference in computing. ... In computer programming, an Iliffe vector is a data structure used to implement multi-dimensional arrays. ... Image File history File links Array_of_array_storage. ...


The first two forms are more compact and have potentially better locality of reference, but are also more limiting; the arrays must be rectangular, meaning that no row can contain more elements than any other. Arrays of arrays, on the other hand, allow the creation of ragged arrays, also called jagged arrays, in which the valid range of one index depends on the value of another, or in this case, simply that different rows can be different sizes. Arrays of arrays are also of value in programming languages that only supply one-dimensional arrays as primitives.


In many applications, such as numerical applications working with matrices, we iterate over rectangular two-dimensional arrays in predictable ways. For example, computing an element of the matrix product AB involves iterating over a row of A and a column of B simultaneously. In mapping the individual array indexes into memory, we wish to exploit locality of reference as much as we can. A compiler can sometimes automatically choose the layout for an array so that sequentially accessed elements are stored sequentially in memory; in our example, it might choose row-major order for A, and column-major order for B. Even more exotic orderings can be used, for example if we iterate over the main diagonal of a matrix. For the square matrix section, see square matrix. ... In linear algebra, the main diagonal of a square matrix is the diagonal which runs from the top left corner to the bottom right corner. ...


References

  1. ^ C calls arrays `vectors'. The term is also common whenever the array is regarded as a mathematical vector.
  2. ^ Tcl 8 lists are implemented using C vectors.
  3. ^ This was the practice in some older languages, e.g. COBOL: Using Tables in COBOL
  4. ^ NIST's Dictionary of Algorithms and Data Structures: Array
  5. ^ Counted B-Tree

C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... Look up vector in Wiktionary, the free dictionary. ... Tcl (originally from Tool Command Language, but nonetheless conventionally rendered as Tcl rather than TCL; and pronounced tickle) is a scripting language created by John Ousterhout. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... COBOL (pronounced //) is a Third-generation programming language, and one of the oldest programming languages still in active use. ...

See also

Look up array in
Wiktionary, the free dictionary.

Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 151 languages. ... In computer programming, array slicing is an operation that extracts certain elements from an array and packages them as another array, possibly with different number of indices (or dimensions) and different index ranges. ... In object-oriented programming, a collection class is any class that is capable of storing other objects. ... Size can be chosen on initialization/declaration after which it is fixed. ... A parallel array is a simple data structure for representing arrays of records. ... In computer science, the set is a collection of certain values without any particular order. ... A sparse array in computing is an array where most of the elements have the same value (called the default value -- usually 0) and only a few elements have a non-default value. ...

External links

  • NIST's Dictionary of Algorithms and Data Structures: Array

  Results from FactBites:
 
Array (Flex™ 2 Language Reference) (5280 words)
var phoneString:String = "(888) 867-5309"; var specialChars:Array = new Array("(", ")", "-", " "); var myStr:String = phoneString; var ln:uint = specialChars.length; for(var i:uint; i < ln; i++) { myStr = myStr.split(specialChars[i]).join(""); } var phoneNumber:Number = new Number(myStr); trace(phoneString); // (888) 867-5309 trace(phoneNumber); // 8888675309
var vegetables:Array = new Array(); vegetables.push(1); vegetables.push(2); vegetables.push(3); vegetables.push(4); vegetables.push(5); var vegnums:String = vegetables.toString(); trace(vegnums+",6"); // 1,2,3,4,5,6
var names:Array = new Array(); names.push("Bill"); names.push("Jeff"); trace(names); // Bill,Jeff names.unshift("Alfred"); names.unshift("Kyle"); trace(names); // Kyle,Alfred,Bill,Jeff
Array - Wikipedia, the free encyclopedia (1672 words)
Arrays permit efficient (constant-time, O(1)) random access but not efficient insertion and deletion of elements (which are O(n), where n is the size of the array).
Dynamic arrays or growable arrays are arrays which automatically perform this resizing as late as possible, when the programmer attempts to add an element to the end of the array and there is no more space.
The zero-based array was made popular by the C programming language, in which the abstraction of array is very weak, and an index n of an array is simply the address of the first element offset by n units.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m