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

Хотя, конечно, хотелось бы какой-то строгости, желательно, математической.

зачем нужна наукообразность на пустом месте? Ты хочешь писать бумаги в журналы по философии CS?

Но российский вариант определения массива по госту поверг меня в предшоковое состояние. Это же хрень какая-то, а не определение?

По-моему, как раз это более точное, но бесполезное определение (как в том анекдоте про математика и воздушный шар). Типа есть многомерный массив ar, его элементы в таком случае будут ar[i,j,k,..], где i, j, k — целые. Другое дело, что, как я понимаю, в массиве главное — это random access, а тут этого как раз и нет.

Не, это как раз бессмысленное определение, т.к. тут нет произвольного и независимого доступа, соотв. тот же linked list подходит под это определение – функция по порядковому номеру элемента.

А для индексов обычно говорили (когда я учился) индексированный массив, массив проиндексированный целыми числами от 0 до n-1, или парами целых чисел и пр.

Скорее всего, оно списано с советского ГОСТа или другого нормативного документа, будет тебе кто-то переводить, ага.

Другое дело, что, как я понимаю, в массиве главное — это random access, а тут этого как раз и нет.

С третьей стороны на уровне реализации это может быть вообще не массив, а класс

Мне всегда казалось, что терминологические споры не имеют смысла:-)

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

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

Это пока ты не упрешься во взаимное недопонимание перерастающее в конфликты.

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

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

Ну вот да. До некоторых пор это нормальное определение. Обычно так и говорят. Ну или тыкают в int a[10] и говорят, что вот это пример массива.

Но лучше уточнить, что тип данных у элементов одинаков, доступ независимый (а значит можно сделать за O(1)) и произвольный.

Складывать-то эти ваши массивы можно?

Расскажите, пожалуйста, про теорию массивов (комментарий)

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

Вот эту шню мы назовём тирьямпампацией, и погнали!

А вот когда начинается рубилово- это вуглускр/неи это не вуглускр! - вот такое пустая трата времени.

Кстати основная проблема философии, что они обычные слова юзают как термины. Дальше я ниче не понимаю что они говорят:-(

доступ независимый (а значит можно сделать за O(1))

А можно и не сделать. Скажем в мапе доступ независимый, но O(ln N)

Согласен, но есть один маленький нюанс: это все хорошо работает среди квалифицированных людей, когда у них есть твердый фундамент в виде опыта или фундаментальных знаний, а вот на этапе обучения, когда твоя аудитория это студенты, нужна строгость, тут нельзя ткнуть в int a[n] и сказать что вот это массив, а дальше сами сообразите, нужно как-то разнести АТД, и определить основные свойства, иначе у них будет каша в голове, и соотв. в коде.

А можно и не сделать. Скажем в мапе доступ независимый, но O(ln N)

А можно и не сделать… Поэтому O(1) в определение массива и не вносят, это вопросы реализации, которая много от чего зависит.

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

В моем понимании массив это вектор элементов + алгоритм преобразованию ключа в оффсет в векторе занимающий О(1). Это для многомерных массивов актуально.

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

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

К сожалению имеют. Видал я спецов которые неправильные термины заучили и оттуда делают неправильные выводы. Большинство выгоняют, т.к. с реальностью результаты их работы не согласовываются, но иногда это не так заметно и тогда они продолжают вредить.

Вот скажем в математике функция распределения это совсем не то же самое что в физике.

Кого будем расстреливать?:-)

Тех кто один и тот же термин приволок для 2 разных вещей. Значит физиков )

Это независимо произошло скорее всего.

Таких историй овердофигища. Скажем термин индукция…

основная проблема философии, что они обычные слова юзают как термины

Ну да, только в философии такая проблема.

Если для задачи не подходит имеющееся определение, напиши своё. В идеале отдельное, чтобы не возникало путаницы

В моем понимании массив это вектор элементов

Вы даёте определение через определение. То есть сначала, надо бы сказать, что значит «вектор элементов» и «элемент».

Что такое вектор это как раз понятно - элементы одинакового типа расположенные в памяти подряд.

Массив это не АТД, это сплошной кусок (виртуальной) оперативной памяти. Это все, что нужно знать про массив.

Что такое вектор это как раз понятно - элементы одинакового типа расположенные в памяти подряд.

То есть, если у меня есть структура, все поля которой имеют один и тот же тип, то согласно вашему определению - это вектор

нет произвольного и независимого доступа

И что? Произвольный и независимый доступ являются артефактами реализации массивов данных в ЯП, а не каким-то заранее заданным свойством.

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

Ну тогда хэш подходит под это определение. Вычисление адреса по индексу это простейшая хэш функция.

российский вариант определения массива по госту поверг меня в предшоковое состояние. Это же хрень какая-то, а не определение?

они же по сути одинаковые.

По ISO это две разных характеристики - однотипность (type array) и перечислимость (array).

По ГОСТ одно понятие - и однотипность, и перечислимость.

ISO считает, что один человек - это объект учета «один человек». Два человека - это объект учета «человеки». И только когда договоримся, кто из них 1 а кто 2, тогда «человеки» становятся «массивом человеков».

По ГОСТ судя по всему подразумевается, что зачем вводить отдельный объект учета, если его сразу и не посчитать?

С ней можно работать как с вектором.

а при чём тут Counter Strike?

Потому что индексация бывает разной. Она может и быть перекрывающейся и экзотической. Например, словарь это тоже массив, но проиндексированный множеством ключей, которые могут быть тоже словами. «ассоциативный массив».

словарь это тоже массив

Да ладно? Это в Питоне такое?

индексация бывает разной

Индексация – это биекция «произвольной хрени» на натуральный ряд ©.
А в ассоциативных массивах для удобства есть промежуточный слой абстракции (словарь).

Вовсе не обязательно биекция и не обязательно натурального ряда на множество. Индексом может выступать все что угодно, и одному и тому же элементу может соответствовать разный индекс. Индексация это отдельная надстройка над структурой. Проиндексировать можно и односвязный список, и очередь, и пр.

Индексом может выступать все что угодно

Ага, но оно сводимо к натуральному ряду.

одному и тому же элементу может соответствовать разный индекс.

Это уже не массив по ГОСТ / ISO.

И попробуй в бухгалтерии получить несколько жалований/зарплат/премий в 1 ведомости на 1 свою фамилию :)

Ага, но оно сводимо к натуральному ряду.

и к конструкции из пустых множеств 0, (0), (0, (0))…, но смысл?

Это уже не массив по ГОСТ / ISO.

Вполне себе массив по ISO, т.к. там в определении про индексацию ничего не сказано.

словарь это тоже массив

вот и пошло терминологическое рубилово;-)

Я таки больше скажу - ассоциативный массив может быть реализован через вектор пар ключ:значение, т.е. он будет дважды массивом!

и к конструкции из пустых множеств 0, (0), (0, (0))…, но смысл?

«Бог создал целые числа, всё остальное — дело рук человека» // Кронекер ©.

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

Везде по другому.

Массив - это по определению целочисленные индексы. Или вон говорят - вообще натуральные.

Всякие списки, словари, и прочая - это уже абстракции верхнего уровня.

Массив - это по определению целочисленные индексы. Или вон говорят - вообще натуральные.

В хэш таблице тоже целочисленные индексы или вообще натуральные могут быть:-)

списки, словари, и прочая - это уже абстракции верхнего уровня.

Вообще то того же, контейнеры.

Все таким массив - это однотипные элементы лежащие в памяти друг за другом. С точностью до выравнивания:-)

Все таким массив - это однотипные элементы лежащие в памяти друг за другом. С точностью до выравнивания:-)

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

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

Строго говоря - действительно по ISO получается, что словари и хэшмапы - массивы.

В реальности-то под массивам везде имеется в виду возможность именно целочисленной адресации каждого элемента. В том числе - потому что у этого есть однозначная аппаратная аналогия с адресами и смещением.

У словаря нет аппаратной аналогии. Словарь это массив + биекция.

действительно по ISO получается, что словари и хэшмапы - массивы

Скорее по ГОСТУ.

Слова про виртуальное адресное пространство и пр. я бы опустил - это тоже детали реализации:-)

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

Не просто целочисленная индексация - индексы идут подряд начиная с нуля (или 1, если это паскаль).

или 1, если это паскаль

или PostgreSQL

SELECT (ARRAY['a','b','c'])[1];

a

А смысл им лежать прям друг за другом? Если это, скажем, строки переменной длинны? Мы говорим – массив строк, подразумевая, что элементы – строки, и можно быстро взять каждую в отдельности и поработать с ней (в т.ч. увеличив или обрезав). Да, реализация скорее всего будет в виде массива указателей (или ссылок), и указатели будут лежать в памяти друг за другом. Но это уже детали реализации, в т.ч. и в том, что массив строк реализуется через массив указателей.

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

Все таки сложные абстракции нажо делать из простых.