лекции (2015) (1160856), страница 5
Текст из файла (страница 5)
Срабатывает приприсваивании элемента массива (A[i] = 50)При этом время доступа константное, в отличие от словаря, где время доступа обычно O(logN).Также заметим, что суть массива отражает принципы фон Неймана:- Однородность (все хранимые данные имеют один и тот же тип)- Линейность (время доступа к элементу не зависит от ‘i’)С массивами иногда может появиться неэффективность. Например, когда массив выделяется вдинамической паамяти, на момент трансляции адрес массива не известен, а известна ссылка.Возникают расходы на разыменование и сборку мусора.В Паскале все адреса массива известны в момент трансляции.
Память используется эффективно,но и длины массивов статичны. Некоторые же языки позволяли выделять массив в стековой памяти.Например, Ada:procedure P(N:integer) isX: array range 1..N of integer;Y: array range 1..2*N of real;begin…end15Андрей ([872-879], завершено)Выделяется память в момент входа в процедуру и освобождается в момент выхода(квазистатические массивы - не могут меняться после создания). Но мы все-равно не знаем, гдеименно в стеке лягут переменные, но зато мы точно всегда знаем offset.Из-за такого вида динамических массивов нужно дополнительно иметь смещение относительнокадра стека, но они все-равно делигированные..Постоянная борьба эффективность/гибкость.Неограниченный массив АдаВ Аде есть неограниченный тип данных.Общее объявление типа массива:type LARR is array INDEX range L..R of T;INDEX - тип индекса, L,R - константные выражения типа индекса, T - тип значенияНеограниченный массив:type ULARR is array Integer range <> T;На самом деле все фуфло, потому что при объявлении переменной размер все-равно надо указать:y : ULARR; ← нельзяz : ULARR range 1..N; ← можно, если N - constw : ULARR range 0..N-1;Единственная плюшка - переменные z и w будут формально одного типа, и поэтому с ними можноделать присваивания, если их длины совпадают z := w.Неограниченный тип удобен для определения процедур, где аргументом является массив, так как поопределению адрес статически мы не знаем.Во всех операциях с неограниченными типами включается квазистатический контроль (либо самкомпилятор, если знает все параметры, проверяет операцию, либо вставит проверку)Работа с массивами Адаfunction Sum(A: ULARR) return T;count : T := 0.0;beginfor i in A’RANGESum := Sum + A(i) ← Индексация круглыми скобкамиend;return count;end Sum;Атрибутные функции массивов Ада: A’LENGTH, A’UPPER, A’LOWER, A’RANGEМассивы в Модуле-2Открытый массив:TYPE A: ARRAY of T;Обычный массив:TYPE B: ARRAY[L..R] of T;При этом переменные типа А могут быть только формальными параметрами процедур и функций(их нельзя создавать)16PROCEDURE Sum(A:ARRAY OF REAL) : REAL;VAR Res: REAL;I : INTEGER;BEGINRes := 0.0;FOR I := 0 TO HIGH(A) DORes := Res + A[I]END;RETURN Res;END Sum;Модула-2 упоротый язык, и в нем нельзя получить нижнюю границу массива, только верхнюю(HIGH(A)).Массивы в ОберонеЕсть многомерные открытые массивы.
Они могут использоваться только в качестве формальныхпараметров функций.Нет беззнакового типа. Нет диапазонов.Массив задается:B : ARRAY N of real; ← N - длина (индексы будут от 0 до N-1)Массивы в JAVA и C#Современные языки имеют референциальную модель (все объекты составных типов хранятся вдинамической памяти)T[] a = new a[N]; ← Длина нужна только для инициализацииПоэтому обращение a[i] всегда поразумевает два разыменования.Это квазастатические массивы: длина постоянна, но задается в момент инициализации.(Это нужно для эффективности. Потому что алгоритм расширения/сужения массива неуниверсалени поэтому не входит в базис)В плюсах есть vector, у которого операция erase, удаляющая все элементы массива, не производитреаллокацию, т.е. зарезервированное место сохраняется.Массивы в динамических языках (JS, Python)JavaScriptМассив - это объект, прототипом которого является Array.
По сравнению с обычными объектами,массив имеет дополнительное поле length, содержащее длину, а также набор специфичных функцийвроде push, map и т.п. При обработке массива учитываются только поля с целочисленнымиключами.Про объекты в JS ниже по текстуvar a = [1,2,3];console.log( a.length ); // 3a.length = 4;console.log( a ); // [1,2,3,undefined]Полностью динамический массив, как в питоне.Python17Есть обобщенное понятие последовательности. Последовательность - это такая штука, которуюможно индексировать.Есть списки, которые на самом деле массивы, но называются списками.a = [1,”str”,3] // непрерывная область памяти, константная по времени индексацияСписки полностью динамические. Можно удалять/вставлять элементы. Реаллокация происходитавтоматически. Можно смешивать разные типы данныхЕсть кортежи (tuple)a = (1,2,”str”) // неизменяемая длина, может быть ключом в словареЕсть строкиa = “str” // неизменяемая длина, при модификации строк просто копируется в новое место, можноиспользовать как ключ в словареСтрока - это не просто массив чаров, а отдельный объект со своими функциями.Есть словариa = {‘a’: 1}Ассоциативный массив, реализован в виде хеша.
При этом все ключи должны быть одного типаЕсть генераторы. Генератор - это такая штука, которая создает последовательность на ходу понеобходимости. (Как потоки в Лиспе)def natural():i = 0while True:yield ii += 1natural() - создает генератор, который создает бесконечную последовательность натуральныхчисел. Как все остальные последовательности, можно использовать в циклах.Со всеми последовательностями можно делать следующее:s.index(obj) ← Поиск первого входждения элемента в последовательностьs.count(obj) ← Подсчет количества вхождений элемента в последовательностьs[2] ← Индексацияs[2:3:1] ← Вырезка (slice) со 2го по 3й элемент с шагом 1.В Python range(right), range(left, right), range(left, right, step) - это генераторысоответствующих последовательностей (В Python 2 - функции.
создающие списки)В Python нет цикла for, есть только foreach, который называется for. Цикл обязательно принимает навход последовательность. Через foreach можно имитировать обычный for:for x in range(left, right, step) в ПитонеЭквивалентноfor(int x = left; step > 0 ? x < right : x > right; x += step) в СяхПоследовательности в Java и C#В Java и C# есть интерфейсы для создания последовательностей: Iterable и IEnumerableсоответственно, а также специальные циклы для перебора этих элементов.18C#Циклforeach (elem in collection) { … }Для работы с итераторами в .NET есть специальный язык LINQ (Language Integrated Query), которыйпозволяет в декларативном стиле описывать преобразования данных.
LINQ использует ленивоепорождение объекта, то есть генераторы.Записи (структуры) в С++, C#, JS (объекты)Запись - это как структура в Сях. Или массив из разнородных элементов, но таких, чтобы всесмещения можно было вычислить на этапе компиляции.В динамических языках такая штука отсутствует за ненадобностью, так как там есть ассоциативныемассивы (хеши).Даже в Java ее нет.C++struct Record { int x; double y; }Record t;t.x, t.y; ← Обращение к полю записиRecord* t = …t->x, t->y; ← Обращение к полю записи через указатель на записьОператор -> можно перегрузить: T* operator ->() { … }Это обычно используется для оберток над ссылками (врапперов)C#Есть структуры.
В отличие от С++, в С# структура отличается от класса поведением. Классы в C#являются ссылочными типами. Структуры - типами-значениями. Это значит, что в отличие отссылок, доступ к полю структуры требует только одно разыменование. Кроме того, структурыхранятся на стеке и присваиваются полным копированием.Это нужно для эффективности, особенно если приходится постоянно создавать/удалять объекты,что на стеке делается быстрее, чем в куче.Структуры нельзя наследовать, переопределять в них конструктор по умолчанию.Объекты в JSЭто ассоциативные массивы с улучшением в виде прототипного наследования.var a = {}; // пустой объект имеет прототип Object и набор стандартных методовvar b = { cat: 5 };a[“dog”] = b.cat;b[“cat”] = a.dog + 1;// a = { dog: 5 }b = { cat: 6 }Обращения a.cat и a[“cat”] эквивалентны, как и a[1] и a[“1”].
Все ключи объектов на самом делестроки. Если ключ не найден, то возвращается undefined.Про прототипное наследование как нибудь потом.Денис ([880-903], завершено)Управление последовательностью вычисленийДва типа сущностей:191. вычисления (выражения, неявное управление)2. последовательность операторов (явное управление)ВыраженияВ рамках одного выражения последовательность вычислений зависит от семантики, при этом еслисемантика допускает неоднозначность, то порядок не определен.В функциональных языках есть “Ленивые вычисления” (операнды вычисляются только приреальной необходимости).Логические операции and, or – ленивые (в and если левая часть false, то правая не вычисляется).Первый вариант Ada предлагал: порядок вычислений не должен иметь таких особенностей,предложили специально добавить andthen и orelse.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
