Упорядоченное множество и пропуск лишних шагов
Множество в виде возрастающего списка прекращает поиск после прохождения цели и объединяет два множества без повторного просмотра префикса.
Какая работа становится излишней, если представление множества гарантирует возрастающий порядок?
- Рассмотрение возрастающего порядка как инварианта представления
- Остановка поиска принадлежности после первого элемента больше целевого
- Продвижение по хвосту одного или обоих множеств после сравнения их голов
- Сохранение порядка объединения при удалении дубликатов
element-of-ordered-set? сравнивает целевой элемент с каждой текущей головой. При равенстве поиск успешен, при меньшем целевом значении поиск сразу завершается неудачей, и только больший целевой элемент оправдывает переход к хвосту. Поэтому поиск 4 проверяет 1, 3 и 5, но никогда не доходит до 7 или 9.
union-ordered-set сравнивает две головы. Процедура сохраняет меньший элемент и продвигает этот список, а равные головы дают один элемент и продвигают оба списка. Каждый рекурсивный шаг потребляет хотя бы одну текущую голову, сохраняя упорядоченность без повторного поиска с самого начала.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает (#f 3). Вторая программа возвращает (1 2 3 5 6 8 9).
Найдите сравнение с 5, которое завершает поиск принадлежности до 7 и 9. При объединении наблюдайте, как каждое сравнение голов потребляет левый, правый или оба списка, в то время как результат остается возрастающим. Эти трассы выполнения опираются на то, что предоставленные входные данные уже являются упорядоченными множествами.
Измените программу и сравните результат.
Напишите intersection-ordered-set с таким же сравнением двух голов. Заранее определите пересечение двух предоставленных входных множеств для объединения.
Показать подсказку
Сохраняйте значение только тогда, когда обе головы равны. В противном случае отбрасывайте меньшую голову.