Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

p[i] = new Point(); - создаём 1000 объектов + 1000 указателей - большая неэффективность.

Уничтожение: 1001раз освободить.

С#:

P[I]=new Point();

Уничтожение: освободить кусок памяти.

Но появляется проблема, возникающая и с простыми типами данных:

Нам необходим специальный механизм - boxing и unboxing - для простого типа данных существует аналогичный класс (Integer, Int32 для int, Boolean для bool и т.д.). Эти классы-обертки наследуются от Object.

object []p; - массив, который может держать в себе любой объект языка, возможно при помощи ф-ий boxing и unboxing, преобразующих значащие типы в объектные.

Пример:

p[0] = 3 - обёртка объекта 3 в класс (С # производится новый объект типа Int32 и ссылка на этот объект кладётся в массив [0]).

x- имя структуры.

p[0] = x;- упаковка структуры в специальный тд, образуется специальный объект и ссылка кладется в массив.

x = p[0]; // ошибка, производному присвоить базовый нельзя!!!

x = (X) p[0]; // правильно, приведение типа.

х - не объект, это структура.

Обёртка происходит, и когда мы передаём объекты как параметры функции.

void f(Object o);

Параметр- любой тд языка.

Объединения

В записи мы указываем несколько вариантов структуры, располагающихся в одном месте памяти.

Это:

- union (Си)

- записи с вариантами (Паскаль)

В современных ЯП записей с вариантами нет:

Запись с вариантами - постоянная часть и вариантная часть.

Объединения :

• размеченные (в постоянной части выделяется поле - дискриминант, в зависимости от значения которого выбирается вариант, по какому варианту отведена память)

• неразмеченные (поле-дискриминант отсутствует, память может отведена по короткому варианту, а мы считаем, что по самому длинному  залезаем в чужую память ). Существенно понижают надежность.

Паскаль и Модула-2 допускают оба типа, язык Ада - только размеченные( значение дискриминанта меняться не может).

В современных ЯП нет объединений - всё реализуется при помощи наследования:

class P;- постоянная часть

class T1:P; - вариант Т1

class T2:P; - вариант Т2

.......

class T4:P; - вариант Т4

Множества

Множество – контейнер, у которого есть базовый тип Т.

Над множеством определены операции:

- принадлежности,

- добавления,

- исключения,

- объединения,

- вычитания.

Впервые появились в языке Паскаль.

Решето Эратосфена (алгоритм определения простых чисел) - помещаем в решето 1000 чисел (от 0 до 1000) и постепенно выкидываем числа (берём меньшее и выкидываем числа, которые делятся на это меньшее).

X: set of T;

S := S + [x]; - включение в мн-во incl

S := S - [x]; иcключение excl

X in S –принадлежность.

В большинстве реализаций Паскаля множества ограничены размерами 16, 32, 64 (разрядность)  в большинстве реализаций задача работать не будет.

Реализация множеств в Паскале:

Тип Т- дискретный, мощность варьируется 16, 32, 64. тип данных Т сводится в диапазон :

T => 0.. N-1 (любой дискретный тип можно свести)

N - разрядность максимальной ячейки памяти, адресуемой на данной машине.

0 бит –0 элемент…N-1бит - N-1 элемент

1. элемент присутствует

1. нет

0 i N-1

+- побитовое “или”

В связи с простотой подобной реализации операции с множествами сводятся к одной машинной операции ( +- побитовое “или”).

Множества произвольного вида неэффективны, т.к. для любой реализации можно придумать пример его использования, для которого данная реализация будет неэффективна.

В языке Ада множеств уже нет.

Множества похожи на структуру данных Map (таблица) или Dictionary( наличие элемента проверяется по ключу).

Основные понятия множества: содержится элемент или не содержится. Отсюда множество - частный случай таблицы.

Самый эффективный способ реализации таблицы – массив(x[i] ключ- № элемента). Но массивы очень требовательны к размерам памяти (ключ-строкамножество значений- множество слов в данном алфавите).

Следующий способ по эффективности - хэш-таблицы( требует хорошую функцию-расстановки).

Поэтому множества реализуют ещё и в виде двоичных деревьёв (Map'ов - они обязаны давать логарифмическую сложность => они используют деревья).

Для эффективной работы Dictionary(хэш-таблица) каждый объект может переопределить свою функцию(С#) GetHashCode()- функкция-расстановки основана на адресе, которая унаследована ещё от общего класса Object.

Стандартная реализация хэш-таблицы и пользовательская реализация функкции-расстановки. ( в Java есть аналогичная функция).

Усложнение структуры данных приводит к невозможности универсальной эффективной реализации современные яп дают нам некоторые стандартные контейнеры, не включая их в базис языка.

В Си++ стандартной реализации словаря нет (так как там GethashCode для каждого объекта, т.к. нет универсального типа Object).

Тоже самое относится к типу файл (до определенного времени (до С) включались специальные средства ввода/вывода, похожие на процедуры, но таковыми они не являются).

Начиная с языка Си все средства ввода-вывода вынесены в стандартную библиотеку.

Эволюция множеств:

В Паскаль множества есть.

В Модуле-2 множества есть, но они в виде BITSET = SET OF [0...N-1]; // N - разрядность машины

X:BITSET;

i in x;- установлен i-ый бит?

C помощью операций над множествами в этих языках мы манипулируем битами. В С, С++, Java множества не нужны, т.к. есть сдвиги и побитовые операции.

В Обероне остался единственный тип множества SET(аналог BITSET)(т.к. есть только целочисленный тип).

Особый тип данных – строки.

Языки программирования.Лекция 10.26.10.04

Строки

Строка - некоторая последовательность символов. Строки в силу своей специфики нельзя сводить только к массивам символов.

В STL введены шаблоны(хранятся в динамической памяти)

-Vector

-String

Массив значений по сути Vector, но не является специализацией стандартного контейнера

Vector.

Строку от обычного вектора отличает:

-изменчивость.

Самая частая операция со строками - операция конкатенации. Так же часто производится поиск, присваивание, обрезание начала строки. Поэтому реализация строк как массивов оказывается неэффективна.

Строки настолько часто употребляются, что создатели многих языков вынесли их в базис языка.

В Java и в Cи# строки встроены в сам язык:

5 + str- либо преобразование строки в число, либо преобразование целого в строку (конкатенация).

Любой тип- производный от базисного типа Object (ТObject - в Дельфи ), который имеет встроенный метод ToString для перевода в строковый тип, что облегчает перевод в строку. Если компилятор чувствует необходимость в переводе в строку, он вызывает ToString, который можно переопределить.

Для типов данных классов метод ToString возвращает тип этого объекта.

В C++ они вынесены в стандартную библиотеку STL. Преобразования зависят не от компилятора, а от программиста (возможность перекрытия стандартных знаков и т.д.).

Подобные преобразования строкового типа данных интегрированы в Java, потому что реализовать их средствами языка нельзя.

Пример:

ASP, PHP, JSP, ASP.NET - технологии динамической генерации веб-страниц.

Скрипты, написанные на ASP и переписанные на ASP.NET стали работать хуже. В частности, из-за неэффективной работы со строками.

В C# и Java есть специальный класс, оптимизированный под построение строки, - StringBuilder. И есть специальная операция Format, позволяющая эффективно её форматировать.

Глава 3 "Процедурные абстракции"

Абстракции - подпрограммы. К ним относятся - процедуры и функции.

Подпрограмма- есть последовательность однотипных вычислений. Мы можем дать это последовательности имя и вызывать её из программы.

Основное назначение функции - вычисление одного значения. return E - оператор явного возврата.

Целью процедуры является побочный эффект - изменение параметров среды.

Главный оператор - оператор присваивания. И этот оператор имеет побочный эффект - он меняет значение левого операнда.

С этой точки зрения такие языки называют императивными или процедурными.

С современной точки зрения процедура - чёрный ящик, имеющий один вход и один выход. Не важно, какая структура этого ящика. Не важно, с какой точки процедуры выход( при использовании: выход один).

С современной точки зрения (1967 год - Э. Дейкстра) оператор goto - вреден. Структурное программирование - программирование в терминах структур (структура - вещь с одним входом и одним выходом - циклы, условные операторы и т.д.).

Процедуры в современных ЯП - это также структура с одним входом и одним выходом.

Подпрограммы.

Альтернативная вещь – сопрограммы (были популярны в несовременных языках).

1) Подпрограмма

Подпрограмма всегда подчинённая. Главная программа в какой-то точке вызывает подпрограмму. Р начинается с первого оператора, а передает управление, куда скажет главная.

главная программа: подпрограмма :

c all p Р

…

c all p

2). Сопрограмма(сп)

Для сопрограммы понятие главной программы отсутствует.

Есть сопрограмма 1 и сопрограмма 2.

СП 2 вызывает СП1 с первого оператора, потом возврат в СП2. После выполнения нескольких операторов в СП2 управление снова передаётся в СП1, но начиная со следующего оператора за последним выполненным.

Р 1 Р2

.

. .

Вместо оператора вызова используется оператор возобновления - resume

Походит на взаимодействие параллельных потоков.

Есть в Модула-2.

Почему в современных ЯП не используется понятие СП?

1. В некоторых случаях нужна именно подчинённость.

Внешне СП похожи на параллельные процессы, в каждое время может выполняться только одна СП. Вместо СП в современных яп мы используем реальное понятие потока (вместо низкоуровнего понятия)- на базе JVM или на родном понятии потоков, понятие потоков встроено в любую из современных ОС, но программы становятся менее переносимыми, С#- на базе потоков .NET.

Параметризации подпрограмм.

Характеристики

Список файлов лекций