Яп
.pdf
Ошибки вычислений с вещественными числами
•Младший значащий разряд результата каждой операции с плавающей точкой может быть неправильным из-за ошибок округления.
1.Исчезновение операнда - Операнд может исчезнуть, если он относительно мал по отношению с другим операндом.
Предположим, что мы имеем дело с десятичной арифметикой с пятью цифрами, тогда:
0,1234∙103+0,1234∙10-4= 0,1234∙103.
Второй операнд в данном вычислении просто потерялся.
121
Ошибки вычислений с вещественными числами
•Потеря значимости - полная потеря значимости, вызванная вычитанием почти равных чисел. Также возникает, когда результат вычислений невозможно представить в допустимой форме.
•Пусть имеется два числа:
|
floatf1= 0,12342; |
|
floatf2 = 0,12346; |
• B математике |
f2 - f1 = 0,00004 |
•Программа, вычисляющая f2 - f1 в четырехразрядном представлении с плавающей точкой, даст ответ:
0,1235∙100-0,1234∙100 = 0,1000∙10-3
•Потеря значимости встречается часто, т.к. проверка на равенство обычно реализуется вычитанием и последующим сравнением с 0.
123
2/27/2023
Ошибки вычислений с вещественными числами
•Умножение ошибки – многократное увеличение абсолютной погрешности операнда, которая может появиться при использовании арифметики с плавающей точкой, даже если относительная ошибка мала.
•Обычно это является результатом умножения и деления.
•Рассмотрим вычисление х∙х:
0,1234∙103∙0,1234∙103= 0,1522∙105
•и предположим теперь, что при вычислении х произошла ошибка на единицу младшего разряда, что соответствует абсолютной ошибке 0,1:
0,1235∙103∙0,1235∙103= 0,1525∙105.
•Абсолютная ошибка теперь равна 30, что в 300 раз превышает ошибку перед умножением.
122
Ошибки вычислений с вещественными числами
•Сравнивать два вещественных числа НЕЛЬЗЯ.
•«< =» и «<» - нет существенного различия.
•Правильный способ проверки равенства с плавающей точкой состоит в том, чтобы ввести малую величину и затем сравнить абсолютное значение разности с малой величиной.
•При вычислении вещественных чисел всегда происходит округление результата до разрядной сетки, то
f1=x*y/z
f2=x/z*y
f1!=f2
Практическивсегда будутполучаться различные мантиссы.f1-f2!=0
124
31
Особенности вещественных типов с С++
•В большинстве случаев операции над double занимают не больше времени, чем над float - можно использовать double без страха временных затрат.
•операции деления, вычисления корня и математических функций быстрее на float, чем на double.
•сложение, вычитание, умножение и т.п. одинаково для float и double на большинстве процессоров (без использования векторизации).
•для больших массивов лучше использовать float, который занимает меньше памяти, и больше элементов помещается в кэш.
•float лучше использовать, если используется векторизация.
125
Символьный тип
•Символьныйтип – полныйаналог целочисленного.
•Char занимает 1 Байт. Всего 256вариантов.
•При использованиинациональных кодировок могут занимать 2и 5 байта (UTF32).
•Для того, чтобысопоставить числам символыиспользуются
таблицыкодировки– ASCII, UTF, Windows…
•Операциисоответствуют целым числам.
‘a’+5; // пятыйсимвол после a. Результат ‘f’
x < y; // верно если значение, хранящееся в x в таблице кодировки находится раньше значения, хранящегося в y.
127
2/27/2023
Смешанная арифметика
•При выполнении арифметических операций компиляторы стараются приводить результаты к более широкому типу, а затем преобразуют результат к типу переменной, в которую он записывается.
•Лучше везде где можно делать явное преобразование типов самому.
•Следует обращать внимание на типы переменных.
int i=7; |
|
double j=i/2; |
// j=3 |
double k=i/2.0; |
// k=3.5 |
126
Перечисления
•Представляет собой таблицу перечислений.
•Операции выполняются в контексте порядкового номера соответствующих обозначений в таблице
typedefenum {black=0, blue=1, green=2…, white=15} color; color a,b;
a = black;
b = a + 2;// результат = green
•Многие ЯП требуют явной типизации
значений типа перечислений при таких операциях.
128
32
Логический тип (булев)
•Булев тип – частный случай перечислений, где значению false соответствует 0, а все остальное трактуется как 1.
bool a,b; a = true;
b = a + 1; // b == true
b = a – 1; b == false, хотя лучше этому не доверять
int x = 10;
if (x) … // будет выполняться, т.к. условие – истина
• Логические операции в выражениях вычисляются по принципу ленивых вычислений слева направо.
• Нужно упорядочивать так, чтобы наиболее частых вычислений было меньше – если операнд более хорошо предсказуем или быстрее вычисляется, поместите его в выражении первым.
• При смене мест операндов в логических выражениях следует опасаться побочных эффектов, когда одно из подвыражений в определенных
случаях не должно вычисляться.
129
СОСТАВНЫЕ ТИПЫ ДАННЫХ. МАССИВЫ
131
2/27/2023
Подтипы
•Это тип, определенныйна основе уже существующего типа.
•Значения просто ограничены некоторомдиапазону.
Pascal:
type Ttemperature= 0 .. 300;
130
Массивы
•Массив — это структура данных, которая содержит последовательность элементов одинакового типа.
•В состав атрибутов для объекта данных типа массив входят:
•Количество элементов — указывается косвенно, путем задания диапазона изменения индексов.
•Тип данных для каждого элемента — в данном случае он одинаков для всех элементов.
•Список значений индексов, применяемых для выбора элементов — задается в виде набора целых чисел, первое из которых соответствует первому элементу, второе — второму элементу и т. д.
132
33
Массивы
•Фундаментальное свойство массива — время доступа к любому его элементу A[i] не зависит от значения индекса i.
•Индекс первого элемента называют нижней границей (в С – 0, Fortran – 1, в остальных может задаваться программистом), а индекс последнего элемента — верхней границей массива.
•Различают компоновку массива (layout) и размещение массива в памяти (allocation).
•При компоновке задаются относительные адреса элементов массива (относительно адреса 1-го элемента), вычисляются формулы для адресации элементов.
•При размещении определяются действительные машинные адреса элементов и выделяется память.
•Связывание типа индекса массива с переменной массива обычно выполняется статически, но по диапазону индексов связывание происходит иногда динамически.
133
Массивы
•Время доступа к элементу массива— константа.Кол-во команд машинной программы,необходимыхдля вычисленияадреса, не зависит от значения i.
•Значениетекущего индекса должнонаходитьсяв пределах допустимого диапазона.Такая проверка способствует
повышениюнадежности вычислений.Однакореализована она тольков языках Pascal, Ada, Java и C#. В других языках (например,в С и С++) проверка отсутствует в силу специфики организации массивов.
•Некоторыеязыки предусматриваютсредства для инициализациимассивовво времяих размещения в памяти. Языки C, C++, Java и C#:
intlist[]= {3, 4, 8, 79};
•заставляет компиляторсамостоятельноустановить длину массива. Это удобно, но вносит ограничения: такая инициализация лишает систему возможностиобнаруживать ошибки выхода индексов за пределыкорректного диапазона.
135
2/27/2023
Массивы
•Если base — адрес начала массива, w — длина элемента массива, то адрес i-го элемента массива равен:
A [i] = (base – low × w) + i×w
•где (base – low × w) — вычисляется предварительно, а (i ×w) — вычисляется во время выполнения программы (поскольку i изменяется).
•В языке С первый элемент массива имеет индекс 0, поэтому адрес i-го элемента массива вычисляется по упрощенной формуле:
A [i] = base + i× w
134
Разновидности массивов. Статические
•Статические массивымассив со статическим связыванием по диапазонаминдексов и таким размещениемв памяти, которое происходитдо начала работы программы.
•Статические массивы достаточноэффективны,поскольку отсутствуют затраты времени как на динамическое размещение в памяти, так и на удаление из нее.
•Недостатком является то, что память ими занимается на все время выполненияпрограммы.
•В языках C и C++ статическими являются массивы, которые объявляются в функциях со спецификатором static.
136
34
Разновидности массивов. Явные стековые массивы
•Явные стековые массивы - массив со статическим связыванием по диапазонам индексов и таким размещением в памяти, которое происходит по итогам обработки объявления в ходе выполнения программы.
•Массив удаляется из стековой памяти по завершению работы программы (подпрограммы).
•Повышают эффективность использования памяти: большой массив одной подпрограммы может занимать ту же область памяти, что и большой массив другой подпрограммы, причем так может продолжаться до тех пор, пока обе подпрограммы не окажутся активными одновременно.
•К недостатку следует отнести дополнительные затраты времени на размещение и удаление массива из памяти.
•Массивы, объявленные в функциях C и C ++ без спецификатора static, считаются явными стековыми
массивами. 137
Разновидности массивов. Явные динамические массивы
•Явные динамическиемассивысвязываниеи по диапазонам индексов,и по памятипроисходитпосле размещения в памяти.
•Связываниепо индексами памятипроизводитсяпо запросу программыи в течение ее выполнения,но памятьвыделяется в куче, а не в стеке.
•Преимуществомявляетсягибкость:изменениеразмера массивавсегдаостаетсяпроблемой.
•Недостатокна размещениев кучетратитсявремени больше, чем на размещение в стеке.
•ЯзыкиC и C++- используютсястандартныебиблиотечные функцииmalloc и free,которые являютсяоперациямидля размещенияв куче и удаленияиз неесоответственно.
•Для управлениякучейприменяютоператоры newи delete
139
2/27/2023
Разновидности массивов. Стековые массивы
•Стековыемассивымассив с динамическимсвязыванием по диапазонаминдексов и динамическимразмещениемв памяти, которое происходитв ходе обработки объявления.
•Связанность диапазонов индексов и размещение массива в памяти сохраняются в течение всей жизнипеременной.
•Главным преимуществом этой разновидности массивов по сравнению с двумя предыдущимисчитается гибкость — не нужно заранее знать (до моментаиспользования)размер массива.
138
Разновидности массивов. Динамические массивы
•Динамические массивымассив с таким динамическим связыванием по диапазонаминдексов и размещению в памяти, которое повторяется многократнов течение всего жизненногоцикла массива.
•Преимущество: максимальная гибкость. Массив по мере необходимостиможетрасти или сжиматься прямов ходе выполненияпрограммы.
•Недостаток: на многократное размещение (удаление) в куче тратится много времени (и все оно приходитсяна период вычислений).
List<String> stringList = new List<String>(); // |
С# |
stringList.Add("Liza"); |
C# |
Java - ArrayList |
|
140
35
Массивы в Perl
•Имена всех массивов должны начинаться с символа @
•но поскольку элементы массива являются скалярными величинами, их имена предваряются знаком доллара $.
@list |
# массив list |
$list[1] |
# обращение ко второму элементу массива |
•На элемент массива в Perl можно сослаться при помощи отрицательного индекса. Отрицательное значение индекса обозначает номер позиции элемента с конца. Индекс –1 соответствует последнему элементу массива, –2 — предпоследнему и т. д.
$list[-2] # адресует предпоследний элемент.
•Ссылка на несуществующий элемент массива в Perl возвращает значение undef, но сообщение об ошибке не формируется.
•push – добавить один и более элементов в конец массива
•unshift - добавить один и более элементов в начало массива 141
Прямоугольные массивы
•Прямоугольный массив — это многомерный массив, в котором все строки и столбцы имеют одинаковое количество элементов.
143
2/27/2023
Массивы в разных языках
•Массивы в JavaScript могут быть разреженными, в которых значения индексов не образуют непрерывную последовательность.
list[70] = 47; list имеет 13 элементов и длину 71.
;Элементы с индексами 12..69 не определены, для их
;хранения память не нужна
•Массивы в языках Python, Ruby и Lua увеличивают или с помощью методов для добавления элементов, или путем соединения с другими массивами.
•Python – списки. Объекты могут иметь любые типы, массивы здесь неоднородны.
•Операции для конкатенации массивов (+) и определения вхождения (членства) элемента (in).
•Cодержит две различные операции сравнения: одна определяет, ссылаются ли две переменные на один и тот же объект (is);
другая проверяет равенство всех объектов, входящих в указанные объекты, независимо от глубины вложенности (= =). 142
Массив массивов
•Массив массивов — это многомерный массив, в котором не требуется, чтобы длины у строк были одинаковыми. Еще называют не выровненными массивами.
•Например, не выровненная матрица может состоять из трех строк, одна из которых содержит пять элементов, другая — семь элементов, а третья — двенадцать элементов.
int[][] jaggedarray2 = new int[][]
{
new int[] {1,3,5,7,9}, new int[] {0,2,4,6}, new int[] {11,22}
};
•Сечение — это подструктура массива, которая сама является массивом.
•Сечениедля трехмерногомассива – двумерный,для двумерного– одномерный.
144
36
Ассоциативный массив
•Ассоциативный массив — это неупорядоченное множество элементов данных, индексированных таким же количеством величин, которые называются ключами.
•Каждый элемент ассоциативного массива несет в себе ключ и значение. Ключ является единственным средством доступа к значению.
Perl:
%age = ( "Liza" => 27, "Alex" => 18, "Nataly" => 30, "John" => 41); $age{"Nataly"} = 33; // обращение к элементу
delete $age{"John"}; // удаление
@age= (); // обнуление хэша
If (exists $age { "Liza"}) ... // проверка существования хэша
•Ассоциативные массивы в Python называют словарями.
•В PHP применяются как обычные, так и ассоциативные массивы. Язык обеспечивает функции как индексированного, так и
хешированного доступа к элементам. |
145 |
Строки
•Строка — это просто последовательностьсимволов.
•В языках программирования строки представляются или в виде отдельногоэлементарноготипа, или в виде массивов из элементов символьноготипа.
•Различают три разновидностистрок:
1.строки фиксированной длины
2.строки переменнойдлины,не превосходящей заданного максимума(строки с ограниченнойдинамическойдлиной)
3.неограниченныеподлине строки (строкис неограниченнойдинамическойдлиной).
147
2/27/2023
СОСТАВНЫЕ ТИПЫ ДАННЫХ. СТРОКИ
146
Строки фиксированной длины
•строки фиксированной длины (строки со статической длиной) - поддержка на аппаратном уровне.
•К данной разновидности относятся строки в языке Python, неизменяемые объекты класса String в Java, а также строковые классы из стандартной библиотеки классов C++, встроенный класс String в Ruby, средства из библиотеки классов .NET, доступные в языкахC# и F#.
Правила:
1.значениями могут быть строки символов только этой длины;
2.присваивание строки символов с длиной, отличной от заданной, приводит к ее усечению (если длина больше заданной) или к добавлению пробелов в ее конец (если длина меньше заданной).
148
37
Строки переменной длины
•Строки переменной длины, не превосходящей заданного максимума (строки с ограниченной динамической длиной).
•Подобные строки приняты в языках C и C++ (строки в стиле C). Правда, вместо объявления длины строки здесь используетсяограничивающий нуль-символ \0, который помещаетсяза последним символом строки.
Правила:
1.в программе указываетсямаксимальная длина строки;
2.фактические строки могут иметь меньшее количество символов;
3.текущая длина строки может меняться,но при превышении максимума лишние символы отсекаются.
149
Операции со строками
•Конкатенация(объединение). Конкатенацией называют операцию, объединяющую две короткие строки в одну более длинную.
•Операцииотношенийнад строками.К строкам можно применятьобычные операции отношения:равно, больше- чем,меньше-чем.
•Операцииосновываются на правиле лексикографического
(алфавитного)упорядочения символов:строка Х меньше строки Y, если первыйсимвол в Х меньше первого символа в Y; если эти символы совпадают, то второй символ Х должен быть меньше второго символа Y.
•Выделение подстрокипри помощи индексов. В этом случае предполагается,что строка представляется как символьный массив. Результатомоперации становится набор символов, позиции которых указаны индексами, являющимися аргументамиоперации: первый индекс задает первую позицию, а второй —последнююпозицию подстроки.
151
2/27/2023
Неограниченные по длине строки
•Неограниченныепо длинестроки (строкис неограниченнойдинамическойдлиной).
•обеспечивается максимальная гибкость, но существенно возрастают затраты на их динамическоеразмещение в памяти, а также на удаление из памяти.
•Такие строки применяютв JavaScript, Perl и стандартной библиотекеC++.
150
Операции со строками
•Выделение подстроки на основе сопоставления с образцом.
•Например, она располагается после символа 'a', или после десятичной точки, или после фразы "Пароль".
•Аргументы:
1.специальная структура данных, которая определяет вид искомой подстроки – регулярное выражение.
2.исходная строка, в которой будет выполняться поиск подстроки, соответствующей заданному образцу.
•Поиск любого адреса электронной почты в доменах yahoo.com, hotmail.com и gmail.com.
(\W|^)[\w.+\-]{0,25}@(yahoo|hotmail|gmail)\.com(\W|$)
152
38
СОСТАВНЫЕ ТИПЫ ДАННЫХ. СТРУКТУРЫ И ЗАПИСИ
153
Структуры и записи
Доступ к элементам структур обеспечивается с помощью:
•операции-точки <имя_структуры>.<имя_элемента>;
•операции-стрелки <указатель_структуры> –> <имя_элемента>. struct block {
intx; float y; };
intmain (){
struct block a, ptr_a = &a; a.x = 5;
ptr_a –> y= 4.5; }
•В памяти запись может храниться в единой области, в которой поля расположены последовательно.
•Формула вычисления адреса i-го поля записи R имеет вид:
155
2/27/2023
Структуры и записи
•Записи позволяют сгруппировать переменные, относящиеся к объекту, и рассматривать их как единый модуль.
Запись - это неоднородная структура данных, в которой отдельные элементы идентифицируются именами. Атрибуты объекта данных типа:
1)количество полей;
2)тип данных для каждого поля;
3)имя для обозначения каждого поля.
154
Структуры и записи
•Допускаетсявзаимноевложение массивови записей: structТипПреподавателя{
int Ид;
int Возраст; float Зарплата; char Кафедра;
} Преподаватель[250];
•В языкахPython и Ruby записимогутбыть реализованыкак хеши, которыесами по себе могутбыть элементамимассивов.
•В языкахJavaи C#записи могутопределяться как элементы данных в классах,с вложенными записями,которые рассматриваютсякак вложенные классы.Элементы данных в таких классахслужатполямизаписи.
156
39
СОСТАВНЫЕ ТИПЫ ДАННЫХ. МНОЖЕСТВА
157
Множества в Python
A = set('qwerty') |
|
users = {"Tom", "Bob", "Alice"} |
|
A = {1, 2, 3} |
|
user = "Tom” |
|
for num in A: |
|
if userin users: |
|
print(num) |
|
users.remove(user) |
|
A.add(4) # {“1”, ”2”, ”3”, ”4”} |
print(users) # {"Bob", "Alice"} |
||
|
|
|
|
A | B |
Возвращает множество, являющееся объединением множеств A и B. |
||
A.union(B) |
|||
A |= B |
Добавляет в множество A все элементы из множества B. |
||
A.update(B) |
|||
A & B |
Возвращает множество, являющееся пересечением множеств A и B. |
||
A.intersection(B) |
|||
A &= B |
Оставляет в множестве A только те элементы, которые есть в множестве B. |
||
A.intersection_update(B) |
|||
A - B |
Возвращает разность множеств A и B (элементы, входящие в A, но не входящие |
||
A.difference(B) |
в B). |
|
|
A -= B |
Удаляет из множества A все элементы, входящие в B. |
||
A.difference_update(B) |
|||
A ^ B |
Возвращает симметрическую разность множеств A и B (элементы, входящие |
||
A.symmetric_difference(B) |
в A или в B, но не в оба из них одновременно). |
||
A ^= B |
Записывает в A симметрическую разность множеств A и B. |
||
A.symmetric_difference_update(B) |
|||
A <= B |
Возвращает true, если A является подмножеством B. |
||
A.issubset(B) |
|||
A >= B |
Возвращает true, если B является подмножеством A. |
||
A.issuperset(B) |
|||
A < B |
Эквивалентно A <= B and A != B |
159 |
|
A > B |
Эквивалентно A >= B and A != B |
||
|
|||
2/27/2023
Множества
•Множество — это структура, содержащая неупорядоченный набор различных значений. Все элементы множества должны быть одного и того же простого типа.
Pascal
var A: set of [1 .. 3];
разрешены подмножества: [ ], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
Множество из n элементов реализуется как битовый вектор длины n. Длина этого вектора обычно кратна длине машинного слова.
СОСТАВНЫЕ ТИПЫ ДАННЫХ. КОРТЕЖИ
160
40