Topic: arrays

topics > computer science > data > Group: data structures


access to components of a data object
collection class
hash table and hash functions
index sequence for array access
object slice
object transformation language
range checking
set-oriented languages
sparse arrays
type parameter
variables for array bounds


Arrays are the most used structures because of their efficient implementation by machine memory. Their index sets are integer sub-ranges defining a parameterized access function. The components of an array belong to one type, usually a basic language type such as reals or integers. Array components are usually accessed by a fixed constant or index variable. In APL, the universal data type is an array of elements with all operations generalized to arrays. This means that a program specified on data elements is also defined for arrays of any dimension. (cbb 5/80)

Mills suggests the avoidance of arrays because of many dependencies. (cbb 1/90)

Subtopic: homogeneous arrays with dynamic selector up

Quote: a Modula-3 array consists of elements of the same size and type, and an index by values of an ordinal type [»cardL_1991]
Quote: arrays are homogeneous with dynamic selectors; records are heterogeneous with static selectors [»maclBJ_1987, OK]
Quote: Oberon abandoned index types for arrays; indices start at 0, declarations specify a length [»wirtN7_1988]
Quote: if A is an array in a cell computer, the name A(i) must be moved whenever cell i is changed [»hehnEC_1977a]

Subtopic: array-oriented language up

Quote: J's primitives are one or two letters, e.g., $y for shape of y, #y for count of y, x,:y append itemized x to itemized y, f^:n y apply f n times to y [»huiRKW8_1991]
Quote: the APL dialect J has 81 operators; e.g., rotate is |., gradeup is /:; display ten random integers is ]y=. ?10$100 [»mcinDB8_1991]
Quote: APL has two function modifiers (reduction and cross product), but they can only combine with primitives [»backJ_1972]
Quote: APL uses a workspace that holds functions and data; a library holds a collection of workspaces [»falkAD8_1978]
Quote: APL's arrays impose a uniform type; e.g., the type of A and B in A+B is array of real or array of integer; not true in LISP [»atkiMP6_1987]
Quote: parallel arrays are Accelerator's fundamental data type; homogeneous, no index operator, no side effects; the result of any operation is a new array [»tardD10_2006]

Subtopic: array as parameterized data up

Quote: is class (i.e., type + extent) a parameterized data type like 'array of int'? [»buneP5_1986]
Quote: a parameterized function is an abstraction of an array; with no parameters, abstraction of value [»hehnEC_1977a, OK]
QuoteRef: kiebRB9_1973 ;;2.3 "Arrays of scalar variables are formed by using type functions with arguments of type i (%integer)." e.g., ->(->real) is a one dim.array and iXi->(->real) is a two dim. array

Subtopic: array as a value up

Quote: in data flow languages, an array is a value; changing an element creates a new, slightly different array [»ackeWB_1979]
Quote: think of an array is an immutable string of integers; no different than an integer as a string of bits [»ackeWB_1979]
Quote: can think of an array as a stream that is processed one element at a time; avoids the array bottleneck [»ackeWB_1979]

Subtopic: array as result up

Quote: return a zero-length array instead of a null; nulls require special code [»blocJ_2001]

Subtopic: array as container class up

Quote: a container class holds objects of another type (e.g., lists, arrays, sets); the type is irrelevant to the definer and crucial to the user [»stroB_1991]

Subtopic: array as pointer arithmetic up

Quote: in C++, pointer arithmetic is defined only within an array; the difference of two pointers is the number of array elements between them [»stroB_1991]
Quote: an array in BCPL is a pointer to storage for the array [»ritcDM7_1978c]
Quote: in BCPL, the ith member of an array is *(Array+i) where * means indirection; also called Array[i] or i[Array] [»ritcDM7_1978c]
Quote: in C, an array refers to the first element of the array, but a reference to an array is automatically converted to a pointer to the array [»ritcDM7_1978c]
Quote: in C, an array argument is converted to a pointer; arrays are effectively passed by reference [»ritcDM7_1978c]

Subtopic: bit array up

Quote: two bits of meta-data per heap data; delimiter bit and value bit gives size, free and allocated [»kharM10_2006]

Subtopic: multi-dimensional array up

QuoteRef: rtl2 ;;multi-dimensional arrays by an array of pointers

Subtopic: arraylet up

Quote: Metronome garbage collector uses arrays of arraylets; the arrayoid contains the object header, arraylet pointers, and optionally. the last arraylet [»bacoDF6_2005]
Quote: keep arraylets in the heap and arrayoid in the garbage collector's nursery; allows large memory objects in the nursery without the space cost [»bacoDF6_2005]
Quote: use 2 KB arraylets instead of large memory objects; efficient access and garbage collection; 8 MB max size using an allocation page as the index [»bacoDF1_2003]

Subtopic: dynamic array up

Quote: CLU arrays do not contain uninitialized elements; they grow and shrink on either end with bounds checking as needed [»liskB_1996]
Quote: HAT structure is a two level array; all blocks of a power of two; only top block and last bottom block may be partial [»demaE7_2001]
Quote: HAT structure can grow and shrink at the beginning; for double-ended queues and deques [»demaE7_2001]
Quote: avoid resizing of HAT structure by doubling size of low-level blocks; 2 sqrt n wasted space; optimal [»demaE7_2001]

Subtopic: associative array up

Quote: data structures by a set of ordered pairs: index/element [»hehnEC_1977]
Quote: script programmers used associative arrays while non-script programmers used arrays and 10-ary trees
Quote: ABC restricts data types to numbers, text, tuples, lists, and tables; lists and tables of the same type [»pembS1_1987]
QuoteRef: cbb_1973 ;;[reading (QuoteRef: dahlOJ_1972) array is a form of a record

Subtopic: function dispatch array up

Quote: use process groups for procedural message-passing systems; labeled by process name and numeric index

Subtopic: object array up

QuoteRef: buxtJN_1962 ;;195 classes eg truck.1 truck.2 with class subscript and carries a subscript array eg truck.1(make)

Subtopic: persistent array up

Quote: g|N=2,4,6,0 and k|N=1(1)10 create tables on the drum [»laniJH1_1954]

Subtopic: open array with variable bounds up

Quote: Modula-3 has fixed and open arrays; the size of an open array is determined when allocated or bound [»cardL_1991]
Quote: an open array is only used for formal parameters, the referent of a reference type, the element type of another open array, or the type of a literal array
Quote: PASCAL should allow variable array bounds; e.g., ALGOL or FORTRAN [»knobB4_1976]

Subtopic: array bounds up

Quote: in Java, array bounds and object types are absolute; you can not lie about the identity of an object [»allmE7_2004]
Quote: CLU arrays do not contain uninitialized elements; they grow and shrink on either end with bounds checking as needed [»liskB_1996]
Quote: efficient array bound checking across procedure calls; reports name and dimension of erroneous array; uses source-to-source Fortran compiler and convex array regions [»nguyTV5_2005]

Subtopic: array assignment up

Quote: arrays are assignable if they have the same element type and shape; an open array requires a runtime shape check [»cardL_1991]
Quote: arrays may be assigned to arrays of different index types or to overlapping subarrays

Subtopic: array operator up

Quote: AQuery variables and operators refer to arrays (a column); e.g., price - prev(price) is daily-change-in-price [»lernA9_2003]
Quote: convert matrix addition into a loop over pair-wise additions [»gallBA4_1967, OK]
QuoteRef: hogbD10_1971 ;;Omnitab is APL like, lots of mathematical and statistical routines
QuoteRef: hogbD10_1971 ;;19 index list by 1***8 (i.e. 1,2,3...8). reference to box by *row,col*

Subtopic: array indexing up

Quote: type checking can catch inappropriate indexing of arrays; like units; e.g., ArrayIndex h, ColumnIndex i, and RowIndex j [»weihK9_2002]
Quote: locality-aware matrix indexing by partitioning the index into column bits and row bits; problem of software and hardware support [»adamMD5_2006]
Quote: x| is a superscript variable (i.e., array); x|^6 is the sixth element while x|n is the n'th element [»laniJH1_1954]

Subtopic: array access function up

Quote: Smalltalk indexed variables accessed by at: and at:put: selectors [»xlrg8_1981]

Subtopic: array overlap up

Quote: Fortran guarantees that multiple array arguments do not overlap; allows spectacular savings on vector hardware [»stroB_1994]

Subtopic: avoiding arrays up

Quote: avoid arrays because they create many dependencies; use sets, stacks, and queues instead [»millHD2_1986]
Quote: wrote 20 thousand line program without arrays; used verification instead of unit testing; no errors after installation [»millHD2_1986]

Related Topics up

Group: sequences   (7 topics, 97 quotes)
Group: sets   (7 topics, 148 quotes)

Topic: access to components of a data object (4 items)
Topic: collection class (11 items)
Topic: hash table and hash functions (41 items)
Topic: index sequence for array access (16 items)
Topic: lists (8 items)
Topic: object slice (3 items)
Topic: object transformation language (10 items)
Topic: range checking (20 items)
Topic: set-oriented languages (20 items)
Topic: sparse arrays (6 items)
Topic: type parameter (34 items)
Topic: variables for array bounds
(7 items)

Updated barber 6/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.