ADS:lab session #2 - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему ADS:lab session #2. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ADS:lab session #2 24, August 2015 Kamil Salakhiev

Слайд 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 Each tick is 10-9s long (for usual CPU frequency 1-3GHz) In CPU it converts to elapsed nanoseconds from some moment (first CPU launching, last CPU launching…) In Java to get access to it System.nanoTime() method exists: long startTime = System.nanoTime(); // ... the code being measured ... long estimatedTime = System.nanoTime() - startTime;

Слайд 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)

Слайд 9

Описание слайда:

Calculate n-th Fibonacci number (n = 1)

Слайд 10

Описание слайда:

Calculate n-th Fibonacci number (n > 1)

Слайд 11

Описание слайда:

Fibonacci number For n = 0 Number of steps: 5 For n = 1 Number of steps: 6 For n > 1 Number of steps: 4n – 6 In Big O notation we take the highest complexity in terms of order, remove constants and variables with order lower than the highest one. Thus:

Слайд 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

Слайд 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

Слайд 16

Описание слайда:

Optional homework Make a report of done work in LaTex: Function graph of time/size(K) (memory) Your code (use package: listings) Your computer configuration: Processor, number of cores, frequency Comparison with parallel sorting - vary number of threads. Discuss the performance, your ideas

Теги session

Похожие презентации