tl; dr: решение проблемы кодирования, которая берет слова в словарь и проверяет, правильно ли они написаны, в кратчайшие сроки
Неделя 5 была посвящена структурам данных, разыменованию и общему низкоуровневому доступу к памяти компьютера. Идея хеш-таблиц и связанных списков стала для меня уникальным просветительским моментом, учитывая количество реальных примеров, в которых используется эта концепция. Нельзя сказать, что концепции, которые я изучил до сих пор, были абстрактными, но я думаю, что со стратегической точки зрения это было хорошей нотой, чтобы закончить C.
Итак, на первый взгляд правописание кажется довольно забавным. Суть этой проблемы состоит в том, чтобы реализовать максимально быструю проверку орфографии. Самое быстрое здесь значение в секундах, как в реальном применении алгоритмов O (n).
Как и в случае с выходом, я сначала был напуган, но код, разбитый на 5 разных блоков, и пошаговое руководство очень помогли. Ключевые идеи здесь включают вспомогательную функцию load, которая сохраняет и читает файл словаря; хэш, который использует знания связанного списка и требует создания хеш-таблицы и индекса для эффективного хранения слов; проверяет какие перекрестные ссылки и видит, есть ли данное слово в словаре; размер возвращает количество слов в словаре; и выгрузить освобождает словарь из памяти.
часть 0: определения
// Implements a dictionary's functionality
#include <stdbool.h>
#include "dictionary.h"
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
//represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// no. of buckets in hash table
const unsigned int N = 26;
// initialise positive hash value using unsigned int
unsigned int hash_value;
// initialise (positive) hash table word count
unsigned int word_count;
// hash table
node *table[N];
Вставляя сюда эту «часть 0» ретроспективно, как я понял после завершения оставшейся части этого пошагового руководства, что я ничего не упомянул об инициализации функций! Это просто вопрос использования unsigned int (для положительных целых чисел) для инициализации различных значений, которые нам нужны, и предварительной установки N = 26, чтобы каждый алфавит получил ведро. Подробнее об этом читайте в части 2: хеш!
часть 1: загрузка
Вызов функции загрузки в текстовом файле словаря сохраняет слова в структуре данных словаря в хэш-таблицу, которая в основном сопоставляет ключи со значениями, используя хеш-функцию для вычисления индекса (т.е. хэш-кода) в массив сегментов (из которых мы можем сорвать то слово, которое хотим). Затем у каждого сегмента есть связанный список, в котором каждый узел имеет значение и указатель на следующий узел, причем последний узел указывает на значение NULL.
malloc принимает аргумент (количество байтов, которые вы хотите выделить) и возвращает этот фрагмент памяти в виде первого адреса, хранящегося в указателе. Это позволяет выделять динамическую память. Здесь malloc используется для каждого нового слова в файле.
Теперь о фактической загрузке.
- Возьмите в качестве аргумента char * или строку, которая является файлом словаря, который нужно открыть и прочитать из
- Используйте fopen, чтобы открыть файл
- Вернуть истину, если выполнено успешно
- Если возвращаемое значение NULL, вернуть false (ошибка выделения памяти)
- Используйте fscanf для чтения строк в файле до EOF (конца файла).
- Используйте malloc для создания и выделения памяти для каждого нового узла.
- Если он возвращает NULL, вернуть false
- Скопируйте слово в узел с помощью strcpy
- Используйте хеш, чтобы взять слова и вернуть хеш-значение / индекс.
- Вставить узел в хеш-таблицу, установив указатель на последовательные узлы
- Подсчитайте количество вводимых слов
// Loads dict into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Open dict
FILE *file = fopen(dictionary, "r");
// If file is not opened, return false
if (file == NULL)
{
return false;
}
// storage space for word
char word[LENGTH + 1];
// Scan dict for strings that are not the end of the file
while (fscanf(file, "%s", word) != EOF)
{
// Allocate memory for new node
node *n = malloc(sizeof(node));
// If malloc returns NULL, return false
if (n == NULL)
{
return false;
}
// Pointer to next node and word itself
strcpy(n->word, word);
// Hash the word to get hash value
hash_value = hash(word);
// Set new pointer
n->next = table[hash_value];
// Set head to new pointer
table[hash_value] = n;
// Increment word count
word_count++;
}
// Close file
fclose(file);
// If dict is loaded, return true
return true;
}
часть 2: хеш
Хеш-функция принимает слово и возвращает хеш-значение или числовое значение слова, чтобы проверить его правильность.
- принимать входные данные, которые представляют собой алфавитные символы, независимо от заглавных букв и, возможно, с апострофами
- вывод должен быть числовым индексом от 0 до N-1 включительно
- детерминированный
Чем больше N, тем эффективнее будет работать программа. Если функция заканчивается значением больше N, можно использовать % N для получения значения в подходящем диапазоне.
Я сыграл просто, выбрав хэш-функцию «первая буква» с N = 26 корзинами. Итак, я порылся на Reddit, чтобы найти хэш-функции, и нашел следующее:
Пришлось немного адаптировать его для собственного использования, но до этого мне действительно нужно было понять, что вообще делает хеш-функция. Оказывается, что хеш «5» (оператор сдвига влево) означает, что хеш сдвигается влево (в двоичном формате) на 5 бит (как указано правым операндом). Не знаю, как Дэн Бернштейн пришел к этому, но ему спасибо, и я просто воспользуюсь этой функцией и посмотрю, что из этого получится.
Настроенная версия этого выглядела так. И toupper, и tolower можно использовать для стандартизации заглавных букв, поскольку это влияет на значение хеш-функции.
// Hashes word to a number
unsigned int hash(const char *word)
{
unsigned long hash = 5381;
int c;
while ((c = toupper(*word++)))
{
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash % N;
}
часть 3: размер
Чтобы вернуть количество слов, программа должна отслеживать количество добавленных слов в реальном времени. word_count уже был определен в load, поэтому оставалось только вернуть его.
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// Check if there are any words
if (word_count > 0)
{
// Return count
return word_count;
}
// Else
return 0;
}
часть 4: проверьте
Проверьте, есть ли слово в словаре, независимо от использования заглавных букв. Вывод имеет форму логического значения.
- Хеш-слово для получения хеш-значения
- Доступ к связанному списку по этому хэш-значению по этому конкретному индексу в хеш-таблице
- Просматривайте связанный список, просматривая по одному узлу за конкретным словом.
- Чтобы пройти, установите курсор или указатель на первый узел в связанном списке
- Используйте strcasecmp, который похож на strcmp, но нечувствителен к регистру, чтобы проверить, есть ли слово в словаре.
- Если это не то слово, введите курсор = курсор - ›далее, чтобы перейти к следующему узлу.
- Делайте это до тех пор, пока курсор не станет равным NULL (eof), а если слово не найдено, верните false.
// Returns true if word is in dictionary else false
bool check(const char *word)
{
//hash the word to get hash value
hash_value = hash(word);
//access the linked list
node *cursor = table[hash_value];
//go through the linked list
while (cursor != NULL)
{
//check if the word matches
if (strcasecmp(word, cursor->word) == 0)
{
return true;
}
//move cursor to next node
cursor = cursor->next;
}
return false;
}
часть 5: разгрузка
Как подчеркивается в лекции, хорошей практикой является освобождение всей памяти, которая могла быть выделена в процессе выполнения программы. Хотя выгрузка путем создания временного курсора в качестве «заполнителя» казалась довольно сложной, в отличие от освобождения самого курсора, аргументация, лежащая в основе этого, довольно интуитивна. В пошаговом руководстве повторяются концепции, изложенные в лекции - ни в коем случае нельзя просто обрезать связанный список, поскольку это означало бы потерю всей соответствующей связанной информации.
- Пройдите по каждому ведру и установите курсор в его местоположение.
- Создайте временную переменную, указывающую на первый узел
- Переместите фактический курсор к следующему узлу в списке
- Освободите временную переменную
- Повторяйте, пока курсор не достигнет последнего сегмента и не станет NULL
- Вернуть истину
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Iterate through buckets
for (int i = 0; i < N; i++)
{
// Set cursor to this each bucket location
node *cursor = table[i];
// If cursor is not NULL, free
while (cursor)
{
// Create temp
node *tmp = cursor;
// Move cursor to next node
cursor = cursor->next;
// Free up temp
free(tmp);
}
// If cursor is NULL
if (i == N - 1 && cursor == NULL)
{
return true;
}
}
return false;
}
Когда код был готов, настало время для реального тестирования времени. Я запустил его на koran.txt и должен признать, что сводная таблица всплывала довольно долго.
Сплошная разница в 18 секунд! Я увеличил N с 26 до 1000000 (почему бы и нет) и снизил его до 0,18 га.
