Data Structures and Algorithms 02 Arrays PDF

COMP20280 Data Structures and Algorithms 02 Arrays Dr. Aonghus Lawlor [email protected]  Arrays COMP20280 2 Array Definition An array is a sequenced collection of variables all of the same type. Each var...

COMP20280 Data Structures and Algorithms 02 Arrays Dr. Aonghus Lawlor [email protected]  Arrays COMP20280 2 Array Definition An array is a sequenced collection of variables all of the same type. Each variable, or cell, in an array has an index, which uniquely refers to the value stored in that cell. The cells of an array, a, are numbered 0, 1, 2, and so on. Each value stored in an array is often called an element of that array. -1 12 0 -7 14 9 3 2 11 6 values 0 1 2 3 4 5 6 7 8 9 indices COMP20280 3 Array Length and Capacity Since the length of an array determines the maximum number of things that can be stored in the array, we will refer to the length of an array as its capacity. In Java, the length of an array named a can be accessed using the syntax a.length. Thus, the cells of an array, a, are numbered 0, 1, 2, and so on, up through a.length−1, and the cell with index k can be accessed with syntax a[k]. int [] a = {-1, 12, 0, -7, 9, 3, 2, 11, 6}; a[a.length-1] a -1 12 0 -7 14 9 3 2 11 6 values 0 1 2 3 4 5 6 7 8 9 indices COMP20280 4 Declaring Arrays The first way to create an array is to use an assignment to a literal form when initially declaring the array, using a syntax as: elementType[] arrayName = {initialValue0, initialValue1, …, initialValuen−1}; The elementType can be any Java base type or class name, and arrayName can be any valid Java identifier. The initial values must be of the same type as the array. COMP20280 5 Declaring Arrays The second way to create an array is to use the new operator. However, because an array is not an instance of a class, we do not use a typical constructor. Instead we use the syntax: elementType[] arrayName = new elementType[n]; n is a positive integer denoting the length of the new array. The new operator returns a reference to the new array, and typically this would be assigned to an array variable. COMP20280 6 Arrays Arrays can be used to store primitives boolean, byte, char, short, int, long, float, double a = int(1); 1 0 0 1 0 Or references to objects: String[] s = new String{“java”, “C++”, “Python”}; new String(“Python”) new String(“java”) new String(“C++”) COMP20280 7  Multidimensional Arrays In Java, the syntax for two-dimensional arrays is similar to the what is the size syntax for one-dimensional arrays, except that an extra index of this array? is involved: int[][] a = new int; [[1,2,3], Direct [4,5,6,9], nitialisation int[][] b = { { 1, 2, 3 }, { 4, 5, 6, 9 }, { 7 }, }; ] Java does not actually have two-dimensional arrays The elements in a 2D array of type int[][] are variables of type int[]. A variable of type int[] can only hold a pointer to an array of int. So, a 2D array is really an array of pointers, where each pointer can refer to a one-dimensional array. COMP20280 8  Multidimensional Arrays rows columns 1 9 2 6 int[][] a = new int; 5 9 7 2 -1 8 0 4 Java doesn't really support true multi-dimensional arrays. In a true two-dimensional array, all the elements of the array occupy a contiguous block of memory. In Java, a multi-dimensional array is an a 1 9 2 6 array of array. For example, two-dimensional array in Java is simply an array of a one- 5 9 7 2 dimensional array: String[][] is an array of String[] or "array of array of strings". -1 8 0 4 COMP20280 9 Multidimensional Arrays Higher dimensional arrays: int[][][] a = new int; Straightforward extension of 2D syntax COMP20280 10 Arrays the length method of an array tells us the size of the array (number of elements in the array) boolean [] a = {true, false, false, true}; all these arrays have length of 4 how much memory double [] a = {0.1, 0.99999, -1.0, 0.3333}; do they actually occupy? String [] a = {"Python", "Java", "C ", "Rust"}; COMP20280 11 + + Array Memory A single-dimension array is a single object. As expected, the array has the usual object header. However, this object header is 12 bytes to accommodate a four-byte array length variable. The array data consists of the number of elements multiplied by the number of bytes required for one element, depending on its type. The memory usage for one element is 4 bytes for an object reference; for a list of the memory usage of primitive types, see the page on Java data types. If the total memory usage of the array is not a multiple of 8 bytes, then the size is rounded up to the next multiple of 8 (just as for any other object). COMP20280 12 Array Memory Java selected type size (eg: double = 8 bytes) 'S' (let's not mention Strings) Java array rounding up to multiple of: 8 bytes 'q' Java reference size: 4 bytes 'R' Java array header size: 12 bytes 'H' double[N] = (N * S + H) + (N * S + H) % q = 'x' double[M][N] = [M * (x + R) + H] + [M * (x + R) + H] % q = 'y' Example: double = (4 * 8 + 12) + (4 * 8 + 12) % 8 = 48 Bytes double = [10 * (96 + 4) + 12] + [10 * (96 + 4) + 12] % 8 = 1016 Bytes COMP20280 13  java.util.Arrays The Arrays class of the java.util package contains several static methods that we can use to fill, sort, search, etc in arrays. This class is a member of the Java Collections Framework and is present in java.util.arrays. Sample of methods: The string representation consists of a list of the array’s public static String toString(int[] a) elements, public static void sort(int[] a) Sorts the specified array into ascending numerical order. Copies the specified array and length. It truncates the array public static int[] copyOf(int[] original, int newLength) if provided length is smaller and pads if provided Fills all elements of the specified array with the specified public static void fill(int[] a, int val) value. COMP20280 14 Arrays initialising multidimensional arrays int[][] board = new int; for (int i = 0; i < board.length; i ) { for (int j = 0; j < board[i].length; j ) { board[i][j] = i + j; } } COMP20280 15 + + + +  Arrays printing multidimensional arrays 0 1 2 now let's print a two dimensional array in Java for (int[] a : board) { for (int i : a) { System.out.print(i + "\t"); 1 2 3 } System.out.println("\n"); } 2 3 4 COMP20280 16 / / Arrays Java has built in System.out.println("another way to print 2D arrays"); System.out.println(Arrays.deepToString(board)); [[0, 1, 2], [1, 2, 3], [2, 3, 4]] COMP20280 17 Array Examples Creating arrays Different object types Iterating over arrays Passing arrays as arguments to functions COMP20280 18 Examples: Integer[] a = new Integer[]{ 1,2,3,4,5,6,7,8,9,10 }; System.out.println(Arrays.deepToString(a)); [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] COMP20280 19 Examples: Integer[][][] b = new Integer; System.out.println(Arrays.deepToString(b)); [[[null, null], 4 [null, null], 3 [null, null]], 2 [[null, null], [null, null], [null, null]], [[null, null], [null, null], [null, null]], [[null, null], [null, null], [null, null]] ] COMP20280 20 Examples: Integer[][][] b = new Integer; System.out.println(Arrays.deepToString(b)); [[[null, null], [null, null], [null, null]], for(int i = 0; i < c.length; i) { [[null, null], for(int j = 0; j < c[i].length; j) { [null, null], for(int k = 0; k < c[i][j].length; k) { [null, null]], System.out.println(c[i][j][k]); [[null, null], } [null, null], } [null, null]], } [[null, null], [null, null], Using Arrays.deepToString is easier than figuring out the [null, null]] indices (there is an error in this code- can you find it?) ] COMP20280 21 + + + + + + Examples Integer[] a = new Integer[]{ -1,12,-13,40,-50,61,-7,18,-9,10 }; int sum = 0; for(int i = 0; i < a.length; i) { sum += a[i]; } System.out.println("sum: " + sum); sum: 61 COMP20280 22 + + Examples Integer[] a = new Integer[]{ -1,12,-13,40,-50,61,-7,18,-9,10 }; Let’s use streams: int sum_1 = Arrays.stream(a).reduce(0, (x,y) x+y); int sum_2 = Arrays.stream(a).reduce(0, Integer sum); int sum_3 = Arrays.stream(a).reduce(0, ArithmeticUtils add); int sum_4 = Arrays.stream(a).collect(Collectors.summingInt(Integer intValue)); int sum_5 = Arrays.stream(a).mapToInt(Integer intValue).sum(); COMP20280 23 - : : > : : : : : : Examples int sum_8 = Arrays.stream(a).mapToInt(Integer intValue).filter((i) i > 0).sum(); > sum_8: 141 filtering Integer[] d = IntStream.range(10, 20).boxed().toArray(Integer[] new); constructing ranges > d: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19] applying a function to transform the array (map) Integer[] d1 = IntStream.rangeClosed(10, 20).boxed().toArray(Integer[] new); > d1: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] IntStream.range(1, 10).mapToDouble((i) Math.pow(i, 2)).boxed().forEach(System.out println); > 1.0 4.0 9.0 16.0 25.0 36.0 49.0 64.0 COMP20280 24 - > : : : : - > : : : : Examples Random random = new Random(); int n = 10; random.ints(n).forEach(System.out println); Double [] d_rnd = random.doubles(n, 0, 1).boxed().toArray(Double[] new); d_rnd: [0.3001528172122965, 0.49023460272602637, 0.22821378960676886, 0.01703052782470249, 0.4125024457982719, 0.8741234790872718, 0.6123476898724487, 0.005468852491704146, 0.12525446744387625, 0.14768559962902228] COMP20280 25 : : : :  Abstract Data Types ADT COMP20280 26 Abstract Data Types mathematical models of a data structure type of the data stored operations supported on them types of the parameters of the operations implementation details are hidden (encapsulation) A client does not need to know how a data type is implemented in order to be able to use it. COMP20280 27  Abstract Data Types ADT abstracts from the organisation to the meaning of the data ADT abstracts from structure to use Classes are Representation does not matter different Both The type is a set of operations implement the Point2D Clients are forced to call operations to access the data concept public class Point2D public class Point2D Point2D(float x, float y) Point2D(float r, float theta) COMP20280 28 Abstract Data Types We like to use ADT’s because: Delay decisions implementation details Fix bugs can modify the underlying implementation without affecting clients Performance optimisations can improve performance without requiring changes on the client side) COMP20280 29 Example ADT The String type in Java is a useful ADT. String is an indexed sequence of char values, and has lots of useful methods: public class String String() int length() int charAt() int indexOf(String p) String concat(String p) String substring(int i, int j) String[] split(String delim) int compareTo(String p) boolean equals(String t) COMP20280 30 Implementing ADT s We public class Point2D { implement Instance variables private float x; private float y; ADTs with a public Point2D(float x, float y) { this.x = x; Java class this.y = y; Constructor } public void move(float dx, float dy) { x += dx; y += dy; } Instance methods String toString() { return "[" + x + ", " + y + "]"; } public static void main(String [] args) { Point2D p = new Point2D(10.0, 20.0); main, with some tests System.out.println(p); } } COMP20280 31 ’  Implementing ADT s public class Point2D { private float x; Instance variables. Instance variables private float y; public Point2D(float x, float y) { data-type values this.x = x; this.y = y; Each declaration is qualified Constructor } by a visibility modifier. public void move(float dx, float dy) { x += dx; In ADT implementations, we y += dy; use private, } Instance methods String toString() { representation of an ADT is return "[" + x + ", " + y + "]"; to be hidden from the client } use final, if the value is not public static void main(String [] args) { to be changed once it is Point2D p = new Point2D(10.0, 20.0); initialised. main, with some tests System.out.println(p); } } COMP20280 32 ’  Implementing ADT s Constructors. public class Point2D { private float x; The constructor establishes Instance variables private float y; an object's identity and public Point2D(float x, float y) { initialises the instance this.x = x; this.y = y; variables. Constructor } We can overload the name public void move(float dx, float dy) { x += dx; and have multiple y += dy; constructors with different } signatures Instance methods String toString() { return "[" + x + ", " + y + "]"; If no other constructor is } defined, a default no- public static void main(String [] args) { argument constructor is Point2D p = new Point2D(10.0, 20.0); implicit, has no arguments, main, with some tests System.out.println(p); and initialises instance values } to default values. } COMP20280 33 ’  Implementing ADT s public class Point2D { private float x; Instance variables private float y; public Point2D(float x, float y) { Instance methods. this.x = x; this.y = y; specify the data-type operations. Constructor } the signature specifies its name public void move(float dx, float dy) { and the types and names of its x += dx; parameter variables) y += dy; } Instance methods may Instance methods String toString() { be public (specified in the API) return "[" + x + ", " + y + "]"; or private (used to organise the } computation and not available to clients). public static void main(String [] args) { Point2D p = new Point2D(10.0, 20.0); main, with some tests System.out.println(p); } } COMP20280 34 ’  Designing ADT’s COMP20280 35 Designing ADT’s Encapsulation. A hallmark of object-oriented programming is that it enables us to encapsulate data types within their implementations, to facilitate separate development of clients and data type implementations. Encapsulation enables modular programming. COMP20280 36 Designing ADT’s Designing APIs. Ideally, an API would clearly articulate behaviour for all possible inputs, including side effects, and then we would have software to check that implementations meet the specification, but this is usually impossible to achieve. There are numerous potential pitfalls when designing an API: Too hard to implement, making it difficult or impossible to develop. Too hard to use, leading to complicated client code. Too narrow, omitting methods that clients need. provide to clients Too wide, including a large number of methods not needed by any client. the methods Too general, providing no useful abstractions. they need and no others. Too specific, providing an abstraction so diffuse as to be useless. Too dependent on a particular representation, therefore not freeing client code from the details of the representation. COMP20280 37 Design Patterns A standard solution to a common programming problem a design or implementation structure that achieves a particular purpose a high-level programming idiom A technique for making code more flexible reduce coupling among program components Shorthand for describing program design a description of connections among program components COMP20280 38 Design Patterns - Encapsulation Problem: Exposed fields can be directly manipulated Objects can be changed unexpectedly Encapsulation Dependences prevent changing the implementation Inheritance Encapsulation Solution: Hide some components Iteration Permit only stylised access to the object... Disadvantages: Interface may not (efficiently) provide all desired operations – Indirection may reduce performance COMP20280 39 Encapsulation To achieve public final class Point2D { private double x, y; encapsulation in Java: public Point2D(double x, double y) { this.x = x; this.y = y; } Declare the variables of public double x() { return x; a class as private. } public double y() { return y; } Provide public setter public double r() { return Math.sqrt(x*x + y*y); and getter methods to } public double theta() { modify and view the } return Math.atan2(y, x); variables values. public static void main(String[] args) { int x0 = 1; int y0 = 2; Point2D p = new Point2D(x0, y0); System.out.println(p.x(), p.y(), p.r(), p.theta()); } } COMP20280 40 Design Patterns - Inheritance (subclassing) base class Problem: public interface List { int size(); Repetition in implementations boolean isEmpty(); boolean add(E e); boolean remove(E e); Similar abstractions have similar members (fields, } methods) sub-class Solution: public class LinkedList implements List { Node start, end; Inherit default members from a superclass public LinkedList() { Implementation is determined at runtime } public boolean add(E e) { Disadvantages: // implementation } Code for a class can be spread over multiple files public boolean remove(E e) { // implementation Runtime performance overhead of dispatching } } COMP20280 41 Design Patterns - Iteration to get this behaviour... Problem: Iterator it = coll.iterator(); To access all members of a collection, we must perform a while(it.hasNext()) { System.out.print(itr.next() + " "); specialised traversal for each data structure } Undesirable dependencies Does not generalise well to other collections implement the Iterator Solution: pattern in our object Allow the implementation to perform the traversal, and // Returns true if there are more elements. do the bookkeeping // Otherwise, returns false. boolean hasNext(); Communicate the result to the clients Disadvantages: // Returns the next element. Object next(); Iteration order is implementation dependent and not // Removes the current element. controlled by client void remove(); COMP20280 42 Iteration SinglyLinkedList sll = new SinglyLinkedList(); sll.addFirst(1); sll.addFirst(2); //... These two forms are identical. The JVM transforms the first into the second Iterator iterator = sll.iterator(); for(Integer s : sll) { System.out.println(s); while(iterator.hasNext()) { } Integer element = iterator.next(); System.out.println( element ); } What is required for this to work: iterator() method in the object which returns an Iterator object the Iterator object must have a.hasNext() and a.next() method COMP20280 43 Iteration public Iterator iterator() { iterator() method in the return new SinglyLinkedListIterator(); } object which returns an Iterator object private class SinglyLinkedListIterator implements Iterator { Node curr = (Node) head; @Override We create the Iterator object as a private class in the public boolean hasNext() { return curr != null; SinglyLinkedList. } The Iterator has a curr pointer to the head of the @Override public E next() { enclosing list. E res = curr.getElement(); curr = curr.next; The hasNext method checks for the end of the iteration return res; (a pointer to null). } } The next method advances the pointer and returns the current element You will use this pattern for every data structure you implement COMP20280 44 Iteration SinglyLinkedList sll = new SinglyLinkedList(); We would like to ‘iterate’ through the sll.addFirst(1); values in our data structure sll.addFirst(2); //... This will work, but the “get(i)” method is very slow for linked lists and a loop for(int i = 0; i < sll.size(); ++i) { like this would be O(n 2) System.out.println(sll.get(i)); } What if the data structure doesn’t have a “get(i)" method? This is the case for some of the Tree structures we will be working with. SinglyLinkedList sll = new SinglyLinkedList(); sll.addFirst(1); The new for loop syntax is better, but you will get sll.addFirst(2); an error: //... foreach not applicable to type for(Integer s : sll) { ‘exercises.SinglyLinkedList' System.out.println(s); } unless you implement the “Iterable” interface for this syntax to work. COMP20280 45 Design Patterns - Exceptions Problem: Code should not be cluttered with error-handling public E getFirst() { routines final Node f = first; if (f == null) Solution: throw new NoSuchElementException(); return f.item; Use language facilities for throwing, catching } exceptions Disadvantages: the exception is thrown but the caller is responsible for doing Code may still be cluttered something about it... It can be hard to decide where the exception should be handled Using exceptions for normal control flow can be confusing and inefficient COMP20280 46