Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Есть ли у вас вопросы?
Содержание
- 1. Есть ли у вас вопросы?
- 2. Краткое содержание предыдущей серииКак в ассемблере происходит
- 3. Краткое содержание этой серииО магииОперации в языке С (продолжение)О-нотация
- 4. Что такое «магия»?В широком смысле – это
- 5. Пример «белой магии»Функция sin. Что возвращает sin?
- 6. Пример «черной магии»Очень сложно понять, что делает эта программа и как она это делает.
- 7. Причины «магии»«Индуизм»Ручная оптимизацияМагические числаОбфускация (намеренное ухудшение читаемости кода)Недокументированные и малоизвестные особенности чего-либоСоревнования волшебников
- 8. «Индуизм» («индусский код»)Не индуизм:if( i > 0
- 9. «Магические числа»Это численные константы, смысл которых не
- 10. Как сделать черную магию белой?// Быстрый вариант
- 11. Что такое интерфейс?Интерфейс – набор входов и
- 12. Интерфейсыdouble sin( double angleInRadians );int work( int
- 13. Хороший интерфейс делает черную магию белой!
- 14. Операции в языке С (продолжение)ЛогическиеБитовые
- 15. Логические операции! – логическое отрицание&& - логическое
- 16. Логическое отрицание - !Результат выражения !A равен
- 17. Логическое ИЛИ - ||Результат выражения А ||
- 18. Логическое И - &&Результат выражения А &&
- 19. Логические операции в ассемблереИх нет! Есть только
- 20. Битовые операции языка С~ - битовая инверсия|
- 21. Битовая инверсия - ~При битовой инверсии каждый
- 22. Битовое ИЛИ - |Результатом битового ИЛИ будет
- 23. Битовое И - &Результатом битового И будет
- 24. Битовое исключающее ИЛИ (XOR) - ^Если значение
- 25. Слайд 25
- 26. СдвигиСдвиги бывают:«просто» сдвиги – они же «логические»
- 27. Сдвиг влево -
- 28. Сдвиг вправо - >>
- 29. Примеры сюрпризовint a = -1 > 4; - implementation defined
- 30. Сюрприз в сюрпризеОписания сдвигов отрицательных чисел появились
- 31. Рассмотрим два алгоритма сортировкиСортировка пузырькомСортировка выбором
- 32. Какой из них быстрее?А если взять другой
- 33. Как узнать, какой алгоритм быстрее?Написать программу и
- 34. Теоретический анализ?Какая самая долгая операция в алгоритме?Какая операция выполняется наибольшее количество раз?От чего зависит это количество?
- 35. Теоретический анализ?
- 36. Теоретический анализ?
- 37. Теоретический анализ?Абстрагироваться от «железа»Абстрагироваться от входных данныхПолучается
- 38. А можно сортировать быстрее?
- 39. Скачать презентанцию
Краткое содержание предыдущей серииКак в ассемблере происходит сравнение?Как используется результат сравнения?Что такое «условное исполнение»?Как в ассемблере осуществляется ветвление?
Слайды и текст этой презентации
Слайд 2Краткое содержание предыдущей серии
Как в ассемблере происходит сравнение?
Как используется результат
сравнения?
Слайд 4Что такое «магия»?
В широком смысле – это «что-то непонятное».
Строгой
классификации не существует.
Условно:
белая магия – результат действия полностью понятен, но
не понятен механизмчерная магия – результат действия понятен не полностью или вообще ничего непонятно
Слайд 5Пример «белой магии»
Функция sin. Что возвращает sin?
Синус угла.
А как
она его вычисляет?
Правильно.
Если вас устраивает результат «белой магии» (точность,
скорость и т.д.), то понимать ее механизм не обязательно.
Слайд 7Причины «магии»
«Индуизм»
Ручная оптимизация
Магические числа
Обфускация (намеренное ухудшение читаемости кода)
Недокументированные и малоизвестные
особенности чего-либо
Соревнования волшебников
Слайд 8«Индуизм» («индусский код»)
Не индуизм:
if( i > 0 && i
100 )
Индуизм:
if( i.toString().length() == 2 )
Стремление писать код кривым, неочевидным,
неестественным способом (жаргонное обозначение).
Слайд 9«Магические числа»
Это численные константы, смысл которых не ясен.
#define SPEED_MAX 59
void
setSpeed(int speed)
{
if(speed > SPEED_MAX)
return;
...
}
void setSpeed(int speed)
{
if(speed > 59)return;
...
}
Слайд 10Как сделать черную магию белой?
// Быстрый вариант функции 1/sqrt.
//
Быстр при аппаратной поддержке плавающей арифметики
float fastInverseSqrt( float number )
{
long
i;float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}
Слайд 11Что такое интерфейс?
Интерфейс – набор входов и выходов черного ящика;
их свойства, возможные диапазоны и т.д.
В зависимости от области интерфейс
может быть разным.
Слайд 12Интерфейсы
double sin( double angleInRadians );
int work( int a, int b,
int * с );
// зависит от трех глобальных переменных
//
возвращает значение -1, если нет ошибок// переменная с не нужна уже второй год,
// но ее забывают убрать
Хороший интерфейс:
Плохой интерфейс:
Слайд 15Логические операции
! – логическое отрицание
&& - логическое И
|| - логическое
ИЛИ
Т.к. тип bool был введен только в С99, все логические
операции используют тип int.Поэтому для них 0 – это ложь, а любое другое число – истина.
Слайд 16Логическое отрицание - !
Результат выражения !A равен нулю, если А
не равно нулю
и равен единице, если А равно нулю.
Выражение !A эквивалентно выражению 0==A.
Слайд 17Логическое ИЛИ - ||
Результат выражения А || B равен нулю,
только если оба аргумента равны нулю, во всех остальных случаях
результат равен единице.
Слайд 18Логическое И - &&
Результат выражения А && B равен единице,
только если оба аргумента не равны нулю, во всех остальных
случаях результат равен нулю.
Слайд 19Логические операции в ассемблере
Их нет! Есть только битовые.
Все операции, которые
называются «logical» в тех. описании, являются битовыми.
Логические операции языка С
превращаются в несколько ассемблерных команд.
Слайд 20Битовые операции языка С
~ - битовая инверсия
| - битовое ИЛИ
&
- битовое И
^ - битовое исключающее или (XOR)
>> - сдвиг
вправо<< - сдвиг влево
Все битовые операции выполняются над двоичными представлениями чисел.
В языке С битовые операции определены только для целых чисел!
Слайд 21Битовая инверсия - ~
При битовой инверсии каждый бит двоичного представления
аргумента меняется на противоположный (инвертируется).
Размер (в байтах) результата операции
равен размеру аргумента, поэтому результат зависит от типа!Примеры:
uint8_t A = 5; // A = 0000 01012 = 510
A = ~A; // A = 1111 10102 = 25010
uint16_t B = 5; // B = 0000 0000 0000 01012 = 510
B = ~B; // B = 1111 1111 1111 10102 = 6553010
Слайд 22Битовое ИЛИ - |
Результатом битового ИЛИ будет число, каждый бит
которого является результатом булевой операции ИЛИ между соответствующими битами аргументов.
Коротко: если бит равен 1 в любом из аргументов – он равен 1 в результате.
A |= B эквивалентно A = A | B.
Битовое ИЛИ удобно использовать для установки отдельных битов в единицу: a |= 1;
Слайд 23Битовое И - &
Результатом битового И будет число, каждый бит
которого является результатом булевой операции И между соответствующими битами аргументов.
Коротко: если бит равен 0 в любом из аргументов – он равен 0 в результате.
A &= B эквивалентно A = A & B.
Битовое И удобно использовать для обнуления отдельных битов:
a &= ~1;
Слайд 24Битовое исключающее ИЛИ (XOR) - ^
Если значение одного бита у
аргументов разное – то результат равен 1.
A ^= B эквивалентно
A = A ^ B.Битовое исключающее ИЛИ удобно использовать для инверсии отдельных битов:
a ^= 1;
Слайд 26Сдвиги
Сдвиги бывают:
«просто» сдвиги – они же «логические» (без учета знака)
арифметические
(с учетом знака)
циклические
Какие же сдвиги в языке С?
Не циклические.
Слайд 29Примеры сюрпризов
int a = -1
behaviour
int a = 1
a = 1 << -2; - undefined behaviourint a = 1 >> -3; - undefined behaviour
int a = -1 >> 4; - implementation defined
Слайд 30Сюрприз в сюрпризе
Описания сдвигов отрицательных чисел появились в стандарте слишком
поздно.
Программисты успели написать достаточно кода, где такие сдвиги используются!
Зачем?
Для получения
битовых масок с заданным числом нулей удобно сдвигать -1 (если он в доп. коде)Но так делать не надо! Сдвигайте лучше ~0u
Слайд 32Какой из них быстрее?
А если взять другой массив?
А если взять
другой компьютер?
А если массив будет гораздо, гораздо больше?
Слайд 33Как узнать, какой алгоритм быстрее?
Написать программу и запустить?
но ее можно
написать с ошибками
на разных компьютерах скорость будет разной
на разных исходных
данных скорость будет разнойна разных запусках скорость может быть разной!
Слайд 34Теоретический анализ?
Какая самая долгая операция в алгоритме?
Какая операция выполняется наибольшее
количество раз?
От чего зависит это количество?
Слайд 37Теоретический анализ?
Абстрагироваться от «железа»
Абстрагироваться от входных данных
Получается т.н. «О-нотация» (Big-Oh
notation):
Время работы алгоритма выражается как функция от размера входных данных
NИгнорируются константные коэффициенты
Остается только старший порядок
Очень грубое объяснение! Подробнее см. «алгоритмическая сложность», «теория алгоритмов»
