#import "@docs/bmstu:1.0.0":*
#import "@preview/tablex:0.0.8": tablex, rowspanx, colspanx, cellx
#show: student_work.with(
  caf_name: "Компьютерные системы и сети",
  faculty_name: "Информатика и системы управления",
  work_type: "лабораторной работе",
  work_num: "1",
  discipline_name: "Технология разработки программных систем",
  theme: "Выбор структур и методов обработки данных (Вариант 11)",
  author: (group: "ИУ6-42Б", nwa: "<NAME>"),
  adviser: (nwa: "<NAME>"),
  city: "Москва",
  table_of_contents: true,
)

= Цель лабораторной работы
Определить основные критерии оценки структуры данных и методов ее обработки применительно к конкретной задаче.

= Описание задания

== Задания

1. На основе теоретических сведений выделить критерии оценки структур данных, принципы работы и критерии оценки операций поиска, сортировки и корректировки.

2. В соответствии с вариантом задания (Вариант 11) предложить конкретную схему структуры данных (в задании указана абстрактная структура данных) и способ ее реализации на выбранном языке программирования.

3. Определить качественные критерии оценки (универсальность, тип доступа и др.) полученной на шаге 2 структуры данных с учетом специфики задачи по выданному варианту.

4. Определить качественные критерии оценки полученной на шаге 2 структуры данных: требуемый объем памяти на единицу информации, на структуру данных в целом и др.

5. Провести сравнительный анализ структуры данных, предложенной на шаге 2, на основе оценок, полученных на шаге 3 и шаге 4, с другими возможными вариантами реализации с целью поиска лучшей структуры данных к заданию по варианту.

6. Если цель шага 5 достигнута, то необходимо выполнить шаг 2, но для новой абстрактной структуры данных с указанием качественных и количественных критериев.

7. Оценить применимость метода поиска, который указан в варианте задания, с учетом структуры данных.

8. Если метод поиска применим, то необходимо сформулировать его достоинства и недостатки, используя качественные и количественные критерии: универсальность, требуемые ресурсы для реализации, среднее количество сравнений, время выполнения (такты) и др.

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

10. Оценить применимость метода упорядочивания, который указан в варианте задания, с учетом структуры данных.

11. Если метод упорядочивания применим, то необходимо сформулировать его достоинства и недостатки, используя качественные и количественные критерии: универсальность, требуемые ресурсы для реализации, среднее количество сравнений, время выполнения (такты) и др.

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

13. Оценить применимость метода корректировки, который указан в задании, к структуре данных.

14. Если метод корректировки применим, то необходимо сформулировать его достоинства и недостатки, используя качественные и количественные критерии: универсальность, требуемые ресурсы для реализации, время выполнения (такты) и др.

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

17. Определить основной режим работы программы и с учетом этого сделать выводы, а итоговые полученные результаты внести в таблицу. Из данной таблицы должно следовать, что предложенный альтернативный вариант решения задачи лучше. Как минимум должно быть одно улучшение, но могут быть заменены все методы обработки и сама структура данных.

#pagebreak()
== Основные требования

Основные требования приведены в таблице ниже:

#align(center)[
  #table(
    columns: 5,
    inset: 10pt,
    align: horizon,
    [Номер\ задачи],[Структура\ данных],[Поиск],[Упорядочение],[Корректировка],
    [2],[Таблица],[Вычисление\ адреса],[Пузырьком],[Удаление\ сдвигом],
  )
]

== Задача

Дана таблица материальных нормативов, состоящая из K записей фиксированной длины вида: код детали, код материала, единица измерения, номер цеха, норма расхода.

= Основной вариант

== Структура данных

В заданной таблице указана абстрактная структура данных -- таблица. Это означает, что нам необходимо явно выбрать структуру данных, элементы которой связанны неявно. Из задачи следует, что столбцами таблицы будут код детали, код материала, еденица измерения, номер цеха, норма расхода. Строками мы будем заносить записи.

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

#align(center)[
  #table(
    columns: 2,
    inset: 10pt,
    align: horizon,
    [Столбец],[Тип данных],
    [Код детали],[```cpp unsigned int```],
    [Код материала],[```cpp unsigned int```],
    [Единица измерения],[```cpp String (char[])```],
    [Номер цеха],[```cpp unsigned int```],
    [Норма расхода],[```cpp unsigned int```],
    [Номер записи],[```cpp unsigned int```],
  )
]

Везде (кроме единиц измерения) будем использовать беззнаковый целочисленный тип, для того, чтобы увеличить количество чисел, которые можно сохранить в двое, по сравнению со знаковым типом. Коды, номера изначально не могут быть отрицательными в силу здравного смысла. Норма расхода -- максимально допустимое плановое количество сырья, материалов, топлива, энергии на производство какой-либо единицы какой-либо продукции. Т. е. это значение тоже не может быть отрицательным, но в зависимости от единиц измерения оно может перестать быть целочисленным. В данной задаче не сказано, что это число будет вещественным, поэтому примем правило: если необходимо ввести вещественную норму расхода, необходимо ввести целую норму расхода и изменить еденицы измерения на более меньшие.

О номере записи опишем подробнее позже, когда будем рассматривать непосредственно алгоритмы.

После определения структуры необходимо задуматься о том, как хранить строки в памяти. Самым простым в реализации способом будет хранение их друг за другом -- в массиве. Таким образом общей структурой данных будет массив записей. Вот его схема: 

#img(image("dstruct.svg", width:94%), [Схема структуры данных])

=== Реализация структуры на языке C++

#let lab1 = parsercpp(read("lab1.cpp"))
#code(funcstr(lab1, "struct norm {") + "}", "cpp", [Структура данных ```asm norm```])

=== Расчет памяти, занимаемой массивом

Объем занимаемой памяти массивом $V = k V_э$, где $k$ — количество элементов, а $V_э$ — размер одного элемента. Множитель $k$ определяется пользователем, но не может быть динамически изменен. Размер элемента является суммой размера полей элемента. Рассчитаем эти размеры, учитывая, что 1 символ занимает 1 байт (в среднем сокращенные еденицы измерения занимают 2 символа):

$ V_э = l_"det" + l_"mat" + l_"mea" + l_"ws" + l_"cn" + l_"no" tilde.eq 4 times 5 + 3 = 23 $

Получаем $V = 23k$ байт.

Если массив статический, а $k$ неизвестно, то это приведет к неэффективному использованию оперативной памяти, а так же к ограничению к количеству записей изменить которое можно только в коде программы (для этого объявим ```cpp #define max 300```).

Необходимо пояснить, что ```cpp std::string``` является более сложной структурой, чем ```cpp char[]```, хотя бы из-за того, что в данной структуре можно легко оперировать с динамическим добалением элементов, но так как в процессе программы использования этого нет необходимости будем считать, что ```cpp std::string``` занимает столько же памяти, сколько и ```cpp char[]```.

=== Оценка времени доступа к $i$-му элементу

В массиве доступ выполняется по индексу. Для удобства мы храним адрес лишь первого элемента массива, поэтому для доступа мы должны прибавить к этому адресу $i$, что займет $t_"++" = 1$ такт, доступ к оперативной памяти осуществляется за $t_arrow = 1$ такт процессора.

$ T_д = t_"++" + t_arrow = 1 + 1 = 2 "такта." $

Стоит отметить, что из-за особенностей адресного поиска доступ к i-тому элементу в данной реализации будет $T_"ди" = 2 i "такта"$. Но операции поиска и сортировки будут выполняться по индексам ($T_д = 2$ такта), поэтому доступ к элементам (не по индексу, а по номеру записи) будет необходим только в процессе вывода или удаления элементов.

=== Оценка времени удаления $i$-го элемента

При удалении мы переписываем весь массив на одну ячейку влево, начиная с $i$-го элемента, поэтому удаление -- это перезапись $k-i$ элементов. (подробнее см. 3.4.3)

== Метод поиска

Поиск необходимо реализовать адресный. Адресный поиск -- один из самых эффективных по времени методов поиска. Он предполагает связь искомой ячейки и индекса записи. Так как значения заренее не извесны, создать функцию поиска индекса по значению можно только проиндексировав динамически массив. Это возможно сделать в виде структур ключ-значение. Возьмем для этого структуру хеш-таблицы, куда динамически будем при записи заносить значения в виде ключей, а значениями хеша будет выступать односвязный список -- одно значение может быть в нескольких записях. Список использовать будем из-за того, что результат поиска необходимо выводить весь, т.е. использовать доступ к элементам не по их порядку нет необходимости.

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

#code("typedef unordered_map<unsigned int, list<int> > uimap;
typedef unordered_map<string, list<int> > smap; 
uimap maps[4] = {{},{},{},{}};
smap  measureMap = {};
", "cpp", "Объявление новых типов и переменных для поиска")

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

Алгоритм поиска будет возвращать список с индексами найденных элементов, так как сами элементы не упорядочены по этому индексу доступ к элементам усложняется (будет равен $T_"ди"$). Для доступа к элементам будем использовать следующую функцию:

#code(funcstr(lab1, "unsigned int idxSearch(unsigned int idx){")+"}", "cpp", [Ищем запись с индексом `idx`])

Эта функция принимает "статический" индекс записи и возвращает индекс записи в массиве. При этом используется последовательный поиск по массиву.

=== Реализация метода поиска


#code(funcstr(lab1, "list<int> adressSearch(string icol, bool wo){")+"}", "cpp", [Метод адресного поиска])

Тут мы передаем в функцию номер колонки, по которой будем искать и `wo` -- флаг, который указывает стоит ли выводить информацию о выходе из поиска после вывода результатов.

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

=== Среднее количество сравнений

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

$ C = 0 $

=== Оценка времени поиска

В лучшем случае, если не возникает коллизий поиск выполняется за время генерации хеша из ключа (для этого используются хеш-функции). Хеш-функций много, но основная задача у них одна: используя некоторую математическую базу обеспечить одностороннее преобразование ключа в хеш (обычно обратное преобразование не требуется). При этом создается структура, похожая на динамический массив, но для доступа к элементам используются не индексы, а хеши. Если возникают коллизии программа выделяет большую облать памяти для хранения всей хеш-таблицы и полностью переносит всю хеш-таблицу туда. При вставки значений в хеш-таблицу коллизий избежать не удастся, но при получении значения по ключу они возникают редко (или вообще не возникают, зависит от хеш-функции). Возьмем для примера хеш-функцию на делении, общее количество тактов при делении  -- 28, поэтому на получение одного значения по ключу будет уходить около 30 тактов.

=== Оценка занимаемой памяти

Хеш-таблицы являются некоторым компромиссом между временем (удаления, доступа, вставки) и занимаемой памятью. В таблице всегда есть незаполненное пространство, которое во избежание коллизий увеличивается с увеличением самой таблицы. Отношения памяти, заполненной данными ко всей выделенной под таблицу называют коэффициентом загрузки. Оптимальным коэффициентом считают значение $0.5$ и ниже, при этих значениях маленькая вероятность коллизии. Так как во всех записях обязательно должны быть значения их индексы обязательно попадут во все 5 таблиц.

$ V_"таб" = 1/"к-т загрузки" times 5 times v_"int" times k = 40 k "байт" $

== Метод упорядочивания

Метод сортировки пузырьком заключается в том, что наибольшие элементы "всплывают" (отсюда название -- пузырек) в вверх массива. Для этого просто сравниваются два рядом стоящих элемента и если у элемента, индекс в массиве которого меньше, большее значение, то они меняются местами (при этом меняется их индекс в массиве, номер записи остается неизменным). Далее тот же элемент сравнивается со следующим элементом, если он больше, то снова элементы меняются местами и так далее.

Так как сравниваются постоянно два элемента для реализации необходимо использовать вложенный цикл: первый элемент -- тот, который будет "всплывать" будет с индексом `i` (`i = range(0, n)`), второй элемент -- тот, с которым будем сравнивать первый, будет с индексом `j` (`j = range(i+1, n)`). Таким образом в худшем случае -- когда массив отсортирован по убыванию будет необходимо пройти по всем элементам $n^2$ раз, а в лучшем, когда массив отсортирован, $n$ раз.

=== Реализация метода упорядочивания

#code(funcstr(lab1, "void bubbleSortUi(int nocol){")+"}\n\n"+funcstr(lab1, "void bubbleSortStr(){")+"}", "cpp", [Метод сортировки пузырьком])

Так как сравнения у целочисленного типа и строк сильно отличаются создадим две функции, для охвата всех полей таблицы. Отличаться тут будет только само условие: для целочисленного типа используем оператор больше, для строк используем функцию, которая последовательно сравнивает все буквы в строке, до того момента, как номер букв (в кодировке) в двух строках не будет отличаться, затем возвращет число, насколько этот номер отличается. Если это число больше 0, то вся запись с этой строкой "всплывает", таким образом получаются записи, отсортированные в алфавитном порядке относительно единиц измерения.

=== Среднее количество сравнений

Внутри цикла мы сравниваем 2 значения (не важно какого типа), так как значение не должно сравниваться само с собой для каждого `i`-того элемента есть `k-1` значений, всего таких элементов `k`, поэтому получим:

$ C_"пуз" = k times (k-1) $


=== Оценка времени упорядочивания

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

$ T_"if" = 2 times (T_д + T_"get") + T_> + t_"if" = 2 times (2 + 2) + 2 + 1 = 11 "тактов" $

$ T_"in_if" = 3 times t_= + 4 times T_д  = 3 times 2 + 4 times 2 = 14 "тактов" $

Мы можем войти в условие по вероятности $p = 0.5$, тогда общее время упорядочивания будет равно:

$ T_"пуз" = С_"пуз" times (T_"if" + p times T_"in_if") =\ = k times (k-1) times (11+0.5 times 14) = 18  k (k-1) "тактов" $

=== Оценка занимемой памяти

Так как все изменения происходят непосредственно в массиве, память используется только для индексов и замены записей местами.

$ V = 31 "байт" $


#pagebreak()
== Метод корректировки

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

=== Реализация метода корректировки


#code(funcstr(lab1, "void removeOffsetIndex(unsigned int index, bool wo){")+"}", "cpp", [Метод удаления сдвигом])

В удалении мы используем тот же флаг, что и при выводе, чтобы при необходимости дать возможность пользователю выйти.

Удаление происходит в 3 этапа: по номеру записи находится индекс записи в массиве, номер записи удаляется из всех хешей, где он был в списках, что бы адресный поиск больше не смог найти индекс удаляемой записи и сама запись удаляется сдвигом из массива записей.

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

#code(funcstr(lab1, "void removeOffsetArray(list<int> indexes){")+"}", "cpp", [Метод удаления сдвигом (по полям)])

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

Необходимо так же показать реализацию метода поиска номера записи в списке. Предполагается, что списки, средней длиной $n << k$. При $k = 300$ длина списка в среднем будет равна $5$-$10$ из логических соображений. Таким образом поиск по списку можно реализовать последовательный, при этом удаление все равно будет происходить быстро.

#code(funcstr(lab1, "list<int>::const_iterator whereList(const list<int>& l, int a) {")+"}", "cpp", [Последовательный поиск индекса в списке])

Поиск реализован так, что возвращает итератор, поэтому `erase` не проходится 2-ой раз по списку, а сразу освобождает элемент и переделывает ссылки предыдущего и следующего элемента (`std::list` - двусвязный список, но можно использовать собственную реализацию односвязного списка, тогда сравнивать необходимо, сохранив предыдущее значение и возвращать предыдущее значение. В целом для данной реализации это единственное отличие двусвязного списка от односвязного).

=== Среднее количество сравнений

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

$ C_"уд" = (5 times n)/2  + k/2 = (5 times k/42)/2 + k/2 = (5 times k + 42 times k)/84 = (47k)/84 $

=== Оценка времени удаления

Удаление, как было сказано ранее, происходит в 3 этапа, первые 2 по времени выполнения будут равны 

$ T_"поиск" = (2 times T_д) times k/2 + (2 times T_arrow) times (5 k)/84 = 2k + (5k)/84 = 173/84 k "тактов" $
со
Видно, что поиск уже занимает достаточно много времени, решение этой проблемы заключается в выборе альтернативной структуры данных. (альтерантивное решение)

Для удаления тоже потребуется некоторое число тактов, а именно доступ и запись k-i (в среднем $k/2$) элементов.

$ T_"уд" = (T_д + T_=) times k/2 = 4 times k/2 = 2k "тактов" $

$ T_"уд_общ" = T_"поиск" + T_"уд" = 173/84 k + 2k = 341/84 k tilde.eq 4k "тактов" $

Эффективное по времени удаление данных из массива в лучших случаях достигает 3-4 такта, будем стремиться к этому в альтернативном варианте.

=== Оценка освобождаемой памяти

При удалении освобождается память, занимаемая списками в хешах, но из-за статического масссива при затирании элементов длина массива не сокращается, т.е. даже после удаления элемента память, выделенная для него остается, так как в задании нет необходимости реализации добавления новых элементов эта память остается пустой в конце массива до завершения программы. За каждое удаление мы освобождаем от данных 23 байта. Полностью освобождается только память, занимаемая номером в списках, т.е. 20 байт.

= Альтернативный вариант

== Структура данных

В основном случае был расмотрен неплохой вариант организации таблицы. Поиск выполняется за константу, что при большом количестве элементов все равно лучше, чем зависимость от этого количества. Хорошим показателем памяти обладает алгоритм упорядочивания. Алгоритм удаления вышел самым неэффективным -- во-первых память после удаления элемента не освобождается, во-вторых для удаления необходимо пройти по всем элементам несколько раз.

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

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

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

Будем использовать динамический массив, который будет хранить в себе номера записей, при сортировке эти номера будут меняться местами, а если i-тый (i - номер элемента, а не индекс в массиве) элемент удален, то поставим в его еденицы измерения "\~", как флаг удаленного элемента (сборщик мусора потом пройдет по этому массиву и удалит все записи с "\~" как из массива, так и из памяти). 

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

Предыдущая сортировка эффективна по памяти, но по времени она проигрывает быстрой сортировке, поэтому в данном решении будем использовать сортировку Хоара.

Адресный поиск оставим без изменений, он эффективен по времени.

Вот схема структуры данных для альтернаятивного решения:

#img(image("dastruct.svg", width:80%), [Схема структуры данных для альтернативного решения])

=== Реализация структуры на языке C++

#let lab1a = parsercpp(read("lab1a.cpp"))
#code(funcstr(lab1a, "struct norm {") + "}", "cpp", [Структура записей ```asm norm```])
#code("typedef unordered_map<unsigned int, norm > tytbl; 
tytbl tbl;
vector<int> stbl;
", "cpp", [Объявление хеш-таблицы записей и дин. массива индексов])

=== Рассчет памяти, занимаемой структурой

Память занимаемая структурой состоит из 2 частей: память массива и память хеш-таблицы.

$ V_"хеш" = 1/"к-т загрузки" times V_"зап" times k =  k/"к-т загрузки" times \ times (l_"det" + l_"mat" + l_"mea" + l_"ws" + l_"cn") tilde.eq k/0.5 times (4 times 4 + 3) = 38k "байт" $

$ V_"мас" = V_"int" times k = 4k "байт" $

$ V_"ст" = V_"хеш" + V_"мас" = 46k + 4k = 42k "байт" $

Почусили на $14k$ байт больше, чем в прошлой реализации, но тут данные хранятся динамически, поэтому $k$ вводится в процессе выполнения программы и может быть изменено. При большом разбросе количества записей этот факт может компенсировать увеличение объема памяти. 

=== Оценка времени доступа к $i$-му элементу

Увеличение памяти, занимвемой структурой приводит к уменьшению времени доступа к элементам.

Доступ к элементам может быть через индекс массива $T_д$ или через номер элемента $T_"ди"$.
Так как теперь эти два индекса связанны в одном массиве, то справедливо равенство

$ T_д = t_"++" + t_arrow + T_"ди" = 2 + T_"ди" "тактов"  $

В части 3.2.3 оценено примерное время доступа к одному значению по ключу:

$ T_"ди" = 30 "тактов" $

Как мы видим теперь оба доступа к значениям константы, что хорошо для большого количества значений.

=== Оценка времени удаления $i$-го элемента

list<int> adressSearch(string icol, bool wo);
Так как удаляется не каждый элемент, введем ```cpp #define ev 10```, где 10 -- количество вызовов, через которое элементы будут удаляться. Общее удаление будет происходить сдвигом, размер сдвига будет увеличиваться, каждый раз, когда будет необходимо пропустить(затереть) текущий элемент и таким образом к концу прохода массива сдвиг будет равен `ev`. Очищать будем и хеш и массив, всего необходимо очистить за 1 раз $46 "ev"$ байт. (подробнее см. 4.4.3)

#pagebreak()
== Метод поиска

=== Реализация метода поиска

#code(funcstr(lab1a, "list<int> adressSearch(string icol, bool wo){") + "}", "cpp", [Метод адресного поиска])

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

=== Среднее количество сравнений

$ C = 0 $

=== Оценка времени поиска

На получение одного значения по ключу, в среднем, уходит около 30 тактов

=== Оценка занимаемой памяти

$ V_"таб" = 1/"к-т загрузки" times 5 times v_"int" times k = 40 k "байт" $



== Метод упорядочивания

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

=== Реализация метода упорядочивания

#code(funcstr(lab1a, "void qSortI(vector<int>::iterator stbl, int k){") + "}", "cpp", [Сортировка Хоара для номеров записей])

#code(funcstr(lab1a, "void qSortUi(int nocol, vector<int>::iterator stbl, int k) {") + "}\n"+ funcstr(lab1a, "void qSortStr(vector<int>::iterator stbl, int k){") + "}", "cpp", [Сортировка Хоара для целочисленного и строкового типа])



В данной реализации я решил создать 3 разные функции сортировки: для целочисленных, строквых полей и номеров записей в массиве.

=== Среднее количество сравнений

В данной сортировке используются 2 сравнения: сравнения с центральным элементом и сравнения индексов. Для начала посчитаем все для одного прохода. Тут $n$ - кол-во обрабатываемых элементов, на первой итерации оно совпадает с k, на второй вдвое меньше и т.д.

В цикле произойдет от 1 до $n/2$ сравнений индексов, но по статистике в этот цикл входят повторно с 40% вероятностью (К. Дин "Простой анализ ожидаемого времени выполнения для рандомизированных алгоритмов “разделяй и властвуй”"). После цикла условия входа в рекурсию.

$ C_"инд" = 1 + 0.4 + 2 = 3.4 $

В цикле 2 раза войдем в цикл с $n/4$ в среднем значений, основной цикл выполняется  

$ C_"piv" = 1.4 times (n/4 + n/4)  = 1.4 times n/2 = 0.7n $

$ C_"общ" = C_"инд" + C_"piv" = 3.4 + 0.7n $

Так как мы постоянно разделяем массив на 2 всего функцию мы вызовем примерно $2 k$ раз.

$ C_"общ_rec" = (3.4 + 0.7n) times 2 k $

Причем $n = log_2 k$

$ C_"общ_rec" = 6.8k + 2k log_2 k $

=== Оценка времени упорядочивания

Для начала посчитаем такты для одной функции, затем умножим на $2k$ это значение и подставим $n = log_2 k$ 

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

$ T_"инд" = 4 times C_"инд" = 13.6 $

$ T_"piv" = T_д times C_"piv" = 30 times 0.7n = 21n $

$ T_"общ" = T_"инд" + T_"piv" = 13.6 + 21n $

$ T_"общ_rec" = 27.2k + 42k log_2 k $

=== Оценка используемой памяти

Функция рекурсивная, поэтому до окончания ее выполнения занимает некоторое место в стеке, но в сегменте данных она ничего не выделяет и работает только с текущим массивом, поэтому можно считать, что место используется только для хранения адреса массива, 2 индексов и серединного элемента. И так для каждой из $2k$ вызываемых рекурсивно функций.

$ V = 2k times (4+2 times 4 + 4) = 32k "байт" $

В результате получаем, что для организации рекурсии используется $32k$ байт стека. Но любая рекурсия может быть организована с помощью цикла, поэтому этой памятью можно принебречь.

== Удаление маркировкой и сдвигом


=== Реализация метода удаления маркировкой и сдвигом

#code(funcstr(lab1a, "void removeMarkIndex(unsigned int index, bool wo){") + "}", "cpp", [Удаление маркировкой по индексу])

Глобальная переменная ```cpp evi``` теперь считает количество удаленных элементов, если их теперь столько, сколько и выставленный предел все элементы одним циклом удаляются полностью. Иначе просто заменяем еденицу измерения "\~" и элементы не отображаются (так написана функция отображения).

Идея с удалением по столбцам осталась такой же, поменялся только код реализации удаления.
Удаление из хешей (для адресного поиска) тоже не изменилось, но ушло в отдельную функцию для лучшей читаймости кода.

=== Среднее количество сравнений

Сравнения требуются только при очистке и их ровно $k$.

$ C_"уд" = k/"ev" $

=== Оценка времени удаления

Для начала разберем время без очистки: оно расходуется только на добавление "\~".
$ T_"уд" = T_д + t_"++" + t_"=" = 30 + 2 + 2 = 34 "такта" $

При очистке мы проходим весь массив так же, как это делали каждый раз в основном решении.
$ T_"оч" = 2k $

$ T_"общ" = T_"уд" + T_"оч"/"ev" = 34 + (2k)/"ev"  $

=== Оценка освобождаемой памяти

Понятно, что удаление будет самым быстрым, если `ev` будет большим, но с другой стороны, с каждым увеличением `evi` мы используем большее количество ненужной памяти. Одна запись в таблице занимает 42 байта. В массиве хранится индекс, который занимает 4 байта. В хешах адресного поиска хранится 20 байт индексов.

$ V_"ос" = (42+4+20)*e v = 66 e v "байт" $

= Таблица результатов и вывод

#align(center)[
  #tablex(
    columns: 5,
    inset: 10pt,
    align: center + horizon,
    map-cells: cell => {
      if (cell.x == 3 and cell.y == 3 or
          cell.x == 1 and cell.y == 3 or
          cell.x == 4 and cell.y == 8 or
          cell.x == 3 and cell.y == 9 or
          cell.x == 4 and cell.y == 9 or
          cell.x == 1 and cell.y == 10 or
          cell.x == 3 and cell.y == 10 or
          cell.x == 4 and cell.y == 10
         ){
        cell.content = {
          let text-color =  green.darken(20%)
          set text(text-color)
          strong(cell.content)
        }
      }
      if (cell.x == 2 and cell.y == 3 or
          cell.x == 2 and cell.y == 4 or
          cell.x == 2 and cell.y == 5 or
          cell.x == 2 and cell.y == 8 or
          cell.x == 2 and cell.y == 9 or
          cell.x == 2 and cell.y == 10
         ){
        cell.content = {
          let text-color =  yellow.darken(20%)
          set text(text-color)
          strong(cell.content)
        }
      }
      cell
    },
    [],[Структура\ данных],[Метод\ поиска],[Метод\ упорядочения],[Метод\ корректировки],
    colspanx(5)[*Основной вариант*],
    [Название],                           [Массив\ записей],[Адресный\ поиск],[Сортировка пузырьком],[Удаление смещением],
    [Занимаемая/\ освобождаемая память (байт)],  [$23k$],   [$40k$],[$31$],             [$23(p) + 20$],
    [Среднее\ количество\ сравнений],            [--],      [$0$],  [$k times (k - 1)$],[$ 47/84 k $],
    [Занимаемое\ время\ (такты)],                 [$2$/$2i$],[$30$],[$18k(k-1)$],[$ 341/84 k $],
    colspanx(5)[*Альтернативный вариант*],
    [Название],                                  [Массив\ индексов#h(4pt)и \хеш-таблица],[Адресный\ поиск],[Сортировка\ Хоара],[Удаление маркировкой и смещением ],
    [Занимаемая/\ освобождаемая память (байт)],  [$42k$],[$40k$],[$32$],[$66"ev"$],
    [Среднее\ количество\ сравнений],            [--],[$0$],[$6.8k +$ $+ 2k log_2 k$],[$ k/"ev" $],
    [Занимаемое\ время\ (такты)],                [$32$/$30$],[$30$],[$27.2k+$ $+42k log_2 k$],[$32$],
  )
]

Как видно из таблицы, альтернативный вариант выигравает основной по времени (во всех методах) и по освобождаемой памяти, но занимет больше места в оперативной памяти.

== Вывод
В результате выполнения лабораторной работы были проведены качественные и количественные оценки структур данных и методов их обработки в соответствии с вариантом задания. В альтернативном варианте предложены решения, которые обеспечат более эффективные поиск, сортировку
и удаление данных.

= Приложения

В процессе разработки лабораторной работы для отладки методов были созданы два консольных приложения. Ниже приведен код этих приложений.
== Основной вариант
#let lab1 = read("lab1.cpp")

#show raw: block.with(
  fill: luma(240),
  inset: 9pt,
  radius: 4pt,
)

#align(left+top)[
#raw(writeft(lab1, 0, 38),lang:"cpp")

#raw(writeft(lab1, 44, 84),lang:"cpp")

#raw(writeft(lab1, 85, 125),lang:"cpp")

#raw(writeft(lab1, 126, 166),lang:"cpp")

#raw(writeft(lab1, 167, 208),lang:"cpp")

#raw(writeft(lab1, 209, 249),lang:"cpp")

#raw(writeft(lab1, 250, 290),lang:"cpp")

#raw(writeft(lab1, 291, 331),lang:"cpp")

#raw(writeft(lab1, 332, 365),lang:"cpp")

#raw(writeft(lab1, 366, 382),lang:"cpp")
]

== Альтернативный вариант

#let lab1 = read("lab1.cpp")

#align(left+top)[
#raw(writeft(lab1, 0, 18),lang:"cpp")

#raw(writeft(lab1, 20, 63),lang:"cpp")

#raw(writeft(lab1, 66, 110),lang:"cpp")

#raw(writeft(lab1, 111, 155),lang:"cpp")

#raw(writeft(lab1, 156, 195),lang:"cpp")

#raw(writeft(lab1, 196, 239),lang:"cpp")

#raw(writeft(lab1, 240, 279),lang:"cpp")

#raw(writeft(lab1, 280, 323),lang:"cpp")

#raw(writeft(lab1, 324, 356),lang:"cpp")

#raw(writeft(lab1, 358, 382),lang:"cpp")
]


