---

Рис. 16
В конце концов, поступит символ S5, который ссылается на указатель, использовавшийся ранее, например на 6. Вот здесь и начинает действовать поле CHAIN. Символ S5 записывается в таблицу символов и добавляется к концу цепочки для этого указателя (рис. 17).

№	Хеш-таблица		№	Аргумент	Значение	CHAIN	Ук=5
0			1	S1	…	0
1	2		2	S2	…	0
2			3	S3	…	0
3	3		4	S4	…	5
4	1		5	S5	…	0
5
6	4

Рис. 17
Пусть необходимо внести в таблицу символы S6, S7, S8, которые ссылаются на указатели 4, 3, 3 соответственно (рис. 18).

№	Хеш-таблица		№	Аргумент	Значение	CHAIN	Ук=8
0			1	S1	…	6
1	2		2	S2	…	0
2			3	S3	…	7
3	3		4	S4	…	5
4	1		5	S5	…	0
5			6	S6	…	0
6	4		7	S7	…	8
			8	S8	…	0

---

Рис. 18

Контрольные вопросы

1. 
   В каком типе организации таблиц символов поиск элемента требует сравнения с каждым элементом таблицы, пока не будет найден подходящий?
   
2. 
   Сколько самое большее сравнений бинарный поиск требует для n=128 элементов?
   
3. 
   Какой метод рехеширования состоит в том, что принимаем p1=1, p2=2, p3=3 и т.д.?
   
4. 
   В этом типе рехеширования принимается pi=i*h, где h- исходный хеш-индекс.
   
5. 
   Какое поле в методе цепочек используется для того, чтобы связать в цепочку элементы, для которых хеширование символа приводит к тому же самому указателю?
   
6. 
   Для чего нужна кодировочная таблиц?
   
7. 
   Для чего служит таблица символов?
   
8. 
   Как организуется таблица символов?
   
9. 
   В чём состоит метод бинарного поиска?
   
10. 
    Что такое хеширование?
    
11. 
    Как работает метод цепочек?
    
12. 
    Какие известны способы рехеширования?
    
13. 
    Как сравниваются известные способы организации таблиц символов?
    
14. 
    В чём суть методов бинарного поиска и упорядоченных
    вставок?
    
15. 
    Каковы достоинства хеш-адресации и, каковы её недостатки?
    
16. 
    Какие известны способы рехеширования?
    
17. 
    В чём преимущество метода цепочек по сравнению с рехешированием?
    
18. 
    Какая информация хранится в таблице символов?
    
19. 
    Как записать информацию о переменных?
    

Лекция 4. ОПТИМИЗАЦИЯ КОДА
План:

1. 
   Машинно-зависимая оптимизации
   
2. 
   Машино-независимая оптимизация
   
3. 
   Методы оптимизации кода
   

Ключевые слова: общие подвыражения, инварианты цикла.
Рассмотрим некоторые методы машинно-независимой оптимизации кода. Мы не будем стремиться к детальному описанию какого-либо из этих методов. Вместо этого мы дадим словесное описание и проиллюстрируем основные понятия примерами. Алгоритмы и детали, касающиеся этих методов можно найти в работах [2, 3].

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

VAR x,y: ARRAY [1..10,1..10] OF INTEGER;

…

FOR i : = 1 TO 10 DO

x [ i , 2*j-1 ] : = y [ i , 2*

---

j ];

…

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

Общие подвыражения обычно обнаруживаются при анализе промежуточной формы представления программы (рис. 19). Следует отметить, что в первоначальном варианте требуется выполнить 161 операцию.

Если мы исследуем эту последовательность четвёрок, то обнаружим, что четвёрки 5 и 11 совпадают, за исключением имени
получаемого промежуточного результата. Обратите внимание, что операнд j не меняет своего значения между четвёрками 5 и 11.

1)	: =	#1		I	инициализация цикла
2)		I	#10	(19)
3)	-	I	#1	i1	вычисление индексов для Х
4)	*	i1	#10	i2
5)	*	#2	J	i3
6)	-	i3	#1	i4
7)	-	i4	#1	i5
8)	+	i2	i5	i6
9)	-	I	#1	i8	вычисление индексов для Y
10)	*	i8	#10	i9
11)	*	#2	J	i10
12)	-	i10	#1	i11
13)	+	i9	i11	i12
14)	: =	Y[i12]		X[i6]	операция присваивания
15)	+	#1	I	i14	конец цикла
16)	: =	i14		I
17)	GOTO			(2)
18)	…				следующая операция

---

Рис. 19

Невозможно достичь четвёрки 11, не проходя предварительно четвёрку 5, поскольку они расположены на одном линейном участке.

Таким образом, четвёрки 5 и 11 вычисляют одно и тоже значение. Это означает, что мы можем удалить четверку 11 и заменить любые обращения к её результату (i9) на обращение к переменной i3, которая является результатом четвёрки 5. Эта модификация позволяет избежать дублирования вычислений подвыражения 2*j, которое мы выделили как общее подвыражение при анализе исходной программы.

После замены i3 на i10 мы обнаружим, что четвёрки 6 и 12 также совпадают, за исключением имени результата. Следовательно, мы можем удалить четвёрку 12 и заменить переменную i11 всюду, где она используется на переменную i4. Аналогично четвёрки 10 и 11 также могут быть удалены, поскольку они эквивалентны четвёркам 3 и 4.
В результате получим новую последовательность четверок (рис. 20), которая предполагает выполнение всего 121 операции.

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

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

1)	: =	#1		I	инициализация цикла
2)		I	#10	(14)
3)	-	I	#1	i1	вычисление индексов для Х
4)	*	i1	#10	i2
5)	*	#2	J	i3
6)	-	i3	#1	i4
7)	-	i4	#1	i5
8)	+	i2	i5	i6
9)	+	i2	i4	i12	вычисление индексов для Y
10)	: =	Y[i12]		X[i6]	операция присваивания
11)	+	#1	I	i14	конец цикла
12)	: =	i14		I
13)	GOTO			(2)
14)	…				следующая операция

---

Смотрите также файлы

• Финансовые инновации и рынок инновационных финансовых продуктов.docx

• Отчет о учебной практике по дисциплине Практические основы бухгалтерского учета активов организации в организации ооо Автоцентр Кемерово.docx

• Памятка для участников и организаторов.docx

• Соответственно, целью моего эссе будет выяснить, как совместить толерантность и свободу.docx

• Практическая работа к теме 1 Ценности и их роль для человека и общества Изучила контент (информацию).docx