Array: Difference between revisions
m
→Indexing
Puppydrum64 (talk | contribs) m (→Indexing) |
|||
| (59 intermediate revisions by 6 users not shown) | |||
Line 40:
==Examples==
* [[letter frequency]]
===[[Assembly]]===
An array is simply a sequence of values stored in consecutive memory locations. Its beginning is typically defined with some sort of label that points to the address where that array is stored. Whether an array is mutable or immutable depends on the hardware; in older assembly languages, an array is only typically immutable if it's stored in ROM. Home computer software that is stored on disk or tape can define an array at compile time that can be mutable; ROM cartridge programs cannot. The syntax is the same for both, however. ROM cartridge programs will need to construct their array in ROM, copy it to RAM, and alter the copy.
'''Example using [[6502 Assembly]]:'''
<lang 6502asm>ArrayRAM equ $00
;the beginning of an array, stored in zero page RAM
ArrayROM: db 0,5,10,15,20,25,30,35,40,45,50
;on Commodore 64 (for example) these values can be modified at runtime, but on the NES they are read-only.</lang>
====Indexing====
Almost all assembly languages have a method of loading from a memory address offset by some sort of variable amount. That offset is the index into the array. Depending on the size of each element that index is multiplied by the number of bytes each element takes up. What constitutes an "element," "row," or "column" of the array is entirely decided by the programmer. Arrays in assembly are always zero-indexed.
'''Example using [[68000 Assembly]]:'''
<lang 68000devpac>LEA myArray,A0 ;loading a labeled array name like this loads the address of the zeroth element
MOVE.W #4*5*1,D1 ;five elements per row, so to get the 4th row we multiply the row number by the elements per row,
;times the number of bytes per element
LEA (A0,D1),A0 ;offset A0 by the row number
LEA (2*1,A0),A0 ;column number times the number of bytes per element (the times 1s aren't needed but it's here for clarity)
MOVE.B (A0),D0 ;load decimal 52 into D0
myArray:
DC.B 10,11,12,13,14 ;typing the array in rows like this is only for the viewer's convenience - it means nothing to the CPU.
DC.B 20,21,22,23,24 ;all 25 entries could have been on one line in the same order and it wouldn't change how they are stored.
DC.B 30,31,32,33,34
DC.B 40,41,42,43,44
DC.B 50,51,52,53,54
myArray_End: ;this label exists to mark the end of the array.
</lang>
It is <b>much</b> easier to work with arrays in assembly if all rows are the same length. The best way to deal with a ragged or jagged array, such as an array of strings of different lengths, is to store ''pointers to the array entries rather than the intended entries themselves.'' This equalizes the size of all the elements of the array which makes it much easier to index. Another way to handle such arrays is with padding, by adding extra null bytes to the ends until all rows are the same length, but for many data types it's better to construct an array of pointers.
<lang 68000devpac>main:
;goal: Print "Orange" to stdout
LEA Strings,A0
LEA (4,A0),A0 ;this is NOT a dereference operation, it merely adds 4 to A0.
MOVE.L (A0),A0 ;now we dereference the pointer so that we have the address of "Orange" in A0.
;If we did MOVE.B (A0),D0 now, we'd load the "O" in "Orange" into D0.
JSR PrintString ;or whatever you use to write to stdout
RTS ;return
Strings:
DC.L AppleAddress
DC.L OrangeAddress
DC.L GrapeAddress
AppleAddress:
DC.B "Apple",0
even
OrangeAddress:
DC.B "Orange",0
even
GrapeAddress:
DC.B "Grape",0
even</lang>
In assembly, there is '''nothing''' stopping your program from indexing an array out of bounds! The computer doesn't have an understanding of where your array "ends," so asking it to return (for example) the 500th element of an array with only 25 elements is perfectly legal. This typically won't happen for arrays that aren't indexed based on user input, but be careful nonetheless. Indexing an array out of bounds and trying to read from it can cause segmentation faults on more modern machines, which is the operating system's way of preventing your code from reading memory that is outside of the program that is trying to index the array. Older CPUs don't have this sort of protection, and indexing out of bounds will read whatever is stored in memory at that location, which is why it falls into the realm of undefined behavior- the result entirely depends on how the code in your program is arranged.
====Iteration====
Iteration over the elements of an array is fairly straightforward.
'''Example using [[68000 Assembly]]:'''
<lang 68000devpac>LEA myArray,A0
loop:
MOVE.B (A0)+,D0
; As is, this example code will inevitably index out of bounds.
; In practice there will be some way to end the loop, typically a byte count or a null terminator.
JMP loop</lang>
'''Example using [[z80 Assembly]]:'''
<lang z80>ld hl,myArray ;load the address of myArray into hl
ld de,userRam ;load the address of work RAM into de
ld bc,myArrayEnd-myArray ;assembler directive that auto-calculates the array size using labels placed at the beginning and end.
ldir ;copy the entire contents of the array to work RAM</lang>
====Skip-Counting====
Skipping elements can be easily done with a "dummy read," whereby an auto-incrementing/decrementing addressing mode is used solely for updating the pointer, or by incrementing/decrementing a loop counter multiple times per loop.
'''Example using [[8086 Assembly]]:'''
<lang asm>iterate:
movsb ;store [ds:si] into [es:di], increment both pointers, and decrement cx.
lodsb ;dummy read to increment the pointer and decrement cx. The value loaded into AL gets discarded.
inc di ;increment destination index
jcxz exitloop ;exit loop if cx equals zero.
jmp iterate</lang>
Implementation of a reverse array slice such as <code>a[100:0:-2]</code> example for [[Python]] is much more difficult. First of all, computers cannot implicitly understand the concept of the "end" of an array. The start of an array is easy for a computer to grasp, it is simply a pointer to its first element. However, encoding an array's end point requires some form of metadata, such as a null terminator or an additional variable representing the array's maximum size. High-level languages typically handle this automatically.
====Element Access====
Access of an individual element of an array depends on the language.
<lang asm>;6502 Assembly
lda $2000,x ;load the xth element of the array beginning at memory address $2000
lda $3022,y ;load the yth element of the array beginning at memory address $3022
lda ($20),y ;load the yth element of the array whose pointer is stored at consecutive memory addresses $0020 and $0021
;68000 Assembly
move.b (4,A0,D1),D0 ;load into D0 the (4+D1.W)th element of the array whose beginning address is stored in A0.
;8086 Assembly
mov ax,[bx+di] ;load the BXth element of the array whose beginning is stored in DI, into AX.
;alternatively, load the DIth element of the array whose beginning is stored in BX, into AX.
;ARM Assembly
ldr r0,[r1,#4] ;load the 1st (zero-indexed) element of the array whose pointer to its 0th element is stored in r1, into r0.</lang>
====Encoding an Array's End====
'''Null Terminator'''
This method is most commonly used with strings. An ASCII value that is not associated with any keyboard key, typically 0, is placed at the end of a string. In a typical PrintString assembly routine, the routine is given a pointer to the 0th entry of the string as its only parameter. The routine reads from the pointer, prints that letter, increments the pointer, and repeats until the terminator is read, at which point the routine ends. Without the terminator, the program would not know when to stop reading and eventually crash. A string variable in [[C]] will place a 0 at the end of a string without you having to define it yourself. This method works well for strings and other arrays where the terminator's value is not a possible value for actual data. On more general arrays where the entries represent non-ASCII data, this causes problems where you have a datum that just so happens to equal the terminator.
'''Example using [[8086 Assembly]]:'''
<lang asm>PrintString:
; input: [DS:SI] = string pointer
mov al,[ds:si]
jz Terminated ;we've reached the terminator
inc si
call PrintChar ;call to hardware-specific printing routine
jmp PrintString
Terminated:
ret
HelloText:
db "Hello World",0 ;a value in quotes is its ASCII equivalent, anything else is a numeric value.</lang>
In cases like this, high-level languages often implement <i>escape characters</i> which when encountered in a string, result in a branch to a section that reads the next character without checking if it's a terminator or other control code. Effectively this removes the special meaning of that character but only if an escape character is before it. This concept is often reversed to allow the programmer to easily implement ASCII control characters, such as <code>\n</code> for new line (in ASCII this is represented by a 13 followed by a 10, for carriage return + line feed.) In this case the backslash signals to <code>printf()</code> that the next letter is associated with a particular ASCII control code. If the next character read is an "n" then ASCII 13 gets printed, followed by ASCII 10. After this, normal reading and printing resumes.
The example below shows a simple implementation of an escape character. The first instance of the null terminator gets printed as-is rather than used to end the routine.
'''Example using [[8086 Assembly]]:'''
<lang asm>PrintString:
; modified to use the \ as an escape character.
; input: [DS:SI] = string pointer
mov al,[ds:si]
inc si
cmp al,5Ch ;ascii for backslash, this is the escape character
;notice that the check for the escape character happens before the check for the terminator.
jz EscapeNextChar
cmp al,0h ;check the terminator
jz Terminated ;we've reached the terminator
call PrintChar ;call to hardware-specific printing routine
jmp PrintString
EscapeNextChar:
mov al,[ds:si] ;perform an additional read, except this read doesn't compare the fetched character to anything.
inc si
call PrintChar ;print that character as-is
jmp PrintString ;go back to the loop's beginning, skipping the terminator check entirely.
Terminated:
ret
HelloText:
db "Hello World\",0,13,10,0</lang>
'''End Label'''
This method is best for pre-defined arrays. Its usage was shown in earlier examples. Most assemblers can create a constant based off simple arithmetic using labels. A label's numeric value is the address it gets assembled to, decided at assemble time. Placing another label immediately after the end of an array will point it to the next byte after that array. The assembler subtracts the array's beginning label from this value to create a size constant that you don't have to manually adjust if you change the number of entries the array has.
This method can be used with array variables in conjunction with a null terminator and padding the distance between the terminator and the end of the range dedicated to storing array variables.
The major Achilles' heel of this method is that it only works on arrays that are of known length prior to assembling. In other words, you <b>cannot</b> make the array larger at runtime.
'''Example using [[68000 Assembly]]:'''
<lang 68000devpac>main:
LEA myArray,a0
MOVE.W #(MyArray_End-MyArray)-1,D7 ;the minus 1 corrects for DBRA, the subtraction of the two labels gives us the total byte count
;for .W or .L sized data you may need to right-shift D7 by 1 or 2 respectively, depending on what you're doing
loop:
MOVE.B (A0)+,D0
JSR PrintChar ;or whatever your implementation uses to write to stdout.
DBRA D7,loop
RTS ;exit program
MyArray:
DC.B "Hello World"
MyArray_End:
EVEN ;to get the correct byte count, you'll need the EVEN directive AFTER the end label.</lang>
'''Size Value'''
This method is best for arrays that are not pre-defined. Placed before the 0th element of the array is its maximum size. This value's location relative to the 0th element is always the same, regardless of how long the array actually is. As such, the pointer to the 0th element can be offset by a fixed negative amount to get the size. Alternatively, rather than storing the size of the array, a pointer to the last element can also be stored in front of the array. This lets you use pointer arithmetic to calculate the array's size, by subtracting the pointer of the 0th element from the last. This method is commonly used in picture file formats to mark where the picture data ends.
'''Example using [[68000 Assembly]]:'''
<lang 68000devpac>MyArray:
DC.W 3,5 ;three rows, five columns
;it would have also been sufficient to have "DC.W 15" instead of "DC.W 3,5".
DC.B 1,2,3,4,5
DC.B 6,7,8,9,10
DC.B 11,12,13,14,15</lang>
===[[ATS]]===
The array types built into ATS are an extremely complicated topic, and I shall mention only three points of interest.
# ATS wants to prevent you from going outside the bounds of the array; and it wants to do so without runtime checks. There are numerous ways to get around that "desire", but the capability for strictness is there.
# ATS wants to distinguish between the initialized and uninitialized parts of an array. Again, you can get around this "desire", but the capability to be rigorous is there.
# ATS arrays are basically C arrays. An array is a contiguous block of memory at a particular machine address, with no other runtime structure.
An array is represented by a pointer to the beginning of the memory block, as in C; but, furthermore, there is a ''view''. The view exists only as a typechecking entity; there is no runtime code associated with it. Suppose you have a fully initialized array, called '''a''', of fourteen '''int''' starting at address '''p'''. Then the view for the array may be written <lang ATS>@[int][14] @ p</lang> or equivalently as <lang ATS>array_v (int, p, 14)</lang>
To access an element of the array, that view needs to be available to the typechecker. Let us suppose the view is in fact available, and that there are operator overrides to use the square brackets as (in this case one-dimensional) array indices. Then a program that says <lang ATS>let val x = a[3] in a[4] := x end</lang> should be compilable, but one that says <lang ATS>let val x = a[20] in a[30] := x end</lang> will trigger a type error, due to the out-of-bounds indices.
Above we assumed '''a''' was fully initialized. Working with an array that is not fully initialized can become quite complex, and I shall mention only that the view for '''a''' before it is initialized would be <lang ATS>@[int?][14] @ p</lang> with a question mark. Fortunately there are routines in the prelude to fully initialize an array, for instance with a fill value such as zero or an empty string. There are also ways to fully deinitialize an array; to allocate an array in the heap, and to free one; to place an array in a stack frame; to make an array as a global variable.
The curious reader is encouraged to go to [http://www.ats-lang.org/ the ATS website] for more information.
===[[Fortran]]===
Arrays have been available from the start, for each of the allowed standard types of variables: integer, real, complex, logical, and character, and their different precisions. They can be indexed only with integer values, and definitely not with text strings as in say Snobol - though one could place a short text into a small CHARACTER variable that is equivalenced to an INTEGER variable and use that integer as in a "hash table" scheme, possibly to good effect. Indexing starts with one, and the size is fixed by the declaration at compile time, thus <lang Fortran> REAL A(66) !Declares an array, elements one to sixty-six.
A(3) = 1.1 !Assigns a value to the third element of A.
A(2) = 1.1
A(1) = 1.1</lang>
Higher dimensonality is available, with additional indices, thus given the declaration <code>INTEGER B(12,9)</code> individual elements would be accessed via the likes of <code>B(12,6) = 7</code> The type includes the dimensionality so array B can only be referenced with two indices and A only with one, although it is possible to specify something like <code>EQUIVALENCE (A,B)</code> which means that the two names refer to the same storage; the arrays are overlaid, even if of different types. With careful organisation and a good plan, this can have positive benefits. Multi-dimensional arrays are stored in "column-major" order, which is to say that for consecutive elements in storage, the ''left''most subscript varies most rapidly, so the order would be B(1,1), B(2,1), B(3,1), ... B(12,1), B(1,2), B(2,2), ''etc''. This is important when explicit indexing is not used, as when only its name is given in a READ, WRITE, or DATA statement: values are processed in storage order. Thus, element B(12,6) is the sixth element of row twelve, and the next along in storage would be B(1,7), which is not the seventh element of row twelve.
There is no "array subscript" type or usage, whereby, given <code>INTEGER XLAT(2)</code> element B(i,j) might be accessed via B(XLAT) where XLAT(1) = i and XLAT(2) = j. One must use <code>B(XLAT(1),XLAT(2))</code>
An array is identical to a function of integer arguments, so in <code>result = 3*F(X) + 7</code>, the F might be a function (of one parameter, an integer), or, it might be an array of one dimension - unlike with Pascal where F[...] is definitely an array, and F(...) is definitely a function. If a declaration such as <code>COMPLEX F(33)</code> to make it an array does ''not'' appear in that program unit, F will be taken as being a function, and the declaration <code>COMPLEX F</code> should appear since otherwise F would be REAL, not COMPLEX because undeclared names have a type of INTEGER if they start with the letters I, J, K, L, M, or N, otherwise REAL. This could be useful in debugging, where function F will provide checking and trace output, etc. as well as supplying the correct value. Alas, Fortran does not offer the ability to write "palindromic" functions so although <code>N = DAYNUM(Year,Month,Day)</code> is perfectly valid, <code>DAYNUM(Year,Month,Day) = N</code> is not possible with functions, though standard with arrays.
There is no associative access facility, of the form "what indices of A satisfy this condition", except almost: the <code>INDEX</code> function, which however is allowed only for CHARACTER variables. <code>L = INDEX("sometexts","text")</code> will return 5, the location of the first occasion (counting characters from one) where the second parameter exactly matches a portion of the first.
With F90 came the standardisation of many expanded facilities. Arrays can be defined with any lower bound instead of just one, as in <code>REAL A(1951:2017)</code>, and with it now possible to define compound types, there can be arrays of such aggregates. Type matching remains strict, however. There is also much greater flexibility in manipulating arrays without explicit looping. The
Similarly, F90 provides additional functions applicable to arrays; there is a <code>TRANSPOSE</code> function, and <code>MAXLOC(A)</code> returns the index of the (first encountered?) maximum value of the array, but there is still no extension for <code>INDEX</code> to other types. However,
Array sizes are no longer always fixed at compile time: on entry to a subroutine or function it can declare an array of a size determined by that occasion (as in Algol since the 1960s), and arrays can be explicitly allocated and de-allocated storage according to program logic. But, their type and dimensionality remain fixed.
Arrays remain resolutely rectilinear in shape. There is no direct facility to enable "triangular" arrays, still less ragged arrays. Triangular (and potentially other shape) arrays can be attained with a little effort: most simply, use a rectilinear array and waste the unused portion, otherwise, use a one-dimensional array and calculate offsets into it. But it may be possible to employ ''two'' triangular arrays, that can be fitted into a rectilinear array, possibly with special treatment of the diagonal elements; if so, one must be rigorous about keeping track of which has what subscripts! Escalating to three (or more) dimensions is quite possible, but, a calm and resolute mind is needed. As for ragged arrays, F90 facilities are required: consider <lang Fortran> TYPE AROW
REAL, ALLOCATABLE:: COL(:)
END TYPE AROW
TYPE(AROW) A(66)</lang>
This declares an array of sixty-six rows, where A(r,c) would be accessed via <code>A(r).COL(c)</code>, but first the code would have to execute <code>ALLOCATE(A(r).COL(first:last))</code> for every row that is to be used to acquire storage for it. Such usage will not be as swift as with plain arrays.
===[[Pascal]]===
Line 78 ⟶ 297:
</lang>
==
jq's data types are the same as JSON's data types, and thus jq's arrays can hold any combination of JSON entities. jq arrays are indexed beginning with 0, so ["hello"][0] evaluates to "hello".
Line 122 ⟶ 341:
reduce range(2;n+1) as $i (1; . * $i) # => n!</lang>
==={{header|
<lang ReScript>let arr1 = [4, 2, 8, 14, 3, 6, 22, 17]
let _ = Js.Array2.push(arr1, 5)
arr1[3] = 9
let isEven = x => mod(x, 2) == 0
let square = x => x * x
let arr2 = Js.Array2.filter(arr1, isEven)
let arr3 = Js.Array2.map(arr2, square)
let total = Js.Array2.reduce(arr3, \"+", 0)
Js.log2("total: ", Js.Int.toString(total))
let arr4 = Js.Array2.sortInPlaceWith(arr3, (a, b) => a - b)
let arr5 = Js.Array2.slice(arr4, ~start=2, ~end_=4)
Js.Array2.forEach(arr5, x => Js.log(x))
switch Js.Array2.find(arr1, x => x < 0) {
| Some(x) => Js.log2("found: ", x)
| None => Js.log("no negative element found")
}</lang>
{{out}}
<pre>$ bsc arr.res > arr.js
$ node arr.js
total: 604
36
64
no negative element found
</pre>
===[[REXX]]===
<lang rexx>/*REXX program snippets to show a variety (types) of "array" indexing. */
Line 201 ⟶ 455:
ht=14411; z='feet'; mt.rainier.12.9.4.6.44.z.12.7.1.0.6.2.2.2.1 = ht</lang>
===[[Smalltalk]]===
Smalltalk provides a rich set of collection classes in its base library, which is also standard (ANSI) among the different implementations.<br>The most used are:
* Array - fixed size, indexed by integer index, any kind of element
* ByteArray - an array of bytes, like Array, but only byte valued integers as elements
* String - an array of characters, like Array, but only characters as elements
* OrderedCollection - variable size, indexed by integer index, any kind of element
* Dictionary - variable size, indexed by arbitrary object as index, any kind of element
<br>
Array, ByteArray, String and all other collection types provide a common protocol which they inherit from their common superclass, <tt>Collection</tt>. ByteArray and String can be considered as Arrays with a more compact storage representation internally (but provide additional protocol eg. for case conversion or bit-array operations).
In Smalltalk, a character is exactly that: a character with a code point, not to be confused with a byte valued integer. Thus Strings and ByteArrays are different things (as opposed to eg. in the C language).
Array
<lang smalltalk>"an array literal (i.e. constant); this is immutable.
Array literals are constructed at compile time (thus the following costs effectively nothing)"
a1 := #(10 20 30 40).
"another array literal; notice the 5th element being another array"
a2 := #(1.0 20.0 'thirty' true #(5 5 5)).
"a new created array; all 10 elements are initially nil"
a4 := Array new:10.
"an new created array with 5 elements computed from expressions (at run time)"
a3 := { 10 . 20 . (a1 at:3) . 40 squared }.
"access by index (notice: in Smalltalk index starts at 1)"
a1 at:2. -> 20
a1 at:index put:100. -> error; immutable
a2 at:4 -> 1600
a2 at:4 put:99.999.
"asking for the size"
a1 size -> 4
"concatenating"
a1,a2 -> #(10 20 30 40 1.0 20.0 'thirty' true (5 5 5)
"enumerating, mapping etc."
a1 do:[:e | e printCR ] -> prints each element
a1 select:[:e | e > 20]. -> #(30 40)
a1 collect:[e | e squared]. -> #(100 400 900 1600)
a1 collect:#squared -> ditto
a1 inject:0 into:[:accu :el | el + accu]. -> 100
a1 conform:[:e | e even]. -> true
a1 count:[:e | e >= 20]. -> 3
.. there are many many more such functions..
"converting"
a1 asByteArray -> #[10 20 30]
#(200 300 400) asByteArray -> error raised
(#(65 66 67) collect:#asCharacter) asString -> 'ABC'
#(1 2 3 1 2 3 4) asSet. -> Set(1 2 3 4)
#(1 2 3 1 2 4) asBag. -> Bag(1*2 2*2 3 4)
#(1 2 3 1 2 4) asSortedCollection. -> SortedCollection(1 1 2 2 3 4)
"searching"
a1 includes:100 -> false
a1 occurrencesOf:10 -> 1
a1 indexOf:40. -> 4
a1 lastIndexOf:40. -> 4
a1 findFirst:[:e | e > 10] -> 2
a1 findLast:[:e | e > 10] -> 4
a1 detect:[:e | e > 10] -> 20</lang>
ByteArray
<lang smalltalk>"a Byterray literal (i.e. constant); this is immutable"
b1 := #[10 20 30 40].
all of the above also works for ByteArrays</lang>
String
<lang smalltalk>"a String literal (i.e. constant); this is immutable"
s1 := 'hello'.
s2 := 'здрависване'.
"all of the above also works for Strings; i.e."
s1 occurencesOf:$l -> 2
s1,' ',s2 -> 'hello здрависване'.</lang>
OrderedCollection
<lang smalltalk>"these are like arrays, but they can also grow or shrink"
o1 := #(10 20 30 40) asOrderedCollection.
o1 add:'fifty'.
o1 addAll: #(60 70.0).
o1 addAll: a1.
o1 addAll: s1.
o1 -> OrderedCollection(10 20 30 40 'fifty' 60 70.0 10 20 30 40 $h $e $l $l $o).
o1 removeLast:4.
o1 removeFirst:4.
o1 -> OrderedCollection('fifty' 60 70.0 10 20 30 40 $h).
o1 addFirst:1.
o1 add:22 beforeIndex:3.
"of course, all of the above also work for OrderedCollections"</lang>
Dictionary
<lang smalltalk>"these can take any object as key"
d1 := Dictionary new.
d1 at:1 put:'one'. "an integer works as key"
d1 at:'one' put:1. "an string as key"
d1 at:a1 put:42. "an array as key"
d1 at:'one'. -> 1 "access by key"
d1 at:#(10 20 30 40). -> 42 "any object as key, again
d1 printCR -> Dictionary(1->one one->1 #(10 20 30 40)->42)
d1 removeKey:'one'
d1 includesKey:'two' -> false. "is key present"
d1 includes:2 -> false. "is value present; attention: not O(1)"</lang>
Overall there are hundreds of methods implemented in Collection, from which all of the above inherit and which are not listed here.
[[Category:Data Structures]]
| |||