Из сказанного уже может быть ясно, почему в методе близнецов ряд чисел экспоненциальный. В таком ряду числа растут очень быстро, поэтому в общую сумму ряда наибольший вклад вносят небольшое количество членов ряда, или иначе говоря небольших чисел существенно больше чем больших. Это соответствует ситуации с блоками данных, большинство которых также имеет небольшой размер. Кроме того, такой ряд будет как бы сам подстраиваться под реальную ситуацию с блоками данных.
Рассмотрим пример. Пусть мы имеем изначально следующий ряд: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, то есть ряд построенный на числах Фиббоначи. И есть следующие блоки данных: 1, 2, 1, 4, 4, 1. Посмотрим как будут распределяться наши блоки и что будет происходить с памятью. Занятые блоки будем помечать красным, а новые блоки синим.
Шаг 1: Блок данных объёмом 1 : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 2: Блок данных объёмом 2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 3: Блок данных объёмом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Шаг 4: Блок данных объёмом 4: 1, 1, 2, 3, 1, 4, 8, 13, 21, 34, 55
На этом шаге мы имеем небольшие потери. А именно пришлось использовать блок длины 5 для хранения блока данных длины 4
Шаг 6: Блок данных объёмом 1: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55
Не сложно заметить, что количество блоков небольшого размера увеличилось. А теперь попробуем оценить потери. Рассмотрим ещё один пример и на нём рассчитаем отношение занятой памяти реальными данными к памяти которую пришлось вычеркнуть и списка свободной памяти. Пусть необходимо разместить следующие блоки: 4,1, 6,7. Общая память 1, 1, 2, 3, 5, 8, 13,
Блок 4: 1, 1, 2, 3, 5 , 8, 13
Блок 1: 1, 1, 2, 3, 5 , 8, 13
Блок 6: 1, 1, 2, 3, 5 , 8, 13
Блок 7: 1, 1, 2, 3, 5 , 8, 5, 8
Итак получаем
| Требовалось | Использовано |
| 4 | 5 |
| 1 | 1 |
| 6 | 8 |
| 7 | 8 |
| Итого 18 | Итого 22 |
Отношение = 18/22=0,82 Это своего рода КПД (коэффициент полезного действия)
Конечно смотря с чем сравнивать. Если сравнить с двигателями внутреннего сгорания, то это очень высокий КПД.
Представим себе процесс поиска блока нужного размера. Пусть в ряду размеров нет никаких закономерностей. Тогда все, что нам остается это честно просмотреть весь ряд, а блок нужного размера вполне может оказаться в самом конце это ряда. Или даже ещё хуже ситуация : блок примерно подходящего размера нашёлся уже в самом начале, однако пока мы не просмотрим весь ряд нельзя абсолютно уверенно сказать, что нет лучшего варианта. Поэтому единственной возможностью закончить процесс поиска досрочно - это обнаружение идеального варианта, то есть такого блока памяти размер которого абсолютно точно равен размеру блока данных, а это событие маловероятно.
Если же ряд размеров свободных блоков подчиняется хорошо считаемой закономерности, то мы имеем сразу два удобства.
Во-первых, мы можем вычислить с некоторой точностью номер блока нужного размера. Причём некоторое время это вычисление можно выполнять абсолютно точно, и лишь когда начнётся процесс разбиения больших блоков на маленькие точные вычисления будет выполнять несколько сложнее.
Во-вторых, первый же найденный блок и будет оптимальным решением (потому как следующий будет уже больше и может быть даже существенно больше).
Все рассуждения, приведённые выше нужны только для того, чтобы сформулировать проблемы и очертить пути их решения. А вот ниже мы займёмся конкретным методом, называемым методом близнецов. Этот метод даёт ответ на следующие вопросы:
1. Как разбить память на блоки разного размера, так чтобы для любого блока данных нашелся нужный объём памяти.
2. Как упорядочить блоки свободной памяти, так чтобы поиск нужного блока велся максимально быстро.
3. Как организовать быстрое перераспределение памяти так, чтобы не было потребности перерабатывать всю память и составлять новый список свободных блоков.
Литература
1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.
2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.
3. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975
4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.
5. Машовцев В.А. Вступительные экзамены по информатике//Информатика. 1997, №13
6. Орлов В.А. О вступительных экзаменах по информатике//Информатика, 1997, №15
7. Яснева Г.Г. Логические основы ЭВМ//Информатика и образование, 1998, №2
8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999
9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.