ADS:lab session #2

Сентябрь 7, 2022

Главная
Алгебра
ADS:lab session #2

Содержание

2. Time estimating in machine Machine measures time in 2 ways: For itself, by counting ticks For
3. What about Java
4. Another method Another way to calculate elapsed time is System.currentTimeMillis() method: long startTime = System.currentTimeMillis(); //
5. Storage estimating Storage refers to the data storage consumed in performing a given task, whether primary
6. The RAM model of computation The RAM model of computation estimate algorithm according the following rules:
7. Big O notation In Big O notation we are interested in the determining the order of
8. Calculate n-th Fibonacci number (n = 0) Number of steps: 5
9. Calculate n-th Fibonacci number (n = 1) Number of steps: 6
10. Calculate n-th Fibonacci number (n > 1) Number of steps: 9 + n + 3(n-1) =
11. Fibonacci number
12. Time complexities
13. More examples
14. Counting sort Sample output: n = 20 k = 25 A = 12 2 22 24
15. Task #1 Implement “counting sort” that sorts an array of integers Use Math.Random() or r.nextInt(k) to
17. Скачать презентацию

Слайд 2

Time estimating in machine
Machine measures time in 2 ways:
For itself, by

counting ticks
For humans, by converting ticks to date/time with taking into account leap years, leap seconds, coordination shifts (Kazan +3hrs) and network protocol for auto correlation

Слайд 3

What about Java

Слайд 4

Another method
Another way to calculate elapsed time is System.currentTimeMillis() method:
long startTime

= System.currentTimeMillis();
// ... do something ...
long estimatedTime = System.currentTimeMillis() – startTime;
Why long?

Слайд 5

Storage estimating
Storage refers to the data storage consumed in performing a given task, whether primary (e.g.,

in RAM) or secondary (e.g., on a hard disk drive)
In Java to estimate consumed memory there is a Runtime.getRuntime().totalMemory() method, that returns the total amount of memory currently occupied for current objects measured in bytes:
long start = Runtime.getRuntime().totalMemory(); System.out.println("start = " + start); // prints 64487424 int arr[] = new int[100000000]; long finish = Runtime.getRuntime().totalMemory(); System.out.println("finish = " + finish); // prints 464519168

Слайд 6

The RAM model of computation
The RAM model of computation estimate algorithm

according the following rules:
Each simple operation (+, *, –, =, if, call) takes exactly one time step.
Loops and procedures are not considered as simple operations.
Each memory access takes exactly one time step
Example:
for (int i = 0; i < n; i++) { x++; }
Takes n steps

Слайд 7

Big O notation
In Big O notation we are interested in the

determining the order of magnitude of time complexity of an algorithm

Слайд 8

Calculate n-th Fibonacci number (n = 0)
Number of steps: 5

Слайд 9

Calculate n-th Fibonacci number (n = 1)
Number of steps: 6

Слайд 10

Calculate n-th Fibonacci number (n > 1)
Number of steps: 9 +

n + 3(n-1) = 4n + 6

Слайд 11

Fibonacci number

Слайд 12

Time complexities

Слайд 13

More examples

Слайд 14

Counting sort
Sample output:
n = 20
k = 25
A = 12 2 22

24 22 14 6 18 10 6 3 13 17 5 8 13 24 12 22 19
C = 0 0 1 1 0 1 2 0 1 0 1 0 2 2 1 0 0 1 1 1 0 0 3 0 2
A = 2 3 5 6 6 8 10 12 12 13 13 14 17 18 19 22 22 22 24 24

For array A with size n, where upper possible element equals K algorithm is the following:

Слайд 15

Task #1
Implement “counting sort” that sorts an array of integers
Use Math.Random()

or r.nextInt(k) to fill array where K is data value upper limit. Let K = 10000
Implement time measurement for the algorithm. Measure time using System.nanoTime() for array size of 100, 1000, 10000, 100000, 1000000 elements in array.
Vary K from 10000 to 100000 find the dependency of how it affects time consumption
*Extra task. Implement counting part of counting sort in parallel. Compare results