Поиск свободного места методом половинного деления

Допустим. имеется какая-то область для хранения данных. Например, в флеш-памяти. Она последовательно заполняется блоками данных и с конца остается свободное место. Метод половинного деления позволяет избежать перебора всех данных. Если область вмещает 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;
}
Реклама