Словарь на упорядоченном массиве

Теги: Словарь, хранение пары, ассоциативный массив



Словарь на массиве

Пусть перед нами стала задача хранить пары <ключ, значение>. Такая задача встречается очень часто. Например, нужно хранить информацию о продукте по его id, медиа-данные по их метаданным, изображение по его имени, информацию о человеке по его имени и фамилии и т.д.

Такой контейнер должен, по крайней мере, реализовывать операции

  • PUT(ключ, значение) – для вставки новой пары в контейнер. При этом поведение в случае вставки значения, которое уже есть в коллекции, не определено. Можно подменять старое значение, либо выбрасывать ошибку, либо ничего не делать.
  • GET(ключ) – для получения значение по ключу. Здесь не определено, что будет возвращаться в случае, если такого значения в коллекции нет. Например, если мы храним указатель, то можно возвращать NULL. Но вполне возможно, что NULL – это приемлемое значение для указателя. Также NULL, если ключ целочисленный, может трактоваться, как число 0.
  • REMOVE(ключ) – для удаления пары из контейнера. Во время удаления объект изымается из контейнера, но дальнейшее поведение опять не определено. Удалять пару может как функция REMOVE, так и внешняя функция, получившая результат.

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

Самое простое решение использовать неупорядоченный массив структур. Очевидно, что в таком случае вставка будет иметь сложность порядка 1, поиск порядка n, так как придётся перебрать все элементы, удаление также потребует n шагов, потому что перед удалением нужно найти пару в массиве (само удаление будет иметь сложность 1).

Коллекция «словарь» использует для хранения упорядоченный по ключу массив пар. Соответственно, поиск всегда будет иметь сложность log(n), так как в упорядоченном массиве можно использовать двоичный поиск. Удаление и вставка будет иметь сложность порядка n, так как придётся сдвигать элементы массива (делать это, конечно, будем не в цикле, а функцией memcpy).

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

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

Так как массив структур упорядочен, то необходимо, чтобы для ключей были реализованы, как минимум, две функции – сравнения на равенство и сравнения на больше (или меньше).

Реализация

Как обычно, массив структур будет иметь некоторый начальный размер, чтобы не утруждаться частым изменением размера. Сделаем значение по умолчанию равным 100.

Для начала определим новые типы данных. Первый для ключа, он будет называться K, второй для значения V (Key и Value). В нашем примере ключом и значением будет строка. 

typedef char * K;
typedef char * V;

Далее, необходимо определить функции для работы с нашими ключами. Первым делом – сравнение на равенство и меньше 

#define CMP_LT(a, b) (strcmp((a), (b)) < 0)
#define CMP_EQ(a, b) (strcmp((a), (b)) == 0)

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

Функция freeEntry будет использоваться для освобождения памяти из-под пары. Так как ключом и значением могу являться, в принципе, любые объекты, для которых определены операции сравнения, то и их удаление может происходить разными способами. 

void freeEntry(Entry **e) {
	free((*e)->key); 
	free((*e)->value); 
	free(*e); 
	/**e = NULL;*/
}
#define FREE_ENTRY(e) freeEntry(e)

Мы уже говорили о том, что словарь будет иметь какой-то начальный размер. В том случае, если число элементов превысит размер, то необходимо будет изменять размер массива. Новый размер предлагается вычислять как старый, умноженный на некоторое число multiplier. Поэтому введём две константы – начальный размер и множитель. 

static const size_t INIT_SIZE = 100;
static const float MULTIPLIER = 2.0f;

Сама структура словарь 

typedef struct Dictionary {
	size_t limit;
	size_t size;
	float multiplier;
	Entry **data;
} Dictionary;

Здесь data – массив указателей на пары. Изначально у нас будет только массив указателей на пары. При вставке новой пары элемент массива будет хранить адрес новой пары.

size – количество элементов в словаре. multiplier – множитель, во сколько раз изменится размер массива при превышении размера.

limit – размер массива.

Функция, создающая новый пустой словарь 

Dictionary* createDictionary(size_t initSize) {
	Dictionary *dict = (Dictionary*)malloc(sizeof(Dictionary));
	dict->limit = initSize > INIT_SIZE ? initSize : INIT_SIZE;
	dict->size = 0;
	dict->data = (Entry**)malloc(sizeof(Entry*) * dict->limit);
	dict->multiplier = MULTIPLIER;
	return dict;
}

Самая важная функция – поиск элемента. В двоичном поиске мы находим элемент в упорядоченном массиве. Если его нет, то возвращаем, например, указатель на NULL, если нашёлся, то указатель на элемент. Наша функция должна определять, есть ли элемент в массиве. Если он есть, то возвращать его индекс, а также указывать, что элемент был найден. Если элемента нет, то указать, что элемент не найден, и вернуть индекс элемента, после которого нужно производить вставку (или до какого элемента производить вставку). Поиск осложняется ещё и тем, что индекс имеет тип size_t, то есть не может стать отрицательным. При вычитании из size_t единицы получим большое целое число.

Наша функция будет возвращать 0, если элемент не найден и 1, если найден. Также она будет присваивать переданному через указатель параметру индекс найденного элемента, либо индекс, после которого нужно производить вставку. В идеале.

__inline static int find(K key, Entry** data, size_t size, size_t *index) {
	size_t i = 0;
	size_t j = size-1;
	size_t med;
	int result = 0;	
	while (i <= j) {
		//чтобы избежать переполнения складываем именно так
		med = i + (j - i) / 2;
		if (CMP_LT(key, data[med]->key)) {
			//Проверка, чтобы число не стало меньше нуля
			if (med != 0) {
				j = med - 1;
			} else {
				break;
			}
		} else if (CMP_EQ(key, data[med]->key)) {
			result = 1;
			break;
		} else {
			i = med + 1;
		}
	}
	*index = med;
	return result;
}
  • 1. Представим, что мы ищем элемент, который меньше самого маленького элемента массива. Тогда функция возвратит 0, а значение index будет равно 0. По идее, оно должно быть отрицательным, так как мы хотим позицию, после которой нужно вставлять элементы. Таким образом, эту проблему мы перекладываем на вызывающую функцию, которая должна с ней как-то рабираться.
  • 2. Мы ищем элемент в массиве длиной 0. Тогда j-1 приведёт к тому, что j станет очень большим, попытается провести поиск в пустом массиве и наткнётся на access violation. Опять же, перекладываем проблему на вызывающую функцию.
  • 3. Мы ищем последний элемент. Если он есть, то будет возвращена единица и индекс, указывающий на него. Но тот же самый индекс будет возвращён и в случае, ели такого элемента нет. Снова этот случай пусть рассматривает вызывающая функция.

Наша функция вставки пары. put_raw возвращает 0, если элемент уже содержится, и 1, если произошла вставка. 

int raw_put(Dictionary *dict, Entry *e) {
	size_t i = 0;
	size_t j = dict->size;
	size_t index;
	int contains;

	if (dict->size == 0) {
		dict->data[0] = e;
		dict->size++;
		return;
	}

	contains = find(e->key, dict->data, dict->size, &index);
	//Если такой элемент уже содержится, то выходим
	if (contains) {
		return 0;
	}
	//Проверяем размер массива
	if (dict->size >= dict->limit) {
		dict->limit = (size_t) (dict->multiplier * dict->limit);
		dict->data = (Entry**)realloc(dict->data, dict->limit * sizeof(Entry*));
		if (dict == NULL) {
			exit(-5);
		}
	}

	if (index >= (dict->size - 1)) {
		index = dict->size;
		if (CMP_LT(e->key, dict->data[dict->size - 1]->key)) {
			dict->data[dict->size] = dict->data[dict->size - 1];
			dict->data[dict->size - 1] = e;
		} else {
			dict->data[index] = e;
		}
	} else {
		memcpy(&(dict->data[index + 1]), &(dict->data[index]), sizeof(Entry*)*(dict->size - index));
		if (index == 0 && CMP_LT(e->key, dict->data[0]->key)) {
			dict->data[index] = e;
		} else {
			dict->data[index + 1] = e;
		}
	}

	dict->size++;
	return 1;
}

Рассмотри подробнее. Первый блок. 

if (dict->size == 0) {
	dict->data[0] = e;
	dict->size++;
	return;
}

Ситуация, когда элемента нет. Обрабатываем её отдельно. Далее ищем элемент. 

contains = find(e->key, dict->data, dict->size, &index);
//Если такой элемент уже содержится, то выходим
if (contains) {
	return 0;
}

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

//Проверяем размер массива
if (dict->size >= dict->limit) {
	dict->limit = (size_t) (dict->multiplier * dict->limit);
	dict->data = (Entry**)realloc(dict->data, dict->limit * sizeof(Entry*));
	if (dict == NULL) {
		exit(-5);
	}
}

А вот теперь рассматриваем оставшиеся исключительные ситуации. Получили индекс последнего элемента массива. 

if (index >= (dict->size - 1)) {
	index = dict->size;
	if (CMP_LT(e->key, dict->data[dict->size - 1]->key)) {
		dict->data[dict->size] = dict->data[dict->size - 1];
		dict->data[dict->size - 1] = e;
	} else {
		dict->data[index] = e;
	}

Или индекс, равный 0. 

} else {
	memcpy(&(dict->data[index + 1]), &(dict->data[index]), sizeof(Entry*)*(dict->size - index));
	if (index == 0 && CMP_LT(e->key, dict->data[0]->key)) {
		dict->data[index] = e;
	} else {
		dict->data[index + 1] = e;
	}
}

Оканчивается всё одинаково 

dict->size++;
return 1;

Теперь нужна обёртка, чтобы можно было вставить ключ и значение. 

int put(Dictionary **dict, K key, V value) {
	Entry *e = (Entry*)malloc(sizeof(Entry));
	int result;
	e->key = key;
	e->value = value;
	result = raw_put(dict, e);
	if (result == 0) {
		FREE_ENTRY(&e);
	}
	return result;
}

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

Удаление 

Entry* xremove(Dictionary *dict, K key) {
	int contains;
	size_t index;
	Entry *retVal = NULL;

	if (dict->size == 0) {
		return NULL;
	}

	contains = find(key, dict->data, dict->size, &index);
	if (contains) {
		printf("[[%d]]", index);
		retVal = dict->data[index];
		//Если размер блока равен нулю, то поведение не определено,
		//поэтому нужно проверять, чтобы мы не скопировали ноль байт
		if (index != dict->size) {
			memcpy(&(dict->data[index]), &(dict->data[index + 1]), (dict->size - index)*sizeof(Entry*));
		}
		dict->size--;
	}
	return retVal;
}

Здесь также есть особая ситуация, когда размер словаря равен нулю. Обратите внимание на memcpy: необходимо проверять, чтобы мы не скопировали 0 байт. Такая ситуация произойдёт в том случае, если index равен размеру, то есть когда удаляем последний элемент. В этом случае index+1 выйдет за пределы массива, и даже не смотря на то, что размер копируемой области равен 0, вылетит ошибка.

Функция получения значения пары по ключу 

V get(Dictionary *dict, K key, int *wasFound) {
	size_t index;
	V retVal = NULL;

	if (dict->size == 0) {
		*wasFound = 0;
	} else {
		*wasFound = find(key, dict->data, dict->size, &index);
		if (*wasFound) {
			retVal = dict->data[index]->value;
		}
	}

	return retVal;
}

Здесь мы решаем проблему возвращаемого значения следующим образом. Если элемент найден, то wasFound будет равняться 0, даже если значения элемента равно NULL.

Последняя из основных функция – удаление словаря. 

void destroyDictionary(Dictionary** dict) {
	size_t i;
	for (i = 0; i < (*dict)->size; i++) {
		FREE_ENTRY(&((*dict)->data[i]));
	}
	free((*dict)->data);
	free(*dict);
	*dict = NULL;
}

Поиск максимального и минимального элементов 

Entry* getMax(Dictionary *dict) {
	if (dict->size > 0) {
		return dict->data[dict->size - 1];
	} else {
		return NULL;
	}
}

Entry* getMin(Dictionary *dict) {
	if (dict->size > 0) {
		return dict->data[0];
	}
	else {
		return NULL;
	}
}

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

Q&A

Всё ещё не понятно? – пиши вопросы на ящик email
Поворот двоичного дерева поиска
Хэш-карта с закрытой адресацией