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

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


courses:algorithms_structures:cw_2026:grade5:2

Вариант 5.2. Версии словаря и ветки

Постановка задачи

Рабочие пары key/value — редактируемые данные проекта, коммит — сохранённая версия, ветка — именованная линия изменений. Полная имитация настоящего Git не требуется.

Разработайте систему версий набора пар «ключ–значение». Пользователь изменяет рабочее состояние, сохраняет неизменяемые снимки, создаёт ветки, переключается между ними и сравнивает версии. Хранение большого числа почти одинаковых снимков должно экономить память.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

  • key, value, cid, имена веток и идентификаторы коммитов a/b — токены общего формата.
  • Сначала существует пустой коммит 0 и единственная ветка main, указывающая на него; main является текущей.
  • Рабочее состояние первоначально пустое. Коммит — неизменяемый снимок и идентификатор его родительского коммита.
  • В каждом состоянии не более 100000 пар. Все созданные коммиты и ветки сохраняются до завершения сценария.

Операции

Команда Действие Ответ
PUT key value Изменить или добавить пару в рабочем состоянии. OK
DEL key Удалить пару из рабочего состояния. OK; при отсутствии Error: NOT_FOUND
GET key Прочитать рабочее значение. VALUE value; при отсутствии NONE
COMMIT cid Создать новый снимок рабочего состояния. Его родитель — текущий коммит; текущая ветка передвигается на cid. OK; занятый cid — Error: EXISTS
BRANCH name Создать ветку на текущем коммите, не переключаясь на неё. OK; занятое имя — Error: EXISTS
CHECKOUT name Сделать существующую ветку текущей и заменить рабочее состояние её снимком. Несохранённые изменения теряются. OK; ветка отсутствует — Error: NOT_FOUND
READ cid key Прочитать значение из существующего снимка. VALUE value; ключ отсутствует — NONE; коммит отсутствует — Error: NOT_FOUND
DIFF a b Найти различия снимков a и b, по возрастанию ключа. ITEMS k, затем ADD key new, DEL key old либо MOD key old new; отсутствующий коммит — Error: NOT_FOUND
MERGE name Объединить текущую ветку с существующей веткой по описанным ниже правилам. OK; ветка отсутствует — Error: NOT_FOUND; недопустимое объединение — Error: STATE

Правила выполнения и ошибки

Пространства имён коммитов и веток независимы. COMMIT разрешён даже без изменений. BRANCH не сохраняет несохранённые рабочие пары и не переключает ветку. CHECKOUT, в том числе текущей ветки, отбрасывает несохранённые изменения. Родителем нового коммита становится вершина текущей ветки, а не последний по времени коммит другой ветки. Предком считается и сам коммит, и любой коммит, достижимый последовательным переходом к родителю.

MERGE требует, чтобы рабочие пары точно совпадали с текущим снимком; иначе STATE. Сначала проверяется существование целевой ветки. Если текущая вершина — предок целевой, текущая ветка и рабочее состояние заменяются целевой вершиной/снимком. Если целевая вершина — предок текущей, операция успешна без изменений. Если вершины разошлись, возвращается STATE. Нового коммита MERGE не создаёт, другая ветка не изменяется. Объединение произвольных конфликтующих изменений не требуется.

В DIFF направление — от a к b. ADD означает отсутствие ключа в a и наличие в b; DEL — наоборот; MOD — наличие в обоих с разными значениями. Неизменившиеся ключи не выводятся. Изменения рабочего состояния и переключения не меняют ранее сохранённые снимки.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

Пусть N — максимальное число пар в одном состоянии за сценарий; C — число сохранённых коммитов, включая 0; B — число веток, включая main; L — максимальная длина любого строкового поля. Обозначим M=L·log(C+B+2) — допустимую стоимость доступа к метаданным имён. PUT, DEL, GET — O(L·log(N+2)); READ — O(M+L·log(N+2)). COMMIT, BRANCH и CHECKOUT — O(M), без обхода всех пар. Для DIFF допустимо O(M+(na+nb+1)·L), где na и nb — числа пар в сравниваемых снимках. Для MERGE допустимо O(M+(N+1)·L+C): можно сравнивать рабочие пары и проходить историю. Эти границы относятся к худшему случаю, кроме отдельно оговорённого освобождения памяти.

Пусть U — суммарное число успешных PUT и DEL с начала сценария, включая повторную запись того же значения. При U таких изменениях суммарная память всех версий и рабочего состояния должна быть O((U+1)·L·log(N+2)+(C+B)·L), а не O(C·N·L). Способ повторного использования неизменённых данных выбирает студент. Освобождение уже недоступных данных можно учитывать амортизированно.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 5.2, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Ветки и продвижение к новой версии

Ввод:

1
10
PUT a x
COMMIT c1
BRANCH dev
PUT a y
COMMIT c2
CHECKOUT dev
GET a
MERGE main
GET a
READ c1 a

Вывод:

Course work for option 5.2, created by Ivan Ivanov.
OK
OK
OK
OK
OK
OK
VALUE x
OK
VALUE y
VALUE x

Пример 2. Направление сравнения

Ввод:

1
7
PUT a x
COMMIT c1
PUT a y
PUT b z
COMMIT c2
DIFF c1 c2
DIFF c2 c1

Вывод:

Course work for option 5.2, created by Ivan Ivanov.
OK
OK
OK
OK
OK
ITEMS 2
MOD a x y
ADD b z
ITEMS 2
MOD a y x
DEL b z

Пример 3. Разошедшиеся ветки

Ввод:

1
9
BRANCH dev
PUT a x
COMMIT left
CHECKOUT dev
PUT a y
COMMIT right
MERGE main
GET a
READ left a

Вывод:

Course work for option 5.2, created by Ivan Ivanov.
OK
OK
OK
OK
OK
OK
Error: STATE
VALUE y
VALUE x
courses/algorithms_structures/cw_2026/grade5/2.txt · Последнее изменение: — 127.0.0.1