Лекция 7 (1160840)

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

Текст из файла

12

Лекция 7.

На прошлой лекции мы рассмотрели регулярные и комбинированные типы данных. Какие еще составные типы данных есть в современных ЯП? Классы – это по определению средства создания новых типов данных, следовательно, в нашей классификации они относятся не к базовым средствам, а к средствам развития, встроенным в язык.

А пока поговорим про базис. Какие еще составные типы данных присутствуют в языках программирования? Вспомним язык Pascal. Кроме записей и массивов, там присутствуют и такие понятия, как множества и файлы.

Множества и файлы

Формально эти типы данных встроены в язык. В стандарте Паскаль файл был единственным средством ввода-вывода (это была часть виртуальной машины Паскаля, файлы были встроены в язык «традиционно» еще начиная с Фортрана)

Замечание. Даже то, что мы называем стандартной процедурой языка Паскаль – writeln, например – на самом деле не стандартная процедура.

Вся языки, начиная с Фортран, Алгол и Cobol, имели встроенные средства ввода-вывода. Первый язык без встроенных средств ввода-вывода – Cи.

(Так как Си – «потомок» ассемблера, где IN и OUT были машинными командами, а собственно средств ввода-вывода не было).

Стандарт Pascal:

file of T; //такие конструкции языка были ориентированы на устройства типа магнитной ленты. Естественным образом, при переносе языка на интерактивный ввод-вывод возникли проблемы.

Итог: попытка реализовать концепцию ввода-вывода на уровне самого языка программирования излишняя и вредная, гораздо больше все зависит от самой операционной системы. Чтобы сделать ввод-вывод независимым от ОС и переносимым, введена была концепция стандартного ввода-вывода (стандартные библиотеки, которые должны были быть реализованы самой ОС).

Множество – как тип данных, характеризуется

1. набором однотипных элементов

2. Операциями:

• Принадлежности

• Объединения(s1+s2)

• Пересечения(s1*s2)

• Вычитания(s1-s2) или s1/s2

[a1, a2, …, an]

Добавление элемента в множество на языке Pascal

[x]+S

Удаление

S-[x]

Один из наиболее распространенных примеров на множества в учебнике по Pascal – поиск простых чисел. Наиболее известный алгоритм поиска простых чисел: «решето Эратосфена» (Заносим в множество все числа от 2 до N. Выбрасываем по очереди все числа, которые делятся на минимальное число. А если надо – и само число. Повторяем эти шаги до тех пор, пока полученное множество не будет равно множеству, полученному на предыдущем шаге.)

Проблема в том, что алгоритм будет бессмысленным – ведь и без него человек легко может назвать простые числа быстрее, чем напишет программу. Ели же мы хотим, к примеру, найти все простые числа от 2 до 1024 – то в данном случае Паскаль бы нам не помог - таких больших множеств в нем попросту не было. Мощность множеств (основанных, естественно, на дискретных типах данных) зависела от реализации, и размер множеств на разных машинах колебался от 16 до 128.

Очевидно, что множества реализовывались при помощи битовой шкалы, напрямую связанной с размерами машинного слова: 16, 32, 64. Но не больше. Ведь если битовые шкалы будут иметь размер целого числа, то все операции над множествами сведутся к побитовым операциям. (+, | * & ). Более того: ни в одном языке операций с множествами как таковых нет, их заменили побитовые операции.

(Modula-2)

SET OF T;

X: BITSET;

Зачем использовать побитовые операции в языке программирования? Ответ прост: манипулировать с битами внутри числа необходимо для работы с портами ввода-вывода. Ведь каждый порт ввода/вывода – это независимая совокупность битов, которая управляется отдельно.

Интересна эволюция понятия множества:

В Modula-2 остался SET OF T и появился BITSET, а также 2 псевдопроцедуры:

INCL(S, X)

EXCL(S, X)-

реализованные при помощи побитовых операций. (Добавляет и удаляет элемент Х в множество S.)

Из Оберона SET OF T исчез. Там «обязан был быть» диапазон [1..K]

Оберон отличается от Модулы-2 отсутствием диапазона и перечислимого типа данных, поэтому в нем остался только BITSET – для того, чтобы заменять собой побитовые операции.(INCL и EXCL там остались)

Что же в общем случае представляет собой множество? Множество – некая разновидность таблицы. С появлением побитовой шкалы накладываются сильные ограничения на побитовый тип данных. Каковы получившиеся реализации понятия множества? Все зависит от 1) – мощности множества, 2) –от того, какие элементы содержит множество

Побитовая шкала эффективна в случае полностью упорядоченного и «плотного»

набора ключей (когда для любого бита существует отображаемый в него элемент).

Итог:

Мы не можем выбрать оптимальный вариант для реализации структуры множества. Каковы соответствующие типы данных в различных языках?

С++

В С++ множество «ушло» в стандартную библиотеку языка(STL: map, set, multiset)

Про STL-ную реализацию этих структур известно, что для set операция принадлежности должна иметь логарифмический порядок сложности (должна обладать сбалансированным деревом поиска). Структуры map и set в С++ реализованы таким образом, чтобы работа с ними давала результат со скоростью, зависящей только от количества элементов в контейнере и не зависящей от множества ключей и от их типа. Главное, чтобы ключи были упорядочены.

Java

Также есть set, map и multiset, реализованные в виде битовых шкал. Пользователь также может реализовывать свои алгоритмы.

Что происходит с развитием типов данных? Они уходят в стандартные библиотеки языков.

Итог

В некоторых (специальных) языках программирования, сложные реализации встроены в язык.

Пример:

SETL – только множества

PERL/PHP (существуют встроенные Map-ы – ассоциативные массивы, в которые можно добавить и удалить элемент.) – языки для обработки и генерации текстов.(PERL - изначально создавался для генерации большого количества config-файлов - все они были текстовыми)

А в универсальных языках программирования, как мы уже поняли, все мало-мальски сложные структуры ушли в стандартные библиотеки. Заменителями конструкций, подобных по сложности множествам, в данных языках служат интерфейсы, которым должны удовлетворять соответствующие структуры данных. А посему в данных языках остались только массивы, структуры и классы.(?)

Строки

С одной стороны – нетривиальный тип данных, внешне похожие на массивы символов, но не являющиеся ими ни в одном современном языке.

Delphi, C#, Java, C++

Отвлечение.

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

1986 год - надо было выпускать релиз С++  потребность «подрубать концы»

 альтернатива: что реализовать: шаблоны или множественное наследование

Страуструп выбрал множественное наследование.

После 1986 года С++ и его компилятор стали официально распространяться. Компилятор вскоре перестал быть единственным. Другие разработчики стали посылать предложения об исключениях и шаблонах. Каждый разработчик реализовывал шаблоны по-своему (Майкрософт, кстати, лишь в конце 90-х годов выделил тип данных CString – на его внедрение потребовалось около 15 лет). В С++ понятие строки входит в стандартную библиотеку. В Delphi, C#, Java оно встроены в язык.

std::string

В С++ предусмотрены общие шаблонные контейнеры и в то же время есть тип std::string. В чем специфика строк? Почему они не являются массивами? Почему именно для строк пишутся свои реализации? Каковы характерные операции со строками?

• Конкатенация

• Поиском подстроки

Что для обычных массивов не характерно.

В то же время основная операция для vector-а – индексирование. Применительно к строке в STL тоже есть операция индексирования(vector<char>), возвращающая ссылку на char в отличие от операции индексирования для строк, возвращающей char. Ведь vector<char> - это изменяемая структура, и, если бы не ссылки, то изменять и-тое значение, например, было бы нельзя. А если мы хотим изменить строку, то мы обязаны завести новую строку. Интересен механизм реализации присваивания строк – при этом строки не копируются, реализован механизм подсчета ссылок.

Пример

ASP (Visual Basic. Строки фиксированной длины.) -> ASP.NET(тот же Visual Basic. Строки стали динамические. Реализация строк была оптимальной, но медленной – алгоритм сборки мусора только и делал, что сдвигал кусок памяти.)

Microsoft для превращения строки в массив символов порекомендовал использовать StringBuilder.

Глава 4. Операторный базис ЯП

С «базисной» точки зрения ЯП не сильно отличаются друг от друга.

В любом процедурном языке программирования есть объявления (определения)

и операторы.

Замечание

В С++ присутствует тонкая семантическая разница между двумя понятиями «объявление» и «определение»:

extern int a;//объявление

int a;// определение

)

Пример. В Ассемблере, как мы знаем, существует 3 вида предложений:

-комментарий

-директива

Собственно машинная команда

То, что в ассемблере называли директивой, в иных языках превратилось в объявление.

Традиционно все операторы делились на 3 вида:

1) присваивания

2) операторы ввода/вывода(IO- в современных ЯП их просто нет, они ушли в стандартную библиотеку)

3) операторы управления последовательностью действий – нужны для упорядочивания операторов присваивания(циклы, условные и безусловные переходы, вызовы процедур)

Замечание.

Оператор вызова процедуры «похож» на оператор перехода, более того, во многих языках CALL моделируют «ручками».

Замечание. Арифметика – это не оператор. Все, что выполняет какие-то действия – это операция. Операция по-английски – operator. В С++ он, как мы помним, стал ключевым словом, служащим для переопределения стандартных операций. Оператор от операции отличается тем, что что-то меняет.

Таким образом, операторный базиса оказался до предела узок, и с данной точки зрения все языки еще менее разнообразны, чем с точки зрения описания данных.

Oб операторе goto

Для управления последовательностью действий в блок-схемах удобен был оператор goto. В Fortran был единственный оператор IF(e) M1; M2; M3 – в зависимости от флагов перехода одна из команд М выполнялась. Дейкстра был уверен, что бесконечное использование оператора goto приводит к низкой читабельности программного кода.

Идея Дейкстра: программировать, думая обо все задаче целиком – сложно, поэтому целесообразней перейти к «пошаговому» (структурному) программированию, состоящему из серии последовательных уточнений (до тех пор, пока не дойдем до конструкций языка). С точки зрения Дейкстра, любая управляющая конструкция должна была иметь 1 вход и 1 выход. Оператор goto легко может нарушить данную концепцию.

В Java, к примеру, ключевое слово goto есть (зарезервировано), но не реализовано. Зато есть операторы return, break, continue.

Составной оператор

В нашей классификации отсутствует составной оператор, позволяющий трактовать несколько операторов как один.

Иногда он еще называется блоком.

begin s1; … ; sn end [Паскаль]

{ …………………… } [Си, C++ и другие]

В блоках, как правило, сначала идут объявления (которые, возможно, могут отсутствовать), а затем – операторы (также могут отсутствовать, но чаще все-таки присутствуют).

Существуют языки, где составного оператора нет.

Однако многие «обычные» согласно нашей классификации операторы (циклы, ветвления) – это составные структуры.

Пример:

while B do S //S – «четко» составной оператор [Паскаль]

while(B) S;//Си- подобный язык. Аналогично.

while S do S1; … ; SN END //Модула-2, Оберон

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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