В информатике запись (также называемая структурой , структурой или составным типом данных ) представляет собой составную структуру данных — набор полей , возможно , различных типов данных , обычно фиксированных по количеству и последовательности. [1]
Например, дата может храниться как запись, содержащая числовое поле года , поле месяца , представленное в виде строки, и числовое поле дня месяца . Запись круга может содержать числовой радиус и центр , который является записью точки , содержащей координаты x и y .
Известные приложения включают тип записи языка программирования и для хранения на основе строк, данные, организованные как последовательность записей, такие как таблица базы данных , электронная таблица или файл значений, разделенных запятыми (CSV). В общем, значение типа записи хранится в памяти , а хранение на основе строк — в запоминающем устройстве .
Тип записи — это тип данных , который описывает такие значения и переменные. Большинство современных языков программирования позволяют программисту определять новые типы записей. Определение включает указание типа данных каждого поля и идентификатора ( имени или метки), по которому к нему можно получить доступ. В теории типов , как правило, предпочтительны типы продуктов (без имен полей) из-за их простоты, но надлежащие типы записей изучаются в таких языках, как System F-sub . Поскольку записи теории типов могут содержать поля с типом функции первого класса в дополнение к данным, они могут выражать многие особенности объектно-ориентированного программирования .
В контексте хранения, например, в базе данных или электронной таблице, запись часто называется строкой , а каждое поле называется столбцом . [2] [3] [4] [5]
В объектно-ориентированном программировании объект — это запись, содержащая поля состояния и метода.
Запись похожа на математический кортеж , хотя кортеж может считаться или не считаться записью, и наоборот, в зависимости от соглашений и языка программирования. В том же ключе тип записи можно рассматривать как аналог декартова произведения двух или более математических множеств в компьютерном языке или как реализацию абстрактного типа продукта на определенном языке.
Запись отличается от массива тем, что элементы записи (поля) определяются определением записи и могут быть неоднородными, тогда как массив представляет собой набор элементов одного типа. [6]
Параметры функции можно рассматривать как поля записи, а передачу аргументов в функцию можно рассматривать как назначение входных параметров полям записи. На низком уровне вызов функции включает запись активации или фрейм вызова , который содержит параметры, а также другие поля, такие как локальные переменные и адрес возврата.
Концепция записи может быть прослежена до различных типов таблиц и бухгалтерских книг, используемых в бухгалтерском учете с отдаленных времен. Современное понятие записей в компьютерной науке, с полями четко определенного типа и размера, уже подразумевалось в механических калькуляторах 19-го века, таких как Аналитическая машина Бэббиджа . [ 7] [8]
Первоначальным машиночитаемым носителем, использовавшимся для данных (в отличие от контроля), была перфокарта , использовавшаяся для записей в переписи населения США 1890 года : каждая перфокарта была отдельной записью. Сравните запись в журнале 1880 года и перфокарту 1895 года. Записи были хорошо известны в первой половине 20-го века, когда большая часть обработки данных выполнялась с помощью перфокарт. Как правило, каждая запись файла данных записывалась на одну перфокарту, при этом определенные столбцы назначались определенным полям. Как правило, запись была наименьшей единицей, которую можно было прочитать с внешнего хранилища (например, считывателя карт, ленты или диска). Содержимое записей в стиле перфокарт изначально называлось «единичными записями», поскольку перфокарты имели предопределенную длину документа. [9] Когда системы хранения стали более совершенными с использованием жестких дисков и магнитной ленты , записи переменной длины стали стандартом. Запись переменной длины — это запись, в которой размер записи в байтах приблизительно равен сумме размеров ее полей. Это было невозможно сделать до изобретения более совершенных устройств хранения данных, поскольку все перфокарты должны были соответствовать заранее определенной длине документа, который мог считывать компьютер, поскольку в то время карты приходилось физически вводить в машину.
Большинство реализаций машинного языка и ранних языков ассемблера не имели специального синтаксиса для записей, но эта концепция была доступна (и широко использовалась) благодаря использованию индексных регистров , косвенной адресации и самомодифицирующегося кода . Некоторые ранние компьютеры, такие как IBM 1620 , имели аппаратную поддержку для разграничения записей и полей, а также специальные инструкции для копирования таких записей.
Концепция записей и полей была центральной в некоторых ранних утилитах сортировки и табулирования файлов , таких как IBM Report Program Generator (RPG) .
COBOL был первым широко распространеннымязыком программирования, поддерживающим типы записей,[10]и его возможности определения записей были довольно сложными в то время. Язык позволяет определять вложенные записи с буквенно-цифровыми, целочисленными и дробными полями произвольного размера и точности, а также поля, которые автоматически форматируют любое назначенное им значение (например, вставка знаков валют, десятичных точек и разделителей групп цифр). Каждый файл связан с переменной записи, в которую считываются или из которой записываются данные. COBOL также предоставляет операторMOVE CORRESPONDING, который назначает соответствующие поля двух записей в соответствии с их именами.
Ранние языки, разработанные для числовых вычислений, такие как FORTRAN (до FORTRAN IV ) и ALGOL 60 , не поддерживали типы записей; но более поздние версии этих языков, такие как FORTRAN 77 и ALGOL 68, добавили их. В исходном языке программирования Lisp также отсутствовали записи (за исключением встроенной ячейки cons ), но его S-выражения обеспечивали адекватную замену. Язык программирования Pascal был одним из первых языков, полностью интегрировавших типы записей с другими базовыми типами в логически последовательную систему типов. Язык PL/I обеспечивал записи в стиле COBOL. Язык C предоставляет концепцию записи с использованием structs. Большинство языков, разработанных после Pascal (таких как Ada , Modula и Java ), также поддерживали записи.
Хотя записи больше не часто используются в своем первоначальном контексте (т. е. используются исключительно для хранения данных), записи повлияли на новые объектно-ориентированные языки программирования и реляционные системы управления базами данных. Поскольку записи обеспечивали большую модульность в способе хранения и обработки данных, они лучше подходят для представления сложных, реальных концепций, чем примитивные типы данных , предоставляемые по умолчанию в языках. Это повлияло на более поздние языки, такие как C++ , Python , JavaScript и Objective-C , которые удовлетворяют те же потребности в модульности программирования. [11] Объекты в этих языках по сути являются записями с добавлением методов и наследования , которые позволяют программистам манипулировать поведением данных, а не только содержимым записи. Многие программисты считают записи устаревшими сейчас, поскольку объектно-ориентированные языки обладают возможностями, которые намного превосходят то, на что способны записи. С другой стороны, многие программисты утверждают, что низкие накладные расходы и возможность использовать записи на языке ассемблера делают записи по-прежнему актуальными при программировании с низкими уровнями абстракции . Сегодня самые популярные языки в индексе TIOBE , индикаторе популярности языков программирования, в какой-то степени подверглись влиянию записей из-за того, что они являются объектно-ориентированными. [12] Языки запросов, такие как SQL и Object Query Language, также подверглись влиянию концепции записей. Эти языки позволяют программисту хранить наборы данных, которые по сути являются записями, в таблицах. [13] Затем эти данные можно извлечь с помощью первичного ключа . Сами таблицы также являются записями, которые могут иметь внешний ключ : ключ, который ссылается на данные в другой таблице.
Операции для типа записи включают:
Некоторые языки предоставляют средства, которые перечисляют поля записи. Это средство необходимо для реализации определенных служб, таких как отладка , сборка мусора и сериализация . Оно требует некоторой степени полиморфизма типов .
В контекстах, которые поддерживают подтипирование записей, операции включают добавление и удаление полей записи. Конкретный тип записи подразумевает, что присутствует определенный набор полей, но значения этого типа могут содержать дополнительные поля. Таким образом, запись с полями x , y и z будет принадлежать к типу записей с полями x и y , как и запись с полями x , y и r . Обоснование заключается в том, что передача записи ( x , y , z ) в функцию, которая ожидает запись ( x , y ) в качестве аргумента, должна работать, поскольку эта функция найдет все требуемые ей поля в записи. Многие способы практической реализации записей в языках программирования столкнулись бы с трудностями при разрешении такой изменчивости, но этот вопрос является центральной характеристикой типов записей в более теоретических контекстах.
Большинство языков допускают назначение между записями, имеющими абсолютно одинаковый тип записи (включая одинаковые типы полей и имена в том же порядке). Однако в зависимости от языка два типа данных записи, определенные отдельно, могут рассматриваться как различные типы, даже если они имеют абсолютно одинаковые поля.
Некоторые языки также могут разрешать назначение между записями, поля которых имеют разные имена, сопоставляя каждое значение поля с соответствующей переменной поля по их позициям в записи; так что, например, комплексное число с полями, называемыми realи , imagможет быть назначено переменной записи 2D-точки с полями Xи Y. В этой альтернативе два операнда по-прежнему должны иметь одинаковую последовательность типов полей. Некоторые языки также могут требовать, чтобы соответствующие типы имели одинаковый размер и кодировку, так что вся запись может быть назначена как неинтерпретируемая битовая строка . Другие языки могут быть более гибкими в этом отношении и требуют только того, чтобы каждое поле значения могло быть законно назначено соответствующему полю переменной; так что, например, короткое целочисленное поле может быть назначено длинному целочисленному полю или наоборот.
Другие языки (например, COBOL ) могут сопоставлять поля и значения по их именам, а не по позициям.
Эти же возможности применимы к сравнению двух значений записи на предмет равенства. Некоторые языки также могут допускать сравнение порядка ('<'и '>'), используя лексикографический порядок, основанный на сравнении отдельных полей. [ необходима цитата ]
PL/I допускает оба предыдущих типа присваивания, а также допускает структурные выражения , например, a = a+1;где «a» — это запись или структура в терминологии PL/I.
В Algol 68, если бы Ptsбыл массив записей, каждая с целочисленными полями Xи Y, можно было бы написать для получения массива целых чисел, состоящего из полей всех элементов . В результате операторы и имели бы тот же эффект.Y of PtsYPtsY of Pts[3] := 7(Y of Pts)[3] := 7
В Pascal команда with R do Sвыполнит последовательность команд S, как если бы все поля записи Rбыли объявлены как переменные. Аналогично вводу другого пространства имен в объектно-ориентированном языке, таком как C# , больше нет необходимости использовать имя записи в качестве префикса для доступа к полям. Таким образом, вместо записи Pt.X := 5; Pt.Y := Pt.X + 3можно написать .with Pt do begin X := 5; Y := X + 3 end
Представление записи в памяти различается в зависимости от языка программирования. Часто поля хранятся в последовательных ячейках памяти в том же порядке, в котором они объявлены в типе записи. Это может привести к тому, что два или более полей будут сохранены в одном и том же слове памяти; действительно, эта функция часто используется в системном программировании для доступа к определенным битам слова. С другой стороны, большинство компиляторов будут добавлять поля заполнения, в основном невидимые для программиста, чтобы соответствовать ограничениям выравнивания, налагаемым машиной, — скажем, что поле с плавающей точкой должно занимать одно слово.
Некоторые языки могут реализовать запись как массив адресов, указывающих на поля (и, возможно, на их имена и/или типы). Объекты в объектно-ориентированных языках часто реализуются довольно сложными способами, особенно в языках, которые допускают множественное наследование классов .
Самоопределяющаяся запись — это тип записи, который содержит информацию для идентификации типа записи и для поиска информации в записи. Она может содержать смещения элементов; элементы, таким образом, могут храниться в любом порядке или могут быть опущены. [14] Информация, хранящаяся в самоопределяющейся записи, может быть интерпретирована как метаданные для записи, что похоже на то, что можно было бы ожидать найти в метаданных UNIX относительно файла, содержащего такую информацию, как время создания записи и размер записи в байтах . В качестве альтернативы различные элементы записи, каждый из которых включает идентификатор элемента, могут просто следовать друг за другом в любом порядке.
Запись, особенно в контексте строкового хранения, может включать ключевые поля, которые позволяют индексировать записи коллекции. Первичный ключ уникален во всех сохраненных записях; существует только один такой ключ. [15] Другими словами, для любого первичного ключа не может существовать дубликатов. Например, файл сотрудника может содержать номер сотрудника, имя, отдел и зарплату. Номер сотрудника будет уникальным в организации и будет первичным ключом. В зависимости от носителя данных и организации файла номер сотрудника может быть проиндексирован — то есть также сохранен в отдельном файле, чтобы ускорить поиск. Код отдела не обязательно уникален; он также может быть проиндексирован, и в этом случае он будет считаться вторичным ключом или альтернативным ключом . [16] Если он не проиндексирован, весь файл сотрудника должен быть просканирован, чтобы создать список всех сотрудников определенного отдела. Ключи обычно выбираются таким образом, чтобы минимизировать вероятность того, что несколько значений будут реально сопоставлены с одним ключом. Например, поле «Зарплата» обычно не считается пригодным для использования в качестве ключа, поскольку многие сотрудники, скорее всего, будут иметь одинаковую зарплату.