Раздел «Образование».FIVTLecturesTerm1Lecture8:
<<Лекции ФИВТ, 1-й семестр

Лекция 8. Двоичный поиск. Структура данных "Множество"

Основной цикл двоичного поиска

  while ( r - l > 1 ) {
    int c = (l + r) / 2;
    if ( a < f(c) ) {
      r = c;
    } else {
      l = c;
    }
  }

Задача 1. Напишите код, который находит lower_bound - самое левое значение x: a == f(x).

Структура данных "Множество"

Плохой код N1

Напишем для начала код, который

  1. Память выделяет статически
  2. Позволяет создавать в памяти лишь одну структуру "Множество" (используются глобальные переменные)
  3. Не содержит проверок на достижение предельного количества (n == 10000)
  4. После обавления элемента просто вызывает функцию сортировки qsort, которая есть в stdlib (хотя можно было бы поместить новый элемент в конец а затем с помощью swap'ов переместить его в нужное место, чтобы массив был отсортированн)

%CODE{cpp}%
#include <stdio.h>
#include <malloc.h>

int set[10000];
int n = 0;

// add element to set
int insert(int a);

// check if a exists in set
int include(int a);

// clear set
int clear();

int cmp_int(const void *a, const void *b) {
  const int *aa = a;
  const int *bb = b;
  return *aa - *bb; 
}

int clear() {
  n = 0;
  return 1;
}

int insert(int a) {
  if (include(a)) return 1;
  set[n++] = a;
  qsort(set, n, sizeof(set[0]), cmp_int);
  return 1;
}

int include(t *s, int a) {
  int l = 0;
  int r = n;
  if (n == 0) return 0;
  while ( r - l > 1 ) {
    int c = (l + r) / 2;
    if ( a < set[c] ) {
      r = c;
    } else {
      l = c;
    }
  }
  return set[l] == a;  
}

int assert(int cnd, char *msg) {
  if (!cnd) {
    printf("FAIL: %s\n", msg);    
  }
}

int main(int argc, char *argv[]) {
  int i;
  int b[10000];
  int n = 1000;

  if (argc > 1) {
    n = atoi(argv[1]);
  } 

  if (n <= 0) {
    n = 1000;
  }

  for ( i = 0; i < n; i++) {
    b[i] = rand();
    insert(b[i]);
    assert( include(b[i]), "1" );
  }

  for ( i = 0; i < n; i++) {
    assert( include(b[i]), "2" );
  }

  clear(s);

  for ( i = 0; i < n; i++) {
    assert( !include(b[i]), "3" );
  }

  return 0;
}

Задача 2. Улучшите код функции insert - не вызывайте функцию qsort, а используйте последовательность операций swap, чтобы перестить новый элемент из конца массива в надлежащее место.

Улучшенный код

#include <stdio.h>
#include <malloc.h>

struct set {
  int *set;
  int n;
  int allocated_n;
};

typedef struct set  set_t;

set_t* set_new();

// add element to set
int set_insert(set_t *s, int a);

// check if a exists in set
int set_include(set_t *s, int a);

// clear set
int set_clear(set_t *s);

int cmp_int(const void *a, const void *b) {
  const int *aa = a;
  const int *bb = b;
  return *aa - *bb; 
}

set_t* set_new() {
  set_t *s = (set_t*)malloc(sizeof(set_t));
  s->allocated_n = 1000;
  s->set = (int *)malloc(s->allocated_n * sizeof(int));
  s->n = 0; 
  return s;
}

int set_clear(set_t *s) {
  s->n = 0;
  s->set = (int *)realloc(s->set, (s->allocated_n = 1000) * sizeof(int));
  return 1;
}

int set_delete(set_t *s) {
  free(s->set);
  free(s);
  return 1;
}

int set_insert(set_t *s, int a) {
  if (set_include(s, a)) return 1;
  if ( s->n >= s->allocated_n ) {
    s->set = (int *)realloc(s->set, (s->allocated_n *= 2) * sizeof(int));
  }
  s->set[s->n++] = a;
  qsort(s->set, s->n, sizeof(s->set[0]), cmp_int);
  return 1;
}

int set_include(set_t *s, int a) {
  int l = 0;
  int r = s->n;
  if (s->n == 0) return 0; // строчка, которая изначально была пропущена, но тесты выявили этот bug
  while ( r - l > 1 ) {
    int c = (l + r) / 2;
    if ( a < s->set[c] ) {
      r = c;
    } else {
      l = c;
    }
  }
  return s->set[l] == a;  
}

int assert(int cnd, char *msg) {
  if (!cnd) {
    printf("FAIL: %s\n", msg);    
  }
}

int main(int argc, char *argv[]) {
  int i;
  int *b;
  int n = 1000;

  set_t *s = set_new();

  if (argc > 1) {
    n = atoi(argv[1]);
  } 

  if (n <= 0) {
    n = 1000;
  }

  b = malloc(n * sizeof(int));

  for ( i = 0; i < n; i++) {
    b[i] = rand();
    set_insert(s, b[i]);
    assert( set_include(s, b[i]), "1" );
  }

  for ( i = 0; i < n; i++) {
    assert( set_include(s, b[i]), "2" );
  }

  set_clear(s);

  for ( i = 0; i < n; i++) {
    assert( !set_include(s, b[i]), "3" );
  }

  return 0;
}

Задача 3. Напишите функцию set_remove для удаления элемента из множества.

Задача 4. Оцените время выполениявсех операций (set_new, set_delete, set_insert, set_include, set_remove) в худшем случае.

Test Driven Development (TDD)

На примере разработки этого кода мы увидели, как важно писать тесты. Они позволили найти нам ряд ошбибок, в частности, мы нашли баг с проверкой на принадлежность пустому множеству, которая выдавала иногда неверно true. Чтобы исправить баг, мы добавили строку:

  if (s->n == 0) return 0; // строчка, которая изначально была пропущена, но тесты выявили этот bug

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

Это три крайне важных момента. TDD широко используется на практике.

Важные замечания