Компонентный Паскаль/Транспонирование одномерных матриц

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

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

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

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

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

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

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

TYPE
	TString = POINTER TO RECORD
		len_max: INTEGER; (* максимальная лина текста *)
		len_txt: INTEGER; (* текущая длина текста *)
		txt: ARRAY 2049 OF CHAR; (* сам текст *)
	END;

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

Инициализация тип TString

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

PROCEDURE (s: TString) Init, NEW;
VAR
	(* счётчик инициализации строки *)
	i: INTEGER;
BEGIN
	Log.String('[Инициализация текстового массива]'); Log.Ln;
	s.len_max := 2048;
	s.len_txt := 0;
	FOR i := 0 TO s.len_max DO
		s.txt[i] := ' '
	END;
END Init;

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

a.Init; (* a -- экземпляр записи типа PONTER TO TString *)

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

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

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

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

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

Ввод данных

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

PROCEDURE (s: TString) ReadText, NEW;
BEGIN
	Log.String('[Чтение входного текста]'); Log.Ln;
	In.Open;
	WHILE In.Done & (s.len_txt < s.len_max) DO
		In.Char(s.txt[s.len_txt ]);
		INC(s.len_txt)
	END;
	Log.String('Длина введённого текста: '); Log.Int(s.len_txt); Log.Ln
END ReadText;

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

Вывод текста

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

PROCEDURE (s: TString) LogText, NEW;
VAR
	i : INTEGER; 
BEGIN
	Log.String('[Вывод текста]'); Log.Ln;
	i:=1;
	WHILE i <= s.len_txt DO
		Log.Char(s.txt[i]);
		INC(i)
	END;
	Log.Ln
END LogText;

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

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

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

PROCEDURE (s: TString) RotateText, NEW;
VAR
	i: INTEGER;
	c: CHAR;
BEGIN
	Log.String('[Разворот текста]'); Log.Ln;
	i := 1;
	FOR i := 1 TO(s.len_txt DIV 2) DO
		c := s.txt[i];
		s.txt[i] := s.txt[s.len_txt - i];
		s.txt[s.len_txt - i] := c
	END;
END RotateText;

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

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

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

PROCEDURE Start*;
BEGIN
	Log.String('=[ Начало ]='); Log.Ln;
	Log.String('[Создание TString]'); Log.Ln;
	NEW(txt);
	txt.Init;
	txt.ReadText;
	txt.LogText;
	txt.RotateText;
	txt.LogText;
	Log.String('=[ Конец ]='); Log.Ln
END Start;

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

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

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

Hello12.odc

MODULE TestHello12;
(* Этот пример показывает как развернуть
матрицу шиворот на выворот *)

IMPORT In, Log, Math;

TYPE
	TString = POINTER TO RECORD
		len_max: INTEGER; (* максимальная лина текста *)
		len_txt: INTEGER; (* текущая длина текста *)
		txt: ARRAY 2049 OF CHAR; (* сам текст *)
	END;


VAR
	i: INTEGER;
	txt: TString;


PROCEDURE (s: TString) Init, NEW;
	VAR
		(* счётчик инициализации строки *)
		i: INTEGER;
	BEGIN
		Log.String('[Инициализация текстового массива]'); Log.Ln;
		s.len_max := 2048;
		s.len_txt := 0;
		FOR i := 1 TO s.len_max DO
			s.txt[i] := ' '
		END;
	END Init;


	PROCEDURE (s: TString) ReadText, NEW;
	BEGIN
		Log.String('[Чтение входного текста]'); Log.Ln;
		In.Open;
		WHILE In.Done & (s.len_txt < s.len_max) DO
			In.Char(s.txt[s.len_txt]);
			INC(s.len_txt)
		END;
		Log.String('Длина введённого текста: '); Log.Int(s.len_txt); Log.Ln
	END ReadText;

	PROCEDURE (s: TString) LogText, NEW;
	VAR
		i: INTEGER;
	BEGIN
		Log.String('[Вывод текста]'); Log.Ln;
		i := 1;
		WHILE i <= s.len_txt DO
			Log.Char(s.txt[i]);
			INC(i)
		END;
		Log.Ln
	END LogText;

	PROCEDURE (s: TString) RotateText, NEW;
	VAR
		i: INTEGER;
		c: CHAR;
	BEGIN
		Log.String('[Разворот текста]'); Log.Ln;
		i := 1;
		FOR i := 1 TO(s.len_txt DIV 2) DO
			c := s.txt[i];
			s.txt[i] := s.txt[s.len_txt - i];
			s.txt[s.len_txt - i] := c
		END;
	END RotateText;

	PROCEDURE Start*;
	BEGIN
		Log.String('=[ Начало ]='); Log.Ln;

		Log.String('[Создание TString]'); Log.Ln;
		NEW(txt);
		txt.Init;
		txt.ReadText;
		txt.LogText;
		txt.RotateText;
		txt.LogText;
		Log.String('=[ Конец ]='); Log.Ln
	END Start;


BEGIN
END TestHello12.

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

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

В 2005 году она окончила Колумбийский университет в поступила в
аспирантуру по кибернетике.
Изобретенные Робертсоном позитронные мозговые связи превзошли все
достигнутое в середине XX века в области вычислительных машин и совершили
настоящий переворот. Целые мили реле и фотоэлементов уступили место
пористому платино - иридиевому шару размером с человеческий мозг.
Сьюзен научилась рассчитывать необходимые параметры, определять
возможные значения переменных позитронного "мозга" и разрабатывать такие
схемы, чтобы можно было точно предсказать его реакцию на данные
раздражители.
В 2008 году она получила степень доктора и поступила на "Ю.  С. Роботс"
в качестве робопсихолога, став, таким образом, первым выдающимся
специалистом в этой новой области науки. Лоуренс Робертсон тогда все еще был
президентом компании, Альфред Лэннинг - научным руководителем.
За пятьдесят лет на глазах Сьюзен Кэлвин прогресс человечества изменил
свое русло и рванулся вперед.

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

компилируется "TestHello12"   636   8
=[ Начало ]=
[Создание TString]
[Инициализация текстового массива]
[Чтение входного текста]
Длина введённого текста:  959
[Вывод текста]
 2005 году она окончила Колумбийский университет в поступила в 0DX аспирантуру по кибернетике. 
0DX Изобретенные Робертсоном позитронные мозговые связи превзошли все 0DX достигнутое в середине 
XX века в области вычислительных машин и совершили 0DX настоящий переворот. Целые мили реле и 
фотоэлементов уступили место 0DX пористому платино - иридиевому шару размером с человеческий 
мозг. 0DX Сьюзен научилась рассчитывать необходимые параметры, определять 0DX возможные значения 
переменных позитронного "мозга" и разрабатывать такие 0DX схемы, чтобы можно было точно 
предсказать его реакцию на данные 0DX раздражители. 0DX В 2008 году она получила степень доктора 
и поступила на "Ю.  С. Роботс" 0DX в качестве робопсихолога, став, таким образом, первым 
выдающимся 0DX специалистом в этой новой области науки. Лоуренс Робертсон тогда все еще был 0DX 
президентом компании, Альфред Лэннинг - научным руководителем. 0DX За пятьдесят лет на глазах 
Сьюзен Кэлвин прогресс человечества изменил 0DX свое русло и рванулся вперед.  
[Разворот текста]
[Вывод текста]
 .дерепв яслунавр и олсур еовс 0DX линемзи автсечеволеч ссергорп нивлэК незюьС хазалг ан тел 
тяседьтяп аЗ 0DX .мелетидовокур мынчуан - гниннэЛ дерфьлА ,иинапмок мотнедизерп 0DX лыб еще есв 
адгот ностребоР снеруоЛ .икуан итсалбо йовон йотэ в мотсилаицепс 0DX ясмищюадыв мывреп ,мозарбо 
микат ,ватс ,аголохиспобор евтсечак в 0DX "стобоР .С  .Ю" ан алипутсоп и ароткод ьнепетс аличулоп
ано удог 8002 В 0DX .илетижардзар 0DX еыннад ан юицкаер оге ьтазаксдерп ончот олыб онжом ыботч 
,ымехс 0DX еикат ьтавытабарзар и "агзом" огоннортизоп хыннемереп яинечанз еынжомзов 0DX 
ьтяледерпо ,ыртемарап еымидохбоен ьтавытичссар ьсаличуан незюьС 0DX .гзом йиксечеволеч с моремзар
 ураш умовеидири - ониталп умотсироп 0DX отсем илипутсу вотнемелэотоф и елер илим еылеЦ 
.торовереп йищяотсан 0DX илишревос и нишам хыньлетилсичыв итсалбо в акев XX енидерес в 
еотунгитсод 0DX есв илшозверп изявс еывогзом еыннортизоп моностребоР еыннетербозИ 0DX 
.екитенребик оп урутнарипса 0DX в алипутсоп в тетисревину йиксйибмулоК аличноко ано удог 5002  
=[ Конец ]=

Как видно, вместо переводов строк появился символ "0DX". Это символ перевода строки. Результат не совсем такой, как ожидалось. Как работать со строками будет рассмотрено отдельно.

Примечания

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

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

[1]