[cdev] Задания для 135-й группы

[Grigoriy A. Sitkarev]

Я действительно что-то утомился сегодня.

Даже отправил почему-то 135-й группе совсем не то что нужно.

Сейчас исправим положение.

------------>8-------------------------------------------

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

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

Для создания и манипулирования со структурами потребуются ф-ии 
динамического выделения памяти malloc(3), free(3), realloc(3).

1.  Абстрактный тип "односвязанный список" и функции для работы с ним. 
Операции со списком "добавить", "добавить в конец", "удалить", "поиск 
элемента списка", "проход списка", "сортировка списка по заданной ф-ии 
сравнения", "получить n-й элемент", "получить первый элемент". Элементом 
списка является указатель на void (т.е. любой тип данных можно поместить 
в список).

2. Абстрактный тип "двусвязанный список" и функции для работы с ним. 
Операции со списком аналогично заданию 1 плюс проход списка может 
выполняться и в обратном порядке.

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

+ "подрастание" таблицы с переселением элементов в новую при 
коэффициенте заполнения > 2.0 или < 0.3.

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

В качестве хеш-функции выбрать любую стандартную хеш-функцию (по 
умолчанию) и дать возможность назначать через API такую функцию 
самостоятельно при создании таблицы.

Элементом таблицы является указатель на void (т.е. любой тип можно 
поместить в хеш-таблицу).

4. Абстрактный тип "динамический массив указателей". Операции "создать 
массив", "добавить элемент", "удалить элемент", "взять n-й элемент", 
"заменить элемент", "поиск элемента по ключу", "сортировка массива", 
"уничтожить массив", "получить количество элементов в массиве". 
Подобрать эмпирически метод увеличения/уменьшения размера массива по 
мере добавления/удаления элементов в/из него.

Функцию для сравнения элементов массива можно задать при создании 
массива. Элементом массива является указатель на void (т.е. любой тип 
можно поместить в динамический массив).

5. Абстрактный тип "бинарное дерево" (не сбалансированное). Операции 
"создать дерево", "добавить элемент в дерево", "удалить элемент из 
дерева", "заменить элемент в дереве", "поиск элемента по ключу", "проход 
дерева".

+ поиск ближайшего большего и ближашего меньшего.
+ предложить варианты балансировки дерева.

Функция для сравнения элементов дерева - аналогично 4.

Элементом дерева является указатель на void (т.е. любой тип можно 
поместить в дерево).

6. Абстрактный тип "очередь" (queue). Предлагается использовать простой 
алгоритм кучи (heap queue). Операции "создать очередь", "добавить 
элемент в очередь", "удалить элемент из очереди", "вынуть следующий 
элемент из очереди", "подглядеть следующий элемент очереди", "уничтожить 
очередь".

+ предложить варианты усовершенствованных алгоритмов, например MinMax 
Heap, широко описанные в литературе (искать в сети Интернет).

Функция для сравнения элементов очереди - аналогично 4.

Элементом очереди является указатель на void (т.е. из любых типов и 
структур можно создать очередь).

7. Абстрактный тип "словарь" (dictionary), представляющий возможность 
сортированного (и несортированного) хранения пары ключ->значение. 
Предлагается использовать простой алгоритм "сортировка при вставке" 
(insertion sort). Операции "создать словарь", "добавить ключ в словарь", 
"удалить ключ из словаря", "поиск данных по ключу", "заменить данные 
ключа", "уничтожить словарь".

+ предложить варианты усовершенствования алгоритмов или структур данных.

Элементом очереди является указатель на void (т.е. из любых типов и 
структур можно создать словарь).

Ключом как правило является строка, память для хранения строки 
выделяется программистом.

8. Абстрактный тип "n-мерное дерево", представляющий возможность иметь 
каждому элементу дерева множество (а не два, как в бинарном дереве) 
потомков. Операции "создать n-мерное дерево", "добавить элемент как 
потомка слева/справа", "удалить элемент", "обход всех элементов дерева", 
"обход всех элементов по уровням", "уничтожить дерево".

+ предложить реализацию сортированного n-мерного дерева (в котором 
потомки на каждом уровне находятся в сортированном порядке);
+ предложить усовершенствования алгоритмов и структур данных.

Элементом дерева является указатель на void (т.е. из любых типов и 
структур можно создать n-мерное дерево).

9+. Аллокатор памяти по методу близнецов (buddy memory allocator).

Легенда:

По какой-то причине нас не устраивает стандартный аллокатор библиотеки 
Си и мы вынуждены реализовывать свой. В таком случае стандартный 
malloc(3) и free(3) используется только для начального выделения кусков 
памяти максимального размера, в предположении что они эффективны именно 
для этого случая.

Суть метода в следующем:

Аллокатор выделяет куски памяти размером кратным степеням двойки (т.е. 
от 2 до 2^x где x целое число). Таким образом, требуется определить 
лимиты для верхней и нижней границы (u и l). Слотом мы будем называть 
свободный блок памяти, пригодный для аллокации.

Для того чтобы выделить блок размера k аллокатор поступает следующим 
образом:

1. Искать слот подходящего размера. Это должен быть минимальный блок 
размера 2^n, такой чтобы он был больше или равным размеру аллоцируемой 
памяти. Учтите, что общий размер блока будет по всей видимости включать 
и накладные расходы на хранение его "заголовка" со служебными данными.

    1. Если такой слот найден, то он выделяется вызывающей программе.

    2. Если такого слота не нашлось, то пытаемся создать подходящий
    свободный слот. Для этого:

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

Если требуется освободить память аллокатору:

1. Освободить блок памяти.
2. Посмотреть, нет ли свободного соседнего блока слева или справа?
3. Если такой блок есть, то собрать их в один, перейти на шаг 2 и 
повторить процесс пока не достигнут верхний предел или пока не 
встретится несвободный блок.

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

Предлагается реализовать простой аллокатор по методу близнецов, при этом 
параметры l (минимальный размер блока) равен 2^6 (64 байта) а u 
(максимальный размер блока) равен 2^12 (4096 байт). Максимальный размер 
таким образом равен размеру страницы на машине x86 и x86-64 и других 
архитектур, минимальный выбран из соображений баланса "размер/накладные 
расходы на хранение описания блока".

Данный метод описан в книге Д.Кнута (1-й том монографии), а впервые 
опубликован в 1965 году.

API для аллокатора копирует поведение malloc(3) и free(3).

+ реализовать функцию, копирующую поведение realloc(3).

------------8<-------------------------------------------

Grigoriy A. Sitkarev пишет:
> 
> Действительно, список заданий уже отправлялся в список.
> 
> http://wiki.syktsu.ru/pipermail/cdev/2010-September/000220.html