i21прим/Docu.Пошаговая разработка/4. Уплотнение.odc

4. Пошаговая разработка: Уплотнение массива 

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

Решение

ЧастьА  Постановка задачи. Проектирование интерфейса
ЧастьБ  Проверка корректности входных данных
ЧастьВ  Построение основной процедуры
ЧастьГ  Демонстрация работы
ЧастьД  Упражнения


Часть А. Постановка задачи. Проектирование интерфейсов

Эта часть выполняется в основном так же, как и в первомпримере. Только тип элементов массива-параметра будет CHAR вместо INTEGER, и еще нужно по-другому назвать модуль и процедуру. Пусть полное имя модуля будет i21примУплотнение (т.е. имя файла, в котором хранится модуль, будет Уплотнение). Процедуру назовем Уплотнить. Получим следующую заготовку:

MODULE  i21примУплотнение;
	
	PROCEDURE Уплотнить* ( VAR a: ARRAY OF CHAR );
		VAR  
	BEGIN
		
	END Уплотнить;
	
END  i21примУплотнение.


Часть Б. Проверка корректности входных данных

В этой части изложение менее подробно и предполагает хорошее знакомство с предыдущими примерами.

Особенностью данной задачи является сравнительно сложная структура входных данных, так что возникает необходимость проверить, выполняются ли предположения задачи. Конкретно, нужно определить, действительно ли в массиве a есть элемент, в котором хранится специальное значение 0X, используемое в качестве ограничителя символьных цепочек в Компонентном Паскале.
Рассуждая подобно примеруспроверкойпростыхчисел, выберем такой способ проверки, чтобы программа аварийно останавливалась, если входные условия не удовлетворены. Поручим проверку отдельной процедуре  назовем ее Проверить,  которая вызывается в самом начале процедуры Уплотнить. Для надежности расположим ее вне процедуры Уплотнить в том же модуле (перед Уплотнить):
	
MODULE  i21примУплотнение;
	
	PROCEDURE Проверить ( VAR a: ARRAY OF CHAR );
		VAR  
	BEGIN
		
	END Проверить;
	
	PROCEDURE Уплотнить* ( VAR a: ARRAY OF CHAR );
		VAR  
	BEGIN
		Проверить( a );
		
	END Уплотнить;
	
END  i21примУплотнение.

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

	PROCEDURE Проверить ( VAR a: ARRAY OF CHAR );
		VAR  кандидат: INTEGER;
	BEGIN
		кандидат := 0;
		WHILE (кандидат < LEN(a)) & (a[кандидат] # 0X)  DO
			кандидат := кандидат + 1
		END;
		ASSERT( кандидат < LEN(a) )
	END Проверить;
	
Здесь кандидат  индекс очередного проверяемого элемента массива, и вместо того, чтобы возвращать логическое значение, мы передали его в стандартную процедуру ASSERT. Кроме того, при определении простоты числа TRUE возвращалось, когда подходящий кандидат на роль делителя не был найден, а здесь нужно передавать TRUE в том случае, когда кандидат на 0X был успешно обнаружен. Так что условие в ASSERT соответствует отрицанию возвращаемого выражения в процедуре i21примПростые.Простое.

Часть В. Построение основной процедуры

Алгоритм построим на основе следующего наблюдения: после исключения лишних пробелов порядок литер будет такой же, как и до уплотнения. 
Тогда если i  начальная позиция какой-то литеры, а j  ее позиция после уплотнения, то при постепенном увеличении i значение j будет либо тоже возрастать, либо оно будет оставаться неизменным  в том случае, если i проходит по "лишним" пробелам.

			      i
		до уплотнения:	один  два    три
		после уплотнения:	один два три
			     j

Алгоритм построим в виде цикла. На каждом шаге цикла будем либо увеличивать только i, пропуская лишние пробелы, либо одновременно увеличивать i и j и пересылать значение из a[i] в a[j]. 
Цикл будем строить так, чтобы в начале каждого шага цикла индекс j указывал на последнюю позицию, в которую мы что-либо переслали на предыдущих шагах, а i  на последний просмотренный элемент. 
Тогда цикл можно записать следующим образом:
		
		установить начальные значения для цикла;
		ПОКА не вышли за конец цепочки ДЕЛАТЬ
			увеличить i;
			ЕСЛИ  a[i]  лишний пробел  ТО
				перейти к след. шагу цикла
			ИНАЧЕ
				увеличить j;
				передвинуть значение a[i] в a[j]
			КОНЕЦ
		КОНЕЦ

Переводя ключевые слова на английский язык и сразу кодируя на Компонентном Паскале очевидные операции, получим:

		установить начальные значения для цикла;
		WHILE не вышли за конец цепочки DO
			i := i + 1;
			IF  a[i]  лишний пробел  THEN
				(* ничего не делать *)
			ELSE
				j := j + 1;
				a[j] := a[i]
			END
		END

После THEN стоит только комментарий, т.к. после IF нет никаких инструкций, и поэтому для перехода к началу цикла ничего специально делать не нужно.

Чтобы закодировать охрану цикла ("не вышли за конец цепочки"), посмотрим, что происходит в самом конце цикла. Цепочка замыкается специальной литерой-ограничителем 0X. Ее нужно переслать, чтобы получившаяся цепочка оказалась правильно оформленной. Поэтому ее можно трактовать как и любую другую литеру, не являющуюся пробелом. Тогда 0X должен быть последней литерой, которую мы переслали. Но тогда и распознать, что мы на предыдущем шаге уже переслали 0X, легко: достаточно проверить равенство a[j] = 0X.

		установить начальные значения для цикла;
		WHILE  a[j] # 0X  DO
			i := i + 1;
			IF  a[i]  лишний пробел  THEN
				(* ничего не делать *)
			ELSE
				j := j + 1;
				a[j] := a[i]
			END
		END

Как теперь узнать, является ли значение, хранящееся в a[i], лишним пробелом?
Тут два условия, которые должны выполниться одновременно.
Во-первых, a[i] должно быть пробелом, и если это так, то это должен быть лишний пробел. Первое условие записать легко, так что охрану условного оператора IF можно записать так:

			IF  (a[i] = ' ') & (этот пробел лишний)  THEN

Чтобы понять, как определить, является ли пробел лишним, изобразим именно такую ситуацию. Для этого возьмем тот же пример и поставим i и j в позиции, соответствующие именно такой ситуации:

			     i
		до уплотнения:	один  два    три
		после уплотнения:	один два три
			    j

Видно, что достаточно посмотреть на значение, хранящееся в a[j]: ведь именно там хранится последняя литера, которую мы переместили. Если там пробел, то пробел в a[i] заведомо лишний. В противном случае это не так.

В итоге наш цикл приобретает такой вид:

		установить начальные значения для цикла;
		WHILE  a[j] # 0X  DO
			i := i + 1;
			IF  (a[i] = ' ') & (a[j] = ' ')  THEN
				(* ничего не делать *)
			ELSE
				j := j + 1;
				a[j] := a[i]
			END
		END

Позаботимся об установлении начальных значений.
Мы построили цикл исходя из предположения, что в начале каждого шага цикла i должно указывать на последний элемент, который мы уже просмотрели, а j  последний элемент, в который что-то было записано.
Другими словами, мы как бы должны к моменту начала первого шага цикла сделать первый шаг уплотнения.
Исследуем первую литеру начальной цепочки. Это может быть пробел, или любая другая литера, в том числе и 0X. Если это пробел, то перед ним, разумеется, нет пробелов, и поэтому по условию задачи он не является "лишним", т.е. должен остаться в цепочке после уплотнения. Если это другая литера (в том числе и 0X), то она тем более должна остаться в цепочке. 
Куда она должна попасть? Так как это первая литера, то и попасть она должна на первое место  попросту остаться там, где она и так стоит.

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

MODULE  i21примУплотнение;
	
	PROCEDURE Проверить ( VAR a: ARRAY OF CHAR );
		VAR  кандидат: INTEGER;
	BEGIN
		кандидат := 0;
		WHILE (кандидат < LEN(a)) & (a[кандидат] # 0X)  DO
			кандидат := кандидат + 1
		END;
		ASSERT( кандидат < LEN(a) )
	END Проверить;
	
	PROCEDURE Уплотнить* ( VAR a: ARRAY OF CHAR );
		VAR  i, j: INTEGER;
	BEGIN
		Проверить( a );
		i := 0;  j := 0;
		WHILE  a[j] # 0X  DO
			i := i + 1;
			IF  (a[i] # ' ') OR (a[j] # ' ')  THEN
				j := j + 1;
				a[j] := a[i]
			END
		END
	END Уплотнить;
	
END  i21примУплотнение.

Мы еще сделали маленькое сокращение кода, исключив пустую ветвь оператора IF; для этого пришлось заменить условное выражение на его отрицание по правилу де Моргана.


Часть Г. Проверка работы

Чтобы продемонстрировать работу процедуры, введем в модуль еще одну процедуру с именем Демо, которая будет получать цепочку литер в качестве параметра, обрабатывать ее с помощью процедуры Уплотнить, а также печатать цепочку до и после уплотнения.
Разумеется, чтобы использовать средства печати в рабочий журнал, нужно импортировать модуль StdLog. 
Окончательный вариант модуля выглядит так:

MODULE  i21примУплотнение;
	IMPORT  StdLog;
	
	PROCEDURE Проверить ( VAR a: ARRAY OF CHAR );
		VAR  кандидат: INTEGER;
	BEGIN
		кандидат := 0;
		WHILE (кандидат < LEN(a)) & (a[кандидат] # 0X)  DO
			кандидат := кандидат + 1
		END;
		ASSERT( кандидат < LEN(a) )
	END Проверить;
	
	PROCEDURE Уплотнить* ( VAR a: ARRAY OF CHAR );
		VAR  i, j: INTEGER;
	BEGIN
		Проверить( a );
		i := 0;  j := 0;
		WHILE  a[j] # 0X  DO
			i := i + 1;
			IF  (a[i] # ' ') OR (a[j] # ' ')  THEN
				j := j + 1;
				a[j] := a[i]
			END
		END
	END Уплотнить;
	
	PROCEDURE Демо* ( цепочка: ARRAY OF CHAR );
		VAR  a: ARRAY 200 OF CHAR;
	BEGIN
		a := цепочка$;
		StdLog.String('до сжатия:');  StdLog.Ln;
		StdLog.String(a);  StdLog.Ln;
		Уплотнить( a );
		StdLog.String('после сжатия:');  StdLog.Ln;
		StdLog.String(a);  StdLog.Ln;
	END Демо;
	
END  i21примУплотнение.

Чтобы выполнить процедуру, нужно кликнуть по коммандеру (черному кружку):

"i21примУплотнение.Демо('Вот пример  для    уплотнения           .')"

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

Ясно, что условие задачи было не совсем реалистичным. 
Более реалистичные варианты задачи оставляются в качестве упражнений.


Часть Д. Упражнения

Упражнение 1. Усовершенствовать процедуру так, чтобы полностью исключались пробелы в начале цепочки.
Подсказка. Достаточно изменить фрагмент инициализации цикла.

Упражнение 2. Усовершенствовать процедуру так, чтобы исключались все пробелы перед знаками препинания.

Упражнение 3. (а) Изменить процедуру так, чтобы исключить повторяющиеся вычисления:
 двукратное обращение к одному и тому же элементу массива a[i] на каждом шаге цикла (обращение к элементу массива подразумевает некоторые скрытые вычисления, в том числе проверку индексов на предмет выхода за границы массива), 
  двукратное обращение к элементу a[j].
Заметить, сколько на это потребовалось времени.

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

MODULE  i21примУплотнение;
	IMPORT  StdLog;
	
	PROCEDURE Проверить ( VAR a: ARRAY OF CHAR );
		VAR  кандидат: INTEGER;
	BEGIN  кандидат := 0;
		WHILE (кандидат < LEN(a)) & (a[кандидат] # 0X)  DO  INC( кандидат )  END;
		ASSERT( кандидат < LEN(a) )
	END Проверить;
	
	PROCEDURE Уплотнить* ( VAR a: ARRAY OF CHAR );
		VAR  i, j: INTEGER;
	BEGIN  Проверить( a );  i := 0;  j := 0;
		WHILE  a[j] # 0X  DO
			i := i + 1;
			IF  (a[i] # ' ') OR (a[j] # ' ')  THEN  j := j + 1;  a[j] := a[i]  END
		END
	END Уплотнить;
	
	PROCEDURE Уплотнить2* ( VAR a: ARRAY OF CHAR );
		VAR  i, j: INTEGER;  ai, aj: CHAR;  x: BOOLEAN;
	BEGIN  Проверить( a );  i := 0;  j := 0;  aj := a[0];
		WHILE  aj # 0X  DO
			i := i + 1;  ai := a[i];
			IF  (ai # ' ') OR (aj # ' ')  THEN  j := j + 1;  a[j] := ai;  aj := a[j]  END
		END
	END Уплотнить2;
	
	PROCEDURE Демо* ( цепочка: ARRAY OF CHAR );
		VAR  a: ARRAY 200 OF CHAR;
	BEGIN
		a := цепочка$;
		StdLog.String('до сжатия:');  StdLog.Ln;  StdLog.String(a);  StdLog.Ln;
		Уплотнить( a );
		StdLog.String('после сжатия:');  StdLog.Ln;  StdLog.String(a);  StdLog.Ln;
		a := цепочка$;
		Уплотнить2( a );
		StdLog.String('после сжатия 2:');  StdLog.Ln;  StdLog.String(a);  StdLog.Ln;
	END Демо;
	
	PROCEDURE Test*;
		VAR  a: ARRAY 200 OF CHAR;  i: INTEGER;
	BEGIN  FOR  i := 1  TO  1000000  DO  a := 'Вот  пример   для     сжатия     .';  Уплотнить( a )  END;
	END Test;
	
	PROCEDURE Test2*;
		VAR  a: ARRAY 200 OF CHAR;  i: INTEGER;
	BEGIN  FOR  i := 1  TO  1000000  DO  a := 'Вот  пример   для     сжатия     .';  Уплотнить( a )  END;
	END Test2;
	
END  i21примУплотнение.

"i21примУплотнение.Демо('Вот пример  для    уплотнения           .')"

i21примУплотнение.Test
i21примУплотнение.Test2