Терминология CS: массив

Шутка

Это да.
Сначала алфавит, потом наборы букв, ..., а далеко там где-то и знания.

Я в итоге пришел в выводу, что лучше сказать, что

int a[n] это массив целых чисел, проиндексированный целыми числами от 0 до n-1,

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

А как уж они там лежат в памяти – это не важно. Тот же динамический массив (т.е. массив численность элементов которого можно менять), можно реализовывать несколькими кусками памяти (их максимальное количество определено заранее), чтобы сэкономить при переносе элементов, это все равно будет массив.

Потому что иначе возникают сложности с вычислением адреса элемента. Массив указателей это косвенная адресация.

Ага, косвенная. Но с т.з. разработки алгоритма, нам наплевать как оно там реализовано, мы считаем массив строк – массивом, т.е. структурой данных с соотв. свойствами. Т.е. мы абстрагируемся от реализации, в чем и есть смысл АТД. Поэтому для АТД «массив» требование последовательного расположения в памяти – лишнее.

int a[n] это массив целых чисел, проиндексированный целыми числами от 0 до n-1

Экспромтом.

Массив это множество элементов.

не каждое множество - массив в общепринятом среди программистов понимании

Тогда так.
Массив это множество элементов к которым можно обратиться по индексу.

я бы уточнил «по непрерывному индексу». Map какбэ тоже индексируемое множество.

Изложите.

изложить что?

Ваше определение массива.

пусть будет «индексируемое множество, индексы элементов которого отображаемы на непрерывное множество целых чисел».

https://ru.wikipedia.org/wiki/Индексное_множество

https://ru.wikipedia.org/wiki/Счётное_множество

разверни мысль.

Может быть в определении сказать «счётное множество»?
Впрочем вроде нормально получилось.

https://ru.wikipedia.org/wiki/Индексное_множество
Может быть «счётное множество»?

Индексное множество не обязано быть счётным ©.

нет. Вообще примерно любой вариант «множества объектов», который используется для хранения сущностей в этих наших комплюктерах и языках программирования - счетное множество, тупо ввиду дискретности.

Так в определении есть текст «непрерывное множество целых чисел» и скорее всего речь идёт о последовательном ряде натуральных чисел.

Любое счётное множество может быть проиндексировано множеством натуральных чисел N.

Пока так
Массив - «индексируемое множество, индексы элементов которого отображаемы на непрерывное множество целых чисел».

Проблема твоего определения в том, что под него подойдет любое индексируемое множество, в частности, граф, если он представлен в виде множества вершин (структура node хранит в себе данные о связях). Но с элементами такого множества нельзя работать независимо, меняя содержание одного узла, потребуется обновить информацию о связях в соседних узлах… Аналогично и с linked list и пр. Для массива нужно требование возможности независимо работать с его элементами.

Ну и ассоциативный массив не будет подходить под твое определение, для него придется придумывать свое, не связанное с определением массива, а также для многомерного массива, или массива записей из бд (тут нет номера, но есть id, которые могут быть с «дырками»).

Так это определение взял с Вашего поста, или о чём речь?

Мне нравится (я считаю наиболее удачным из всех которые видел и придумывал) определение данное в ISO, которое на русский язык можно перевести так:

Массив – множество, состоящее из элементов одного типа, позволяющее обращаться к своим элементам произвольно и независимо.

Произвольно и независимо – означает можно обратиться к любому элементу не обращаясь к другим элементам множества и изменить его, также не обращаясь и не приводя к изменениям других элементов множества.

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

Также можно ввести еще несколько определений (модификаторов типа), позволяющих более точно определить некоторые вариации АТД массива:

индексированный массив (массив проиндексированный каким-то множеством, например, множеством целых чисел),

ассоциативный массив (индексированный массив, у которого индексация – биекция)

двумерный массив (массив проиндексированный парами целых чисел)

статический массив (массив, количество элементов которого фиксировано и не меняется)

динамический массив (массив, количество элементов которого может быть изменено)

…

ключевые свойства массива – произвольный и независимый доступ

Мне казалось, что всем очевидно, что в 2к24 таких объектов не существует.

Надо исправлять, а не цепляться за устаревшие и некорректные термины. Глядишь лет через 200 станет проще науке. А так превратится в философию, если ИИ всё не разгребёт (хотя людям ещё сложнее понимать что там разгребётся будет)

ассоциативный массив не будет подходить под твое определение, для него придется придумывать свое

ну да, ассоциативный массив aka Map - заметно другая сущность.

массива записей из бд

таблица БД не массив вообще, идеологически это просто множество, Set. Идентификатор записи - просто какое-то свойство самой записи, причем необязательное. Индексации в «массивном» понимании там нет, ты не можешь в общем случае взять и обратиться к нужной записи, только выбрать из общей кучи подходящие под запрос.

Индексированный набор значений одного типа. В матане векторы почти то же самое.

Мне «ближе» определение массива как множество элементов к которым можно обратиться согласно значения индекса.

В этом определении акцентируется метод доступа.

Мне «ближе» определение массива как множество элементов к которым можно обратиться согласно значения индекса.

Для меня это «индексированный массив».

Суждение о множестве элементов?

Множество элементов с индексацией.

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

Да тут вообще столько туману навели, можно тупо взять очень конкретное определение «набор объектов одного размера, которые расположены последовательно в памяти», а все что не подходит уже называть как-то по другому.

Массив – множество, состоящее из элементов одного типа, позволяющее обращаться к своим элементам произвольно и независимо.

Deque попадает под это определение, и при этом является существенно отличающейся от массива структурой в общепринятом понимании. Мне кажется - максимальную практическую пользу детишкам принесёт определение взятое из стандартов C/C++/Java. Мои 2 копейки.

Ну массив это в модели линейной озу в виде n steps of element size by index.
Массив строк - массив массивов, набор указателей на другие участки памяти с данными.
Емнип.

Deque не попадает под это определение, т.к. нет произвольного доступа: двунаправленная очередь дает доступ только с головы и хвоста.

тут вообще столько туману навели

И никто не вспомнил, что абстрактные типы данных различаются по доступным для них операциям? Не торт.

Тред не читал, конечно.

Deque не попадает под это определение, т.к. нет произвольного доступа

Позволю себе не согласиться: пруф, в частности «Random access - constant O(1)» requirement.

И никто не вспомнил, что абстрактные типы данных различаются по доступным для них операциям? Не торт.

Терминология CS: массив (комментарий)

Мне «ближе» определение массива как множество элементов к которым можно обратиться согласно значения индекса.
В этом определении акцентируется метод доступа.

Это реализация в std дает произвольный доступ, для АТД двустороняя очередь она не требуется. Эта реализация не позволяет независимо работать с элементами, поэтому это не массив.

поэтому это не массив

Это не массив исключительно потому как не contiguous. В этом плане я полностью согласен с господином AntonI - contiguous memory layout действительно должно быть частью определения массива. Имхо.

contiguous memory layout действительно должно быть частью определения массива. Имхо.

Но это же детали реализации, какое они имеют отношение к абстрактному типу данных. Вот для конкретной структуры данных, реализующей этот АТД, в конкретном языке под конкретную архитектуру — имеет смысл.

Но это же детали реализации, какое они имеют отношение к абстрактному типу данных.

Так вот что «АТД» означает… Как я это вижу: чем ближе абстракции к тому что можно «пощупать ручками» - тем лучше. Особенно если мы говорим об условных «детишках». Как по мне - определение массива сводится к &XN = &X0 + padded(sizeof(X)) * N. Ни больше ни меньше.

ПыСы. И ещё я бы избегал терминов «статический» vs «динамический» массив. Мне кажется «фиксированный размер» гораздо более удобоперевариваемый термин. Особенно если учесть что всё идёт к выпиливанию VLA из стандарта (и поддержки компиляторами).

ДЛя определения (обычного) массива (вектора) ключвым является то, что индексы элементов идут последовательно. ПРи обьясненияя такой штуки ИМНО проще и понятнее напирать на то, что элементы лежат в памяти подряд.

Черезмерно абстрактное определение понятности не добавляет.

И ещё я бы избегал терминов «статический» vs «динамический» массив. Мне кажется «фиксированный размер» гораздо более удобоперевариваемый термин.

Да, согласен, но это уже устоявшиеся англицизмы, – на русском не совсем логично, а на английском смысл как раз очень близок к сущности.

Как я это вижу: чем ближе абстракции к тому что можно «пощупать ручками» - тем лучше

Когда абстракции зависят от деталей конкретной реализации — получаются чернила для пятого класса.

ДЛя определения (обычного) массива (вектора) ключвым является то, что индексы элементов идут последовательно.

Что насчёт разрежённых (sparse) массивов?

Скорее термин «массив» трактуется по разному для разных предметных областей.

Для Си одна трактовка, если говорим об абстракциях, то другая ...
Проще говоря «моно» определение для массива - «не очень.»

Очевидно это не вектора. Ваш К.О.

Очевидно это не вектора

Речь-то шла о массивах. Доступ по индексу за постоянное время есть? Значит, массив.

Доступ по индексу за постоянное время есть?

Для разреженного массива в общем случае нет.

Для разреженного массива в общем случае нет.

Для обычного тогда тоже в общем случае нет — натуральных чисел бесконечное множество, а массиву всё-таки желательно быть конечного размера.

Массив — он и в Африке массив, что за дискриминация на ровном месте. Может, разрежённый, может, нет. Может, ассоциативный вообще. (Хотя чем обычный массив с целочисленными ключами не ассоциативный? Некоторые реализации и не делают разницы, например, Луа. )

Для обычного тогда тоже в общем случае нет

Для обычного в общем случае да.

Разреженные массивы обычно делаются через ассоциативные. Ассоциативные массивы тоже массивы, но ТС под массивом все таки понимал вектор (обычный массив).