Инструменты пользователя

Инструменты сайта


bb:redbook:205

2.5 Транспонирование одномерных матриц

1. Понятие о транспонировании

Слово транспонирование очень умное, но на самом деле ничего заумного в этом нет. Для того, чтобы понять что это такое возьмите лист бумаги, нарисуйте таблицу умножения Пифагора, например 10х5 клеток: по вертикали от 1 до 5, а по горизонтали от 1 до 10. Теперь положите эту таблицу на бок. Если не считать за недостаток, что все цифры теперь лежат на боку, вы только что успешно выполнили транспонирование матрицы. Если матрица небольших размеров, то можно и руками повернуть. А что если в матрице 5 млн X 40 млн элементов? От руки такую матрицу не то, что не напишешь — нет таких листов бумаги нигде в мире.

2. Пример транспонирования одномерного массива

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

Уже было упоминание о том, что надо начинать индексацию массивов с нуля, а заканчивать на размер массива-1 «гражданским» непривычно. Поэтому существует небольшая хитрость, которая заключается в том, чтобы обращаться к массивам с 1, а размер массива объявлять размер_массива+1. Если массив очень большой и многомерный, то это не очень хорошая практика, если же одномерный — то вполне приемлемо 1).

2.1 Создание пользовательского типа

Для решения поставленной задачи, например, возьмём отрывок из Трёх законов робототехники Айзека Азимова. Как вводить, данные в программу, уже было разобрано. Как создать массив, тоже понятно, с той поправкой, что желательно, чтобы он был больше, чем выбираемый отрывок, и обеспечить правильную охрану цикла для ввода и транспонирования. Если считать, что размер отрывка составит десятки мегабайтов, рекурсия тут точно не поможет — никакого стека не хватит. Остаётся только перестановка на месте. Для решения это задачи зададимся несколькими вспомогательными структурами. Одной из них, пусть будет безопасный тип строки:

TYPE
	туСтрока = POINTER TO RECORD
		длин_макс: INTEGER; 
		длин_текущ: INTEGER; 
		текст: ARRAY 2049 OF CHAR;
	END;

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

C помощью записи создаётся новый пользовательский тип туСтрока (тип указательный «Строка»). Он содержит в себе отдельным полем свою длину, и сам массив текста определён на 1 символ больше, чем степень числа «2» (2049 вместо 2048). Это сделано специально, чтобы можно было индексировать начиная с 1 (хотя, с учётом введённых полей делать это излишне - только ради удобства). Кроме того есть поле, означающее максимальную длину массива. Также стоит обратить внимание на то, как изменилась форма определения записи — использована новая привязка POINTER TO RECORD(«указатель на запись»). Указатель, как следует из названия «указывает на что-либо». В данном случае — на запись. И такой подход несколько меняет работу с переменными такого типа (POINTER TO RECORD)2).

2.2 Инициализация типа tString

Поскольку теперь у нас не просто массив литер в кодировке Unicode, а целая запись с полями — прежде чем использовать такую структуру её нужно привести в порядок. Из примеров, которые встречались ранее известно, что переменные без начального присвоения содержат мусор. Ниже приводится текст процедуры, которая как раз подготавливает к использования пользовательский тип туСтрока:

PROCEDURE (сам: туСтрока) Настр, NEW;
VAR
	(* счётчик инициализации строки *)
	цИтер: INTEGER;
BEGIN
	мЛог.String('[Инициализация текстового массива]'); Log.Ln;
	сам.длин_макс := 2048;
	сам.длин_текущ := 0;
	FOR цИтер := 0 TO сам.длин_макс DO
		сам.текст[цИтер] := ' '
	END;
END Настр;

В этой процедуре сразу заметно отличие объявления процедуры от того, что объявлено ранее. Обозначение формальной принадлежности процедуры к типу туСтрокасам является калькой с английского self. Можно использовать вместо сам – всё-что угодно, но автор рекомендует по методическим соображением использовать именно сам. Перед именем процедуры в скобках приведён параметр тип туСтрока. Таким образом происходит привязка этой процедуры к записи. После такого определения можно обратиться к этой процедуре следующим образом:

стр.Настр; (* стр — экземпляр записи типа PONTER TO туСтрока*)

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

После имени процедуры следует ключевое слово NEW. Это означает, что для указанного типа эта процедура вводится впервые. Записи объединённые с процедурами в КП называются объектами. А процедуры, привязанные к записям (и, автоматически уже объектам) — методами объекта. Поля записей в составе объектов называются свойства объекта (так реализуется объектно-ориентированный подход (ООП) в Компонентном Паскале).

Метод, который производит первоначальную настройку объекта в ООП принято называть инициализацией.

В самой процедуре происходит начальное присвоение полям записи первичных значений, массив литер получает в каждом элементе значение «пробел». Целочисленный цикл перебирает элементы массива с индекса 0 по 2048, т.е. всего 2049 элементов. Но, элемент с индексом 0 в дальнейшем использовать не предполагается. Ещё раз надо заметить, что строение туСтрока таково, что такое частное решение в данном случае – избыточно.

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

2.3 Ввод данных

Ввод данных уже разбирался, применим его снова в виде метода объекта:

<code=oberon2> PROCEDURE (сам: туСтрока) Читать, NEW; BEGIN

мЛог.String('[Чтение входного текста]'); Log.Ln;
мВв.Open;
WHILE мВв.Done & (сам.длин_текущ < сам.длин_макс) DO
	мВв.Char(сам.текст[сам.длин_текущ]);
	INC(сам.длин_текущ)
END;
мЛог.String('Длина введённого текста: '); Log.Int(сам.длин_текущ); Log.Ln

END Читать; </code.

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

2.4 Вывод текста

Вывод текста не является обязательной задачей, но всё-таки сделаем это, чтобы убедиться, что текст действительно будет «развёрнут на месте». Этот же метод будет использован для вывода перевёрнутого текста. Текст метода:

В связи с тем, что литерный массив выводится не полностью, а только та часть, что получила заполнение, пришлось ввести локальную переменную «i». Он позволит выводить массив до тех пор, пока он не станет равным заполнению на вводе.

2.5 Разворот текста на месте

Разворот массива на месте выполним с помощью дополнительной переменной литерного типа, в качестве промежуточного хранилища элемента литерного массива. Середина введённого текста может быть найдена через целочисленное деление длины ведённого текста пополам. Для этого используется ключевое слово DIV (сокращение от DIVISION, «деление»). В остальном, метод похож на предыдущие.

Точно также в начале метода используется диагностический вывод.

2.6 Главная процедура модуля

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

Часть кода занято диагностическим выводом, другая вызовом методов переменной, имеющей тип «tString», и здесь тоже всё достаточно прозрачно. Единственная инструкция, требующая пояснения: NEW(txt). «txt» — это переменная, имеющая тип «POINTER TO RECORD» (тип «УКАЗАТЕЛЬ НА ЗАПИСЬ»). Ключевое слово NEW указывает на то, что эта переменная создаётся динамически. Динамическое создание переменных используется очень часто, и использование NEW широко распространено. Если определить переменную «txt» не как динамическую, а как статическую, то размер программы сразу вырастит до примерно 4600 байт — за счёт массива CHAR на 2049 элементов (4098 байт). Без статического определения массива программа занимает порядка 640 байт. [↑]

2.7 Итоговый текст программы

Пример текста модуля ниже.

Hello12.odc

[↑]

2.8 Ввод и вывод данных

Для ввода данных использовать этот текст:

Вывод программы, если всё сделано училось правильно:

Как видно, вместо переводов строк появился парный символ «0DX 09X» (в шестнадцатиричном виде). Даже простой текст такому развороту поддаётся с сюрпризами. Это символ перевода строки. Результат не совсем такой, как ожидалось. Как работать со строками будет рассмотрено отдельно. В качестве самостоятельного задания попробуйте сделать так, чтобы перевод строки сохранялся[2]. [↑]

3. Примечания

[↑] В Паскаль-семействе трюк с пропуском нулевого элемента массива применяется повсеместно. Он бывает полезен в строках, когда чтобы точно установить длину строки — её длина содержится в нулевом элементе. Такие короткие строки (до 255 литералов) и средние строки (до 65,5 тыс. литералов) до сих пор популярны у паскалистов. Если конец строки будет испорчен, то процедуры обработки всё-равно закончат обработку по её размеру в нулевой ячейке. В этом отношении Паскаль-семейство более безопасно, чем лагерь Си — там для обозначения окончания строки в конце добавляется бинарный «00X». Можно себе представить, если вдруг в ближайших мегабайтах памяти этого символа не окажется. ,) Кроме того, затраты на подсчёт длины строки в Паскале равны нулю — подсчёт происходит мгновенно. Аналогичный подсчёт строки в Си будет выполняться крайне медленно (особенно, если строка занимает мегабайты).

[↑] В качестве подсказки: надо найти все комбинации «0DX 09Х» и заменить их на «00Х 00Х». После разворота, найти эти же символы и заменить их опять на «0DX 09Х».

[ ← Назад ] [ Вверх ↑ ] [ Далее → ]

1)
В Паскаль-семействе трюк с пропуском нулевого элемента массива применяется повсеместно. Он бывает полезен в строках, когда чтобы точно установить длину строки — её длина содержится в нулевом элементе. Такие короткие строки (до 255 литералов) и средние строки (до 65,5 тыс. литералов) до сих пор популярны у паскалистов. Если конец строки будет испорчен, то процедуры обработки всё-равно закончат обработку по её размеру в нулевой ячейке. В этом отношении Паскаль-семейство более безопасно, чем лагерь Си — там для обозначения окончания строки в конце добавляется бинарный 0h. Можно себе представить, если вдруг в ближайших мегабайтах памяти этого символа не окажется. ,) Кроме того, затраты на подсчёт длины строки в Паскале равны нулю — подсчёт происходит мгновенно. Аналогичный подсчёт строки в Си будет выполняться крайне медленно (особенно, если строка занимает мегабайты).
2)
Указатель в других языках штука весьма опасная. К счастью, в КП с указателями работа намного проще и отсюда строже. И это благо, так как ошибочная работа с указателями – это бич Божий в других языках программирования. Так называемая адресная арифметика является главным источником ошибок в программах. Именно из-за плохо продуманной семантики указателей во многих устаревших языках программирования нет автоматического сборщика мусора и существуют утечки памяти.
bb/redbook/205.txt · Последние изменения: 2018/11/29 22:13 (внешнее изменение)