🗊Презентация ADS:lab session #2

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
ADS:lab session #2, слайд №1ADS:lab session #2, слайд №2ADS:lab session #2, слайд №3ADS:lab session #2, слайд №4ADS:lab session #2, слайд №5ADS:lab session #2, слайд №6ADS:lab session #2, слайд №7ADS:lab session #2, слайд №8ADS:lab session #2, слайд №9ADS:lab session #2, слайд №10ADS:lab session #2, слайд №11ADS:lab session #2, слайд №12ADS:lab session #2, слайд №13ADS:lab session #2, слайд №14ADS:lab session #2, слайд №15ADS:lab session #2, слайд №16
Скачать
Вы можете ознакомиться и скачать презентацию на тему ADS:lab session #2. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


ADS:lab session #2 24, August 2015 Kamil Salakhiev
Описание слайда:
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
Описание слайда:
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;
Описание слайда:
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?
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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)
Описание слайда:
Calculate n-th Fibonacci number (n = 0)

Слайд 9


Calculate n-th Fibonacci number (n = 1)
Описание слайда:
Calculate n-th Fibonacci number (n = 1)

Слайд 10


Calculate n-th Fibonacci number (n > 1)
Описание слайда:
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:
Описание слайда:
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
Описание слайда:
Time complexities

Слайд 13


More examples
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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

Скачать

Теги ADS:lab session #2
Похожие презентации
Mypresentation.ru
Загрузить презентацию