О статических и динамических массивах


#1

Об одномерных динамических массивах.

Чем больше смотрю на их поведение в версии 3, тем больше ощущение, что это те же списки, только с возможностью обращения к каждому элементу по его индексу. Одномерный массив математически прочно ассоциируется с n-мерным вектором, но ведут себя эти массивы отнюдь “не по векторному”, а как последовательности, что еще раз подтверждает написанное выше.

Пусть имеем следующий фрагмент программы:

  var a:=Arr(1,2,3,4);
  var b:=Arr(5,6,7,8);
  var c:=a+b;
  Println(c);

С точки зрения математики тут все понятно: вектор с должен быть равен сумме векторов a и b, т.е. c[i]:=a[i]+b[i], i=imin…imax

Но нынешняя реализация языка поступает с массивами, как с последовательностями и приписывает компоненты массива b “в хвост” компонентам массива а, так что запустив программу на выполнение, мы обнаружим на выводе 1 2 3 4 5 6 7 8, а вовсе не 6 8 10 12, как предписывает математика.

Что такое в математике a*2, если a - вектор? Вектор такой же размерности, полученный умножением исходного вектора на скаляр, т.е. a[i]*2, i=imin…imax

А что даст такая конструкция в PascalABC.Net 3.1? Все логично, a*2 равнозначно a+a и мы получим исхдный массив, повторенный дважды, т.е. 1 2 3 4 1 2 3 4 Но хотелось бы получить как в математике- 2 4 6 8

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

А что даст с=a-b (а также c=a*b и c=a/b) в контексте приведенного ранее фрагмента программы. Я думаю, уже все догадались - ошибку при компиляции. А что хотелось бы? Да все по той же аналогии с векторами, чтобы c[i]=a[i] op b[i], где op - знак операции +, -, *, /

Тогда и думать не надо, как инициализировать массив, например, единичным значением, достаточно будет написать c:=1;

Это первое. Далее. Присваивание с=<нечто, приведенное к массиву>.

сейчас оно реализовано присваиванием ссылки. Когда в правой части оператора присваивания стоит выражение, насколько я понимаю, мы чаще всего получаем ленивую операцию и это отлично. Но вот когда там стоит массив, передача ссылки на него всего лишь создает массиву второе имя. А это нехорошо. Ну зачем в программе обращаться к массиву с двумя разными именами? В инструктивных материалах нам объясняют, что “во избежание…” мы можем воспользоватся функцией copy(), но, быть может, для случая явного прямого присваивания вида c:=a вызывать Copy автоматически?

Есть такая мощная штука в массивах… В Фотране она называется “сечением”. Там выражение вида a(3:7) для одномерного массива означает, что из него делается “вырезка”, наследующая свойства своего родителя, но содержащая только переиндексированные элементы a(3), a(4), … a(7). Хочу такое и в Паскале! А если серьезно, очень удобная вещь, особенно для многомерных массивов. Но если начинать, то начинать с одномерных. И подумать, получится ли разрешать сечения в левой части оператора присваивания. Т.е. нечто вроде c[3:5]:=b[1:3]. Подумать потому, что тогда должно корректно работать и a[m:n]:=a[p,q], возможно даже с пересечением областей сечений.

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


Версия PascalABC.NET 3.1
#2

Очень правильно всё пишете. Но идеология здесь другая. Давайте обсудим.

Это не математика. Мы не реализуем массивом математический вектор. Динамический массив, как и связный список, как и множества HashSet, SortedSet, являются разновидностями последовательностей. С ними можно делать всё то, что можно делать с последовательностями, плюс обращаться к элементам по индексу и кое-что еще. Говоря языком ООП, array of T реализует интерфейс IEnumerable, а sequence of T является полным синонимом IEnumerable. Для последовательностей определены операции + и * - возвращают они последовательности. Для массивов они переопределены, имеют ту же семантику, но возвращают массив. Поэтому оператор c:=a+b и работает.

Еще раз повторюсь, что фраза “с точки зрения математики” здесь не работает - это не математика. И массив - это не вектор в n-мерном пространстве. Поэтому и операции другие.

Еще раз - Вы правы - массив - это разновидность последовательности, и это - одно из самых главных его свойств. А последовательность в PascalABC.NET - это самостоятельная сущность (first-class object)

Динамические массивы в PascalABC.NET имеют ссылочную семантику со всеми вытекающими последствиями. Это более легковесно, повсеместно используется и имеет свои особенности. Если Вам (иногда) надо сделать копию, используйте copy(). Или используйте статические массивы, но тогда никакого сервиса, связанного с огромным количеством методов внутри, Вы не получите.

Срезы - наша мечта - и - я сказал, что мы их сделаем. Собственно, уже знаем как, просто руки не доходят. Основная проблема - это конструкция a:b, которая используется как элемент форматирования в writeln. Лично нам как разработчикам компилятора она доставляет катастрофические неудобства.

Срезы кстати есть не только в фортране, но и в Питоне скажем и много еще где. Поэтому сделать заманчиво.

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

Кстати, в самое ближайшее время ошибка с последовательностями будет исправлена - мы сейчас пишем совершенно иной алгоритм SeqGen и ему подобные.


#3

Срезы - наша мечта - и - я сказал, что мы их сделаем. Собственно, уже знаем как, просто руки не доходят. Основная проблема - это конструкция a:b, которая используется как элемент форматирования в writeln. Лично нам как разработчикам компилятора она доставляет катастрофические неудобства.

Как говорил Козьма Прутков: “Кто мешает тебе выдумать порох непромокаемый?”. Разве обязательно сохранять в срезах синтаксис Пайтона, неужели нельзя в качестве разделителя в записи среза использовать символы |, или !, или ~ или даже обратный апостроф (`) ?

И - немного о массивах, так сказать, несколько с иного бока. Сейчас для того, чтобы образовать из статического массива динамический, приходится писать что-то вроде var b:=aStatic.ToHashSet.ToArray; что очень некрасиво, а главное - непонятно “малопосвященным”. Может быть, имеет смысл добавить к статическим массивам метод преобразования ToDynamic, обладающий понятной семантикой? Есть, конечно, еще один вариант преобразования, который можно использовать, но это только при выводе элементов: var b:=aStatic.Println; и он тоже с душком шаманства))


#4

А для чего нужны эти статические массивы? Они все равно на стеке не размещаются. Статические массивы - это лишние накладные расходы и ненужное выделение памяти при каждом объявлении.


#5

Да действительно, давайте их уничтожим, как класс? Зачем новорожденных выкармливать грудным молоком, пусть едят прожаренную свиную вырезку! А ничего, что в начале обучения дается понятие статического массива, а потом уже происходит разговор о динамических структурах?


#6

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


#7

Жаль, что Вы не раскрыли это Ваше “многократно проще” - почему-то у меня есть стойкое ощущение того, что далеко не многократно и не особо проще. В чем-то да, проще, но в чем-то и сложнее. Прежде всего, напомню, что речь шла об аудитории, которой адресован PascalABC.Net. Основная направленность, насколько я понял - все же сфера образования. Включающая, конечно же, общеобразовательные школы. Так уж сложилось, что чаще всего у школьника первым алгоритмическим языком оказывается именно Паскаль. И изучают его не справочной системе системы программирования, а по учебнику. А там первая информационная структура, с которой школьник сталкивается - массив. В его простейшем, статическом понимании. “Заведем десять ячеек. Первое число мы поместим в первую ячейку, второе - во вторую, … и так поступи со всеми десятью числами”. В первое время, пусть с трудом, но доходит. А теперь представьте себе, что речь о динамическом массиве. “Заведем десять ячеек. В НУЛЕВУЮ (?) поместим первое число, в ПЕРВУЮ - второе,… а последнее, десятое число поместим в ДЕВЯТУЮ ячейку”. Мало того, что ввели новое понятие, так еще и нумерацию сдвинули. “- Мариванна, у меня на руке пять пальцев, мне что, надо на уроке информатики теперь мизинец четвертым называть?”.

Задача. В массиве удвоить значение элемента, если его порядковый номер четный и утроить в противном случае. Как понятнее школьнику, если по оператору попытаться восстановить исходное задание?

if Odd(i) then a[i]*=3 else a[i]*=2; // статический [1..n]
или
if Odd(i) then a[i]*=2 else a[i]*=3; // динамический [n]

Хочу быть правильно понятым: динамические массивы - прекрасная вещь! Но во всех языках они несут на себе отпечаток адресации областей памяти и поэтому индексируются от нуля. Статический массив имеет граничные пары, что в необходимых случаях дает возможность добиться от алгоритма большей прозрачности. Простая задача: по заданному номеру месяца вывести его название. В статический массив заносим 12 наименований и a[n] дает искомое. В динамическом - либо результат достигается через a[n-1], вызывая определенное недоумение у начинающего, либо надо определять 13 элементов и “самый первый” - тот, что перед первым (!) стоит, не учитывать. Прошу не считать это сообщение прологом к холивару про индексацию от 0 и от 1.


#8

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

У статических массивов есть одно полезное применение — численные расчёты с векторами и матрицами, размеры которых фиксированы, а как структуры данных они очень плохи. Мы фактически сразу вынуждены задавать максимально возможный размер и вводить фактическую заполненность, иначе остаётся решать задачи как в ваших примерах про 10 ячеек или 12 месяцев, плодя по всему коду «магические» константы.

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

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

Кстати, я не слышал от @Admin, как сейчас нужно работать с двоичными файлами: что там с сериализацией динамических массивов? Как сохранить в файл запись со строками произвольной длины и динамическими массивами внутри?


#9

Вот Вам “кажется…”, а я ежедневно в качестве модератора информатики на сервисе “Школьные знания” общаюсь не с одним десятком школьников различных возрастов и вживую вижу те проблемы, о которых пишу.

Вот когда Вы издадите свои учебники по информатике, где все будет базироваться на динамических массивах, и когда их повсеместно признают, тогда можно будет говорить об отказе от “анахронизма”. А сейчас для обучения гораздо востребованее не “динамические массивы” с какой-то особой структурой, а массивы с динамически изменяемой верхней границей. Как в Бейсике. Там не делят массивы на статические, динамические… Если надо границы поменять, выдал в нужном месте ReDim [Preserve] и живешь спокойно дальше. Похожее есть и Pascal: SetLength(), только без опции, позволяющей определить, зачищать ли содержимое массива с изменившимися границами.

Не согласен. Вы сами писали о векторах, матрицах - целом разделе математики. И что, говоря о трехмерном пространстве, мы должны считать что координата Х отображается в нулевом индексе? Есть индекс и есть порядковый номер. “- Алло, девушка, почему мне до сих пор не предоставили справку, Вы же сказали. что я первый на очереди? - Да, но Вы забыли, что перед Вами еще нулевой?” И не надо пытаться заставить человечество считать все от нуля лишь потому, что так было удобно когда-то индексировать области памяти в ассемблере.


#10

@RAlex вы зря тут меряетесь количеством школьников: у @bravit достаточно школьников, чтобы судить (да и у меня тоже). Если вы видите проблемы, то это, как справедливо сказал @bravit, проблемы подходов в обучении, методического обеспечения и так далее, но не проблемы динамических массивов. При должном подходе всё получается вполне доступно и даже лучше, чем с громоздким синтаксисом статических. Таков наш опыт в Воскресной компьютерной школе.

По поводу нужности. Не знаю, как в ПаскалеАБЦ, а в жизни статические массивы нужны. Традиционно у них есть свои экологические ниши: численные рассчёты, а также низкоуровневое программирование аля C (буфера). Разницу нужно понимать, но — не школьнику, а хотя бы студенту (или 11-класснику). А школьнику 7-8 классов (когда мы вводим массивы) нужно предоставить простейший из возможных синтаксисов и всё. Без философии, без низкоуровневой организации и т. п.

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

PS Тему надо отделять, на мой взгляд.


#11

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

А приведите пример, пожалуйста, этого нехорошего “громоздкого синтаксиса статических массивов”. Вот я вчера попробовал переработать с Алгол-60 некогда известный алгоритм 120б “Обращение матрицы методом Гаусса-Жордана”. На статических массивах сразу написал и заработало. А для перехода к динамическим массивам пришлось немного потрудиться, потому что надо было переводить все на индексирование с нуля. Программа, естественно, не стала ни короче (в байтах исходник даже длиннее из-за постоянных n-1), ни понятнее.

P.S. И не надо этого цехового “меряетесь количеством школьников…”. Я не о количестве говорю, а скорее, о качественной разнице.

И - да, тему надо отделять. Или просто почистить)))


#13

Тогда уж так

var b := a.ToArray;

Intellisense надо поправить


#14

В двоичных файлах типа file или file of что-то сохранить объекты со ссылочной семантикой не получится.

Для этого надо использовать более мощную .NET-сериализацию:

uses System;
uses System.IO;
uses System.Runtime.Serialization.Formatters.Binary;

type 
  [Serializable]
  RC = record
    s: string := 'ABC';
    a := Arr(1,2,3);
  end;

begin
  var formatter := new BinaryFormatter();
  var fs := new FileStream('d:\aa.dat', FileMode.OpenOrCreate);
  var r: RC; 
  formatter.Serialize(fs, r);
  fs.Close;
  r.s := 'XYZ';
  r.a := Arr(666,666,666);
  fs := new FileStream('d:\aa.dat', FileMode.OpenOrCreate);
  r := RC(formatter.DeSerialize(fs));
  fs.Close;
  Println(r);
end.

#15

Мы будем использовать в срезах синтаксис a[2:10:2]. Не советуйте нам пожалуйста синтаксические конструкции, которыми вряд ли кто-то будет пользоваться


#16

А вот это отличные новости! Чувствуется, что система программирования, как раньше говорили, идет “верной дорогой” )))

Да я только “за”! Если победите Write(a[3:12:4][2:10:2]:6:3), будет замечательно.


#17

Проще. Это Вы привыкли просто. Ребенку, которому рассказывают это впервые, особой разницы нет.

Но - Вы правы - старых учебников много, и там везде с единицы. Мы и не запрещаем старые массивы. Но Вы получаете вместе с ними тяжелое наследство: память выделяется жестко в процессе компиляции и чтобы их передавать - нужна именная эквивалентность:

type Arr = array [1..10000] of integer; // на всякий случай 10000
procedure Print(const a: Arr; n,m: integer)

и

procedure Print(a: array of integer)

Я уж не говорю, что мы лишаемся огромного количества стандартных методов работы с массивами.

Поэтому проще в дальнейшем - для решения более высокоуровневых задач. А так - побаловаться с индексами в короткой программе на 5-10 строк - да, не проще.


#18

Это вопрос, в начале чьего обучения.

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

Не забывайте также, что у нас и строка string - динамическая. Собственно, она и во Free Pascal динамическая если Вы специально не ставите опцию “программировать в стиле устаревшего Turbo Pascal”. Вообще, весь мир - динамический. И - открою страшную тайну - у нас и статические массивы на самом деле динамические, просто они косят под статические :slight_smile:


#19

Именно так. Их же не раздражает, что в ячейках компьютера хранятся нолики и единички.

Как Вы молодого человека убедите - так он и будет сразу считать правильным.

Вспомните - в Путешествии Гулливера были остроконечники и тупоконечники.


#20

Мы поступаем по-другому как видите. Везде на сайте PascalABC.NET будут культивироваться только динамические массивы как правильный код.

В частности, скоро конструкция

for i:=1 to n do

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


#21

Всё зависит от примеров. Недавно в сбербанке я был первым в очереди с номером номерка 973.

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