SortingMachine
8 February 2019 OSU CSE 1
SortingMachine
Copyright By PowCoder代写 加微信 powcoder
• TheSortingMachinecomponentfamily allows you to add elements of type T to a
collection of such elements, and then to remove them one at a time in sorted order according to a client-supplied ordering
– Queue and Stack support removal in FIFO and LIFO order, respectively
8 February 2019 OSU CSE 2
SortingMachine
FIFO and LIFO are
• TheSortingMachinecomponentfamily
value-based ordering.
collection of such elements, and then to
remove them one at a time in sorted order according to a client-supplied ordering
– Queue and Stack support removal in FIFO and LIFO order, respectively
time-based orderings; a
lements of type T to a
8 February 2019 OSU CSE 3
Why Not Use The sort Method?
while (/*input values remain*/) { /* let x = next input value */
} q.enqueue(x);
q.sort(order);
while (q.length() > 0) {
T x = q.dequeue();
/* output x */
8 February 2019 OSU CSE 4
Why Not Use The sort Method? while (/*input values remain*/) {
/* let x = next input value */
q.enqueue(x);
The Java libraries have similar methods to sort
built-in arrays and other “collections”.
}q.sort(order);
while (q.length() > 0) {
T x = q.dequeue();
/* output x */
8 February 2019 OSU CSE 5
• Suppose you want to find the students with the 50 highest GPAs among all Ohio State students
– Modify the previous code to show how you might do this …
8 February 2019 OSU CSE 6
Performance in the Example
• Code using a sort method spends time to sort all 50,000 GPAs just to find the top 50
• Code based on SortingMachine can be
much more efficient, because if you don’t remove all of the elements you don’t necessarily pay for sorting all of them
8 February 2019 OSU CSE 7
Interfaces and Classes
Standard Iterable extends extends
SortingMachine- Kernel
SortingMachine
implements
SortingMachine1L
implements
SortingMachine5
8 February 2019
Interfaces and Classes
Standard Iterable
extends extends
SortingMachine- Kernel
SortingMachineKernel
has contracts for six methods:
changeToExtractionMode
removeFirst
implements
SortingMachine
implements
isInInsertionMode
8 February 2019
gMachine1L
SortingMachine5
Interfaces and Classes
There is really an abstract class
as usual in the chain here, but it is not shown because these
slides describe the client view,
interface SortingMachine
and a class like SortingMachine1L.
and a client need
SortingMachine
implements
SortingMachine1L
implements
SortingMachine5
8 February 2019
Mathematical Model
SORTING_MACHINE_MODEL is ( insertion_mode: boolean, ordering: binary relation on T, contents: finite multiset of T
) exemplar m constraint
IS_TOTAL_PREORDER(m.ordering)
type SortingMachineKernel is modeled by
SORTING_MACHINE_MODEL
8 February 2019 OSU CSE 11
Mathematical Model
SORTING_MACHINE_MODEL is ( insertion_mode: boolean, ordering: binary relation on T, contents: finite multiset of T
) exemplar m constraint
The mathematical model is an ordered triple (a.k.a. three-tuple):
IS_TOTAL_PREORDER(m.ordering)
type SortingMachineKernel is modeled by a binary relation on T, and
SORTING_MACHINE_
8 February 2019
OSU CSE 12
te multiset of T. L
a boolean,
Mathematical Model
SORTING_MACHINE_MODEL is ( insertion_mode: boolean, ordering: binary relation on T, contents: finite multiset of T
) exemplar m constraint
Recall: a binary relation on T may be viewed as a set of ordered pairs of T,
IS_TOTAL_PREORDER(m.ordering)
or as a boolean-valued function R of
type SortingMachineKernel is modeled by two parameters of type T that is true
SORTING_MACHINE_MO
8 February 2019
OSU CSE 13
at pair is in the set.
Mathematical Model
SORTING_MACHINE_MODEL is ( insertion_mode: boolean, ordering: binary relation on T, contents: finite multiset of T
) exemplar m constraint
A finite multiset is essentially a finite set with multiple copies of elements
IS_TOTAL_PREORDER(m.ordering)
SORTING_MACHI
8 February 2019
OSU CSE 14
allowed, so there are effectively (non-
type SortingMachineKernel is modeled by negative) “counts” of all values of the
pe T; details as necessary. L
Mathematical Model
SORTING_MACHINE_MODEL is ( insertion_mode: boolean, ordering: binary relation on T, contents: finite multiset of T
) exemplar m constraint
IS_TOTAL_PREORDER(m.ordering)
type SortingMachineKernel is modeled by
SORTING_MACHINE_MODEL
8 February 2019 OSU CSE 15
Review: Comparators
• The Java interface Comparator
* Returns a negative integer, zero, or
* a positive integer as the first
* argument is less than, equal to, or
* greater than the second.
int compare(T o1, T o2); }
8 February 2019 OSU CSE 16
Review: Comparators
• The notion of “less than” and “greater than” can be anything
• The notion of “equal to” is actually supposed to be “equivalent to”, in the sense that the first argument is neither “less than” nor “greater than” the other
• There are important technicalities …
8 February 2019 OSU CSE 17
Review: Creating a Comparator
private static class IntegerLT implements Comparator
public int compare(Integer o1, Integer o2) {
if (o1 < o2) { return -1;
} else if (o1 > o2) { return 1;
return 0; }
8 February 2019
OSU CSE 18
Review: Creating a Comparator
private static class IntegerLT implements Comparator
public int compare(Integer o1, Integer o2) {
if (o1 < o2) { return -1;
} else if (o1 > o2) { return 1;
} return 0;
A class that implements Comparator is usually a
nested class (i.e., declared for local use inside another class), and if so should be declared private static.
8 February 2019
Review: Creating a Comparator
private static class IntegerLT implements Comparator
public int compare(Integer o1, Integer o2) {
return o1 – o2; }
Note that the results are not specified to be –1 for “less than” and +1 for
“greater than”, but merely negative and positive values, respectively! Does this code work?
8 February 2019
OSU CSE 20
Review: An Easy Comparator
private static class IntegerLT implements Comparator
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
Since a generic parameter must be a reference type, and each wrapper type T (here, Integer) implements the interface Comparable
– Sorting is based on the ordering provided by
the compare method from order • Requires:
IS_TOTAL_PREORDER(order)
• Ensures:
this = (true, order, {})
8 February 2019 OSU CSE 22
Comparator
SortingMachine
8 February 2019 OSU CSE 23
Comparator
SortingMachine
si = (true, ci, {})
8 February 2019 OSU CSE 24
• Addsxtothecontentsofthis.
• Aliases:referencex
• Updates:this.contents
• Requires:
this.insertion_mode • Ensures:
this.contents = #this.contents union {x}
void add(T x)
8 February 2019 OSU CSE
add void add(T x)
• Addsxtothecontentsofthis.
For multisets (like this.contents),
the union operator means the • Aliases:referencex
• Requires:
this.insertion_mode • Ensures:
this.contents = #this.contents union {x}
“counts” of all values are added. • Updates:this.contents
8 February 2019 OSU CSE
si = (true, ci, {13, 8})
si.add(x);
8 February 2019 OSU CSE 27
si = (true, ci, {13, 8})
si.add(x);
si = (true, ci, {13, 13, 8})
8 February 2019 OSU CSE 28
Note the alias created
ere, which you cannot see in the tracing table.
si = (true, ci, {13, 8})
si.add(x);
si = (true, ci, {13, 13, 8})
8 February 2019 OSU CSE 29
changeToExtractionMode void changeToExtractionMode()
• Changethemodeofthisfrominsertionto extraction.
• Updates:this.insertion_mode
• Requires:
this.insertion_mode
• Ensures:
not this.insertion_mode 8 February 2019 OSU CSE
si = (true, ci, {13, 13, 8})
si.changeToExtractionMode();
8 February 2019 OSU CSE 31
si = (true, ci, {13, 13, 8})
si.changeToExtractionMode();
si = (false, ci, {13, 13, 8})
8 February 2019 OSU CSE 32
removeFirst T removeFirst()
• Removes and returns some “first” (“smallest”) element from the contents of this.
• Updates: this.contents
• Requires:
not this.insertion_mode and this.contents /= {}
• Ensures:
removeFirst is in #this.contents and
for all x: T where (x is in this.contents)
(this.ordering(removeFirst, x)) and this.contents = #this.contents \ {removeFirst}
8 February 2019 OSU CSE
removeFirst T removeFirst()
• Removes and returns some “first” (“smallest”) element For multisets (like this.contents),
from the contents of this.
is in means the “count” of the
• Updates: this.contents
• Requires:
not this.insertion_mode and this.contents /= {}
• Ensures:
removeFirst is in #this.contents and
for all x: T where (x is in this.contents)
(this.ordering(removeFirst, x)) and this.contents = #this.contents \ {removeFirst}
8 February 2019 OSU CSE
given value is positive, i.e., that value is an element of the multiset.
removeFirst T removeFirst()
• Removes and returns some “first” (“smallest”) element For multisets (like this.contents),
from the contents of this.
\ means the “counts” of all values
• Updates: this.contents
• Requires:
not this.insertion_mode and this.contents /= {}
• Ensures:
removeFirst is in #this.contents and
for all x: T where (x is in this.contents)
(this.ordering(removeFirst, x)) and this.contents = #this.contents \ {removeFirst}
8 February 2019 OSU CSE
are subtracted (but all remain non- negative).
si = (false, ci, {13, 13, 8})
x = si.removeFirst();
8 February 2019 OSU CSE 36
si = (false, ci, {13, 13, 8})
x = si.removeFirst();
si = (false, ci,
{13, 13}) x=8
8 February 2019 OSU CSE 37
The element removed is a
“first” element based on the IntegerLT ordering, i.e., a smallest integer value.
si = (false, ci, {13, 13, 8})
x = si.removeFirst();
si = (false, ci,
{13, 13}) x=8
8 February 2019 OSU CSE 38
Example: Remove Another
si = (false, ci,
{13, 13}) x=8
x = si.removeFirst();
8 February 2019 OSU CSE 39
Example: Remove Another
si = (false, ci,
{13, 13}) x=8
x = si.removeFirst();
si = (false, ci, {13})
8 February 2019 OSU CSE 40
Example: Remove Another
si = (false, ci,
{13, 13}) x=8
The element removed is a “first”
Code State
element based on the IntegerLT ordering, i.e., a
smallest integer value; another such element remains!
x = si.removeFirst();
si = (false, ci, {13})
8 February 2019 OSU CSE
isInInsertionMode boolean isInInsertionMode()
• Reports whether this is in insertion mode.
• Ensures:
isInInsertionMode = this.insertion_mode
8 February 2019 OSU CSE
order Comparator
• Reports Comparator
• Ensures:
order = this.ordering
8 February 2019 OSU CSE
size int size()
• Reports the number of elements in this.contents.
• Ensures:
size = |this.contents|
8 February 2019 OSU CSE
For multisets (like this.contents),
int size()
• Reports the number of elements in
this.contents. • Ensures:
“counts” of all values.
|•| means the sum of the multiset’s
size = |this.contents|
8 February 2019 OSU CSE
iterator Iterator
• Returns an iterator over a multiset of elements of type T.
• Ensures:
multiset_entries(~this.seen * ~this.unseen) = this.contents
8 February 2019
multiset_entries is like entries for Iterator
a string, except that each string entry’s “count” in the multiset is the same as
• Returns an iterator over a set of elements
its (occurrence) count in the string.
multiset_entries(~this.seen * ~this.unseen) = this.contents
of type T.
• Ensures:
8 February 2019
Temporal Flexibility
• The contract for SortingMachineKernel
does not tell the client when “sorting” occurs, so an implementation of
SortingMachineKernel may pay the cost of comparing elements to each other:
– During add
– During changeToExtractionMode – During removeFirst
8 February 2019 OSU CSE 48
Instead of sort …
while (/*input values remain*/) { /* let x = next input value */
} q.enqueue(x);
q.sort(order);
while (q.length() > 0) {
T x = q.dequeue();
/* output x */
8 February 2019 OSU CSE 49
Instead of sort …
while (/*input values remain*/) { /* let x = next input value */
} sorter.add(x);
sorter.changeToExtractionMode(); while (sorter.size() > 0) {
T x = sorter.removeFirst();
/* output x */
8 February 2019 OSU CSE 50
while (/*in
Instead of sort …
“first 50” (“smallest 50”) values that were
/* let x = next input value */
} sorter.add(x);
sorter.changeToExtractionMode(); for (int i = 0; i < 50; i++) {
T x = sorter.removeFirst();
/* output x */
added to sorter.
8 February 2019 OSU CSE 51
Why Is This Better Than sort?
• If all elements are already sorted by the
end of changeToExtractionMode, then there is no difference in performance
compared to using sort
• If all elements are not already sorted by the
end of changeToExtractionMode, then there can be a performance advantage if
you don’t need to remove all the elements!
– See a future project ...
8 February 2019 OSU CSE 52
Sorting Algorithms • Implementer of
SortingMachineKernel may embed any sorting algorithm in it, e.g.:
– insertion sort (add does all the work)
– quicksort (changeToExtractionMode
does all the work)
– selection sort (removeFirst does all the work)
8 February 2019 OSU CSE 53
Sorting Algorithms
Actually, any sorting algorithm could be used when sorting is done entirely in
• Implementer of SortingMachineKernel may embed
changeToExtractionMode.
any sorting algorithm in it, e.g.:
– insertion sort (add does all the work)
– quicksort (changeToExtractionMode does all the work)
– selection sort (removeFirst does all the work)
8 February 2019 OSU CSE 54
Resources • OSU CSE Components API:
SortingMachine
– http://cse.osu.edu/software/common/doc/
8 February 2019 OSU CSE 55
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com