CS计算机代考程序代写 prolog data structure Java ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
List: iterative list processing

by

Marcel Turcotte

Version March 20, 2020

Preamble

Preamble

Overview

Overview

List: iterative list processing

We compare the computational time required to traverse a linked list when statements have
access to the nodes of the list against the implementation using the methods of the
interface of the list. We explore an efficient implementation without accessing the nodes of
the list directly.

General objective :
This week you will be able to explain and use an iterator.

1 65

Foreword

The topics covered in this module will reinforce the notions of encapsulation and
object-oriented programming, including the notion of the state of the object, as
well as the interfaces.
It is also an opportunity to informally introduce the complexity of computation
(asymptotic analysis) that will be presented to you in the data structure course.

2 65

Preamble

Learning objectives

Learning objectives

Compare the time required to traverse a linked list, discuss the case where statements
have access to nodes in the list compared to the implementation having access only to
the methods of its interface.
Compare nested static and non-static Java classes.
Modify the implementation of an iterator in order to add a method to it.

Lectures:
Pages 89-96, 103-112 of E. Koffman and P. Wolfgang.

3 65

Preamble

Plan

Plan

1 Preamble

2 Motivation

3 Concept

4 Implementation 1.0

5 Implementation 2.0

6 Implementation 3.0

7 Prologue

4 65

Motivation

Motivation

Problem

Motivation

You must devise a method to traverse a linked list.

5 65

Motivation

Details

Details

We’re working with an singly linked implementation of the interface List.
pub l i c i n t e r f a c e L i s t {

boolean add (E e lement ) ;
E get ( i n t i n d e x ) ;
boolean remove (E e lement ) ;
i n t s i z e ( ) ;

}

The difficulties would be the same if the list was doubly linked.
We’ll call this implementation LinkedList.

6 65

An example of a list

L i s t c o l o r s ;
c o l o r s = new L i n k e d L i s t () ;

c o l o r s . add ( ” b l e u ” ) ;
c o l o r s . add ( ” b l anc ” ) ;
c o l o r s . add ( ” rouge ” ) ;
c o l o r s . add ( ” j aune ” ) ;
c o l o r s . add ( ” v e r t ” ) ;
c o l o r s . add ( ” orange ” ) ;

7 65

Motivation

Internal implementation

Implementation A : inside the class

Inside the class LinkedList, we have access to the implementation details. In
particular, we have access to the nodes.

Give an implementation:

8 65

Motivation

External implementation

Implementation B : out of the class

Outside the class LinkedList, we don’t have access to the implementation details. In
particular, we don’t have access to the nodes.

Give an implementation:

9 65

Remark

From outside the class LinkedList, we need to use E get(int pos) to access the
elements of the list.

10 65

Motivation

Computation time

Discussion

Compare the runtime of the two implementations (internal and external).
Is the implementation of the inside the class faster or slower?
Are the differences minor or major?

11 65

Computation time

These are the execution times in nanoseconds for lists of increasing size.

# nodes A B
20,000 73,214 523,248,106
40,000 138,208 2,054,870,866
80,000 277,909 8,430,799,795

160,000 671,434 36,546,381,116
320,000 1,461,222 157,744,738,581
640,000 3,428,519 655,822,468,389

1,280,000 5,922,119 45 minutes!

For 1, 280, 000 elements, it takes about 45 minutes to go through the list with calls to
get(pos), whereas it only takes 5.92 milliseconds for the approach A.

12 65

Motivation

Discussion

Discussion

How do you explain that difference?
For each implementation, what mathematical relationship is there between the
number of elements in the list, n, and the computation time?

Complete the sentence: every time the number of elements n doubles, the
computation time . . .

13 65

Give the implementation of the method E get(int pos).
Therefore, the implementation of B
f o r ( i n t i =0; i < c o l o r s . s i z e ( ) ; i ++) { System . out . p r i n t l n ( c o l o r s . ge t ( i ) ) ; } Is equivalent to this: Number of nodes visited Call # of nodes visited get(0) 1 get(1) 2 get(2) 3 get(3) 4 . . . get(n-1) n 15 65 Motivation Conclusion Discussion Implementation A visits n nodes. Implementation B visits n2 nodes! 16 65 Concept Concept Objective Concept Objective: Devise an approach to traverse the list one and only once. The user of the list will not have access to the implementation (p.next and others)! The proposed solution will be applicable in a very specific context, when all nodes of the list are visited sequentially. This is not a general solution to speed up get(i). 17 65 Iterator The iterator is a uniform and general mechanism for traversing a variety of data structures, such as lists, but also trees and others (see CSI2110); Provides access to the elements one element at a time; Part of the Java collections. 18 65 Concept Interface Interface Iterator pub l i c i n t e r f a c e I t e r a t o r {
E next ( ) ;
boolean hasNext ( ) ;

}

19 65

Discussion : implementation

Which class will implement Iterator?
How do you create and initialize an iterator?
How do you move the iterator?
How do I detect the end of the iteration?

20 65

Implementation 1.0

Let’s develop an initial implementation that will be quite different from the final
implementation.
It will be a good intermediate step, though.
The class LinkedList implements the interface Iterator.

21 65

Implementation 1.0

Implementation 1.0

pub l i c c l a s s L i n k e d L i s t implements L i s t , I t e r a t o r {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e Node head ;

// . . .

pub l i c E next ( ) { . . . }

pub l i c boo lean hasNext ( ) { . . . }

}

22 65

Implementation 1.0

Example

Contract
0 1 2 3 4

^^ ^ ^ ^ ^
0 1 2 3 4

^^ ^ ^ ^ ^
0 1 2 3 4

^^ ^ ^ ^ ^
0 1 2 3 4

^^ ^ ^ ^ ^
0 1 2 3 4

^^ ^ ^ ^ ^
0 1 2 3 4

^^ ^ ^ ^ ^
Conceptually, the iterator is to the left of the first element at the beginning of the
iteration.
When a call is made to the method next:
1. The iterator is moving forward;
2. Returns the value of the element visited.

A call to the method next when the list is empty or at the end of iteration (when
hasNext returns false) is an error and an exception will be thrown.

23 65

Example

L i s t l ;
l = new L i n k e d L i s t () ;

f o r ( i n t i =0; i <5; i ++) { l . add (new I n t e g e r ( i ) ) ; } i n t sum = 0 ; whi le ( l . hasNext ( ) ) { I n t e g e r v = l . nex t ( ) ; sum += v . i n t V a l u e ( ) ; } System . out . p r i n t l n ( "sum = " + sum ) ; 24 65 Example 0 1 2 3 4 ^^ ^ ^ ^ ^ 0 1 2 3 4 ^^ ^ ^ ^ ^ 0 1 2 3 4 ^^ ^ ^ ^ ^ 0 1 2 3 4 ^^ ^ ^ ^ ^ 0 1 2 3 4 ^^ ^ ^ ^ ^ 0 1 2 3 4 ^^ ^ ^ ^ ^ i n t sum = 0 ; whi le ( l . hasNext ( ) ) { I n t e g e r v = l . nex t ( ) ; sum += v . i n t V a l u e ( ) ; } System . out . p r i n t l n ( "sum = " + sum ) ; 25 65 Implementation 1.0 Discussion What are the necessary instance variables? All it takes is one, current. What’s the type of the variable current? Node

What will be the initial value of current?

The initial value is null and conceptually, the iterator is positioned in before the first
element.

On the first call,

the method next positions the variable current on the first node, and returns the value
found there.

For each subsequent call,

next moves current to the next element.

head

B CA

current

Before iteration

head

B CA

current

after the call to next()

head

B CA

current

after the call to next()

head

B CA

current

after the call to next()

27 65

Implementation 1.0

Instance variable

Implementation 1.0

pub l i c c l a s s L i n k e d L i s t implements L i s t , I t e r a t o r {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e Node head ;
p r i v a t e Node c u r r e n t ;

// . . .

pub l i c E next ( ) { . . . }

pub l i c boo lean hasNext ( ) { . . . }

}

28 65

Implementation 1.0

next

Implementation 1.0

pub l i c c l a s s L i n k e d L i s t implements L i s t , I t e r a t o r {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e Node head ;
p r i v a t e Node c u r r e n t ;

pub l i c E next ( ) {

}

}

29 65

Implementation 1.0

30 65

Implementation 1.0

hasNext

Implementation 1.0

pub l i c c l a s s L i n k e d L i s t implements L i s t , I t e r a t o r {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e Node head ;
p r i v a t e Node c u r r e n t ;

pub l i c boo lean hasNext ( ) {

}

}

31 65

Implementation 1.0

32 65

Is it fast?

These are the execution times in nanoseconds for lists of increasing size.

# nodes Inside Iterator
20,000 73,214 113,817
40,000 138,208 167,639
80,000 277,909 324,540
160,000 671,434 758,642
320,000 1,461,222 1,760,357
640,000 3,428,519 3,717,519

1,280,000 5,922,119 7,239,676

For 1, 280, 000 elements, the computation time is 7.2 milliseconds, barely 13% slower
than the implementation having access to the elements!

33 65

Implementation 1.0

Discussion

Discussion

What’s the biggest restriction of our implementation?

Only one iteration at a time.

What does it take to overcome that limitation?

Several references. One reference per iterator.

34 65

Implementation 2.0

Implementation 2.0

Memory diagram

Memory diagram

Discuss this memory diagram.

head

DB CA

current current

35 65

Discussion

head

DB CA

current current

LinkedList does not implement the interface Iterator.
The iterator is an object that has an instance variable, current, of type Node.
As many iterators as it takes.
The iterator must have access to the elements of the list.
A first level class wouldn’t have access to the elements.
Suggestions?
That’s right, the iterator is a nested class.

36 65

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

An itrator must belong to a given list.
An itrator must access the variable head from its list.

pub l i c E next ( ) {
i f ( c u r r e n t == nu l l ) {

c u r r e n t = head ;
} e l s e {

c u r r e n t = c u r r e n t . nex t ;
}
i f ( c u r r e n t == nu l l ) {

throw new NoSuchElementExcept ion ( ) ;
}
re tu rn c u r r e n t . v a l u e ;

}

Memory diagram

Discuss this memory diagram.

head

DB CA

current

i

current

j

myList

myList

38 65

Implementation 2.0

Instance variables and constructor

pub l i c c l a s s L i n k e d L i s t implements L i s t {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r implements I t e r a t o r {

p r i v a t e Node c u r r e n t ;
p r i v a t e L i n k e d L i s t myLis t ;

p r i v a t e L i s t I t e r a t o r ( L i n k e d L i s t myLis t ) {
t h i s . myL i s t = myLis t ;
c u r r e n t = n u l l ;

}

pub l i c boo lean hasNext ( ) { . . . }

pub l i c E next ( ) { . . . }
}

p r i v a t e Node head ;

}

Implementation 2.0

next

pub l i c c l a s s L i n k e d L i s t implements L i s t {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r implements I t e r a t o r {

p r i v a t e Node c u r r e n t ;
p r i v a t e L i n k e d L i s t myLis t ;

pub l i c E next ( ) {
i f ( c u r r e n t == n u l l ) {

c u r r e n t = ;
} e l s e {

c u r r e n t = c u r r e n t . nex t ;
}
i f ( c u r r e n t == n u l l ) {

throw new NoSuchElementExcept ion ( ) ;
}
r e t u r n c u r r e n t . v a l u e ;

}

pub l i c boo lean hasNext ( ) { . . . }
}

p r i v a t e Node head ;
}

Implementation 2.0

hasNext

pub l i c c l a s s L i n k e d L i s t implements L i s t {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r implements I t e r a t o r {

p r i v a t e Node c u r r e n t ;
p r i v a t e L i n k e d L i s t myLis t ;

pub l i c E next ( ) { . . . }

pub l i c boo lean hasNext ( ) {
i f ( c u r r e n t == n u l l && != n u l l ) {

r e t u r n t rue ;
} e l s e i f ( c u r r e n t != n u l l && c u r r e n t . nex t != n u l l ) {

r e t u r n t rue ;
} e l s e {

r e t u r n f a l s e ;
}

}
}

p r i v a t e Node head ;
}

Implementation 2.0

iterator

pub l i c c l a s s L i n k e d L i s t implements L i s t {

p r i v a t e s t a t i c c l a s s Node { . . . }

p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r implements I t e r a t o r {

p r i v a t e Node c u r r e n t ;
p r i v a t e L i n k e d L i s t myLis t ;

p r i v a t e L i n k e d L i s t I t e r a t o r ( L i n k e d L i s t myLis t ) {
t h i s . myL i s t = myLis t ;
c u r r e n t = n u l l ;

}
pub l i c E next ( ) { . . . }
pub l i c boo lean hasNext ( ) { . . . }

}

pub l i c I t e r a t o r i t e r a t o r ( ) {

}

p r i v a t e Node head ;
}

Implementation 2.0

Example

L i n k e d L i s t l ;
l = new L i n k e d L i s t () ;

// . . .

I t e r a t o r i ;
i = l . i t e r a t o r ( ) ;

whi le ( i . hasNext ( ) ) {

I n t e g e r v1 = i . nex t ( ) ;

I t e r a t o r j ;
j = l . i t e r a t o r ( ) ;

whi le ( j . hasNext ( ) ) {

I n t e g e r v2 = j . nex t ( ) ;

System . out . p r i n t l n ( ” ( “+v1+” , “+v2+” ) ” ) ;
}

}

Implementation 2.0

Computation time

Is it fast?

These are the execution times in nanoseconds for lists of increasing size.

# nodes Inside Iterator
20,000 73,214 113,817
40,000 138,208 167,639
80,000 277,909 324,540
160,000 671,434 758,642
320,000 1,461,222 1,760,357
640,000 3,428,519 3,717,519

1,280,000 5,922,119 7,239,676

For 1, 280, 000 elements, the computation time is 7.2 milliseconds, barely 13% slower
than the implementation having access to the elements!

47 65

Implementation 3.0

Implementation 3.0

Inner class

«Getting in Touch with your Inner Class»

www.javaranch.com/campfire/StoryInner.jsp

48 65

http://www.javaranch.com/campfire/StoryInner.jsp

Definition

An inner class is a non-static nested class.
An object of an inner (non-static) class has access to the variables and methods of
the object of the outer class from which it was created.

49 65

Implementation 3.0

next

Implementation 3.0

hasNext

Implementation 3.0

iterator

Implementation 3.0

Memory diagram

Inner class

head

DB CA

current

i

current

j

53 65

Classe interne

head

DB CA

current

i

current

j

54 65

Example

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

55 65

Implementation 3.0

Example

head

l1

DB CA

current

i

current

j

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

i f ( j . hasNext ( ) ) {
S t r i n g o = j . nex t ( ) ;

}

head

l1

DB CA

current

i

current

j

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

whi le ( j . hasNext ( ) ) {
S t r i n g o = j . nex t ( ) ;

}

head

l1

DB CA

current

i

current

j

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

i f ( i . hasNext ( ) ) {
S t r i n g o = i . nex t ( ) ;

}

head

l1

DB CA

current

i

current

j

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

head

l2

2 31

current

k

i f ( k . hasNext ( ) ) {
I n t e g e r o = k . next ( ) ;

}

head

l1

DB CA

current

i

current

j

head

l1

DB CA

current

i

current

j

head

l2

2 31

current

k

head

l2

2 31

current

k

whi le ( k . hasNext ( ) ) {
I n t e g e r o = k . next ( ) ;

}

Computation time

These are the computation times in nanoseconds for lists of increasing size.

# nodes Inside Iterator Get
10,000 43,508 66,849 1.118841e+08
20,000 49,233 66,986 4.619370e+08
40,000 99,714 108,464 1.873445e+09
80,000 240,057 252,130 8.404544e+09

160,000 592,818 615,779 2.892314e+10
320,000 1,039,555 1,142,309 1.401875e+11
640,000 2,328,335 2,448,321 6.258633e+11

1,280,000 5,124,979 4,896,708 2.753671e+12
2,560,000 11,500,576 11,700,579 1.476815e+13

For 2,560,000 elements, get(pos) is 1 million times slower than the iterator!
1.48e+13 ns = 4.1 hours.

61 65

Prologue

Summary

The iterator is a mechanism for traversing a list one element at a time.
The method hasNext returns true if a call to the method next is possible.
The method next returns the next element in the iteration.
An inner class is a nested non-static class.
Objects of inner classes have access to the variables and methods of the outer class.

62 65

Next module

List : recursive processing

63 65

References I

E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.

64 65

Marcel Turcotte
Marcel.

École de science informatique et de génie électrique (SIGE)
Université d’Ottawa

65 / 65

Marcel.

Preamble
Overview
Learning objectives
Plan

Motivation
Problem
Details
Internal implementation
External implementation
Computation time
Discussion
Conclusion

Concept
Objective
Interface

Implementation 1.0
Example
Discussion
Instance variable
next
hasNext
Discussion

Implementation 2.0
Memory diagram
Instance variables and constructor
next
hasNext
iterator
Example
Computation time

Implementation 3.0
Inner class
next
hasNext
iterator
Memory diagram
Example

Prologue