Допустим. имеется какая-то область для хранения данных. Например, в флеш-памяти. Она последовательно заполняется блоками данных и с конца остается свободное место. Метод половинного деления позволяет избежать перебора всех данных. Если область вмещает 1000 позиций данных, тогда метод позволяет найти свободную позицию всего за 9 или 10 выборок данных. Если область вмещает миллион позиций, то выборок понадобится 19 или 20.
Метод реализован на языке Си в виде библиотеки из двух файлов. Файл div2-search.h пользователь должен приинклудить в своем проекте. А также пользователю требуется реализовать функцию bool div2_search_is_data(const unsigned position), которая будет сообщать функции поиска, есть ли данные в позиции position или нет. Функция поиска div2_search_free_position() вызывается пользователем. В нее передается количество позиций. Отработав, возвращает свободную позицию.
Архив с исходниками.
Файл div2-search.h:
// Дата: 01 сентября 2012
// Автор: Дмитрий Бравиков (bravikov@gmail.com)
//
// Реализация поиска свободного места в областе для хранения данных
// методом половинного деления.
//
// Функция div2_search_is_data() реализуется пользователем.
#ifndef DIV2_SEARCH_H
#define DIV2_SEARCH_H
#include <stdbool.h>
// Количество итераций в последнем поиске
extern unsigned div2_search_iteration_count;
// Возвращает true, если удалось обнаружить данные в позиции position.
bool div2_search_is_data(const unsigned position);
// Возвращает: свободную позицию; -1, если size = 0; size, если нет свободной.
int div2_search_free_position(const unsigned size);
#endif //DIV2_SEARCH_H
Файл div2-search.с:
// Дата: 01 сентября 2012
// Автор: Дмитрий Бравиков (bravikov@gmail.com)
// Описание: см. div2-search.h
#include "div2-search.h"
unsigned div2_search_iteration_count = 0;
int div2_search_free_position(const unsigned size)
{
// Диапазон поиска: [l,r)
unsigned l = 0; // Ограничение слева
unsigned r = size; // Ограничение справа
unsigned c = r / 2; // Текущая позиция
div2_search_iteration_count = 0;
if (size == 0) return -1;
while (r != l)
{
if ( div2_search_is_data(c) )
{
l = c + 1;
}
else
{
r = c;
}
c = l + (r - l) / 2;
div2_search_iteration_count++;
}
return c;
}
// Примеры поиска:
//
// ---------------------------------------------------------------------------
// Итерация: 2 4 3 1
// Позиция: 0 1 2 3 4 5 6 7 8 9 10 11
// Данные: * * * *
//
// Результат: 4
// ---------------------------------------------------------------------------
// Итерация: 1 4 3 2
// Позиция: 0 1 2 3 4 5 6 7 8 9 10 11
// Данные: * * * * * * *
//
// Результат: 7
// ---------------------------------------------------------------------------
// Итерация: 4 3 2 1
// Позиция: 0 1 2 3 4 5 6 7 8 9 10 11
// Данные:
//
// Результат: 0
// ---------------------------------------------------------------------------
// Итерация: 1 2 3
// Позиция: 0 1 2 3 4 5 6 7 8 9 10 11
// Данные: * * * * * * * * * * * *
//
// Результат: 12
// ---------------------------------------------------------------------------
Программа под linux для тестирования алгоритма, файл div2-search-test.c:
// Дата: 01 сентября 2012
// Автор: Дмитрий Бравиков (bravikov@gmail.com)
// Сборка: gcc -Wall div2-search-test.c div2-search.c -o div2-search-test
// Вызов: ./div2-search-test <size> [free_position]
// Описание: size - количество позиций, free_position - свободная позиция.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "div2-search.h"
unsigned size;
unsigned free_position;
int main(int argc, char *argv[])
{
bool free_position_specify = false;
if (argc > 1)
{
int s = atoi( argv[1] );
if (s < 0)
{
printf("error arguments: size should not be less than zero\n");
return 0;
}
size = s;
}
if (argc > 2)
{
int fp = atoi( argv[2] );
if (fp < 0)
{
printf("error arguments: free position should not be less than zero\n");
return 0;
}
free_position = fp;
if (free_position >= size)
{
printf("error arguments: free position must be less than size\n");
return 0;
}
free_position_specify = true;
}
printf("size = %i, ", size);
if (free_position_specify)
{
printf("free position = %i; test...\n", free_position);
int result = div2_search_free_position(size);
if (result == free_position)
printf(" ok, ");
else
printf(" fall, ");
printf("free position = %i, ", result);
printf("iterations = %i\n", div2_search_iteration_count);
return 0;
}
printf("free position = 0...%i; test...\n", size-1);
int fall_count = 0;
for(free_position = 0; free_position < size; free_position++)
{
int result = div2_search_free_position(size);
if (result == free_position)
printf(" ok, ");
else
{
fall_count++;
printf(" fall, ");
}
printf("free position = %i, ", result);
printf("iterations = %i\n", div2_search_iteration_count);
}
printf("fall = %i\n", fall_count);
return 0;
}
bool div2_search_is_data(const unsigned position)
{
if (position < free_position)
return true;
return false;
}
Понравилось это:
Нравится Загрузка...
