Практическая работа. Постановка задачи и рекомендации

Проверка орфографии

Итак, перед нами стоит следующая задача: реализовать load, check, size и unload настолько эффективно, насколько это возможно, чтобы минимизировать TIME IN load, TIME IN check, TIME IN size, и TIME IN unload.

Возможно, не совсем понятно, что значит минимизовать. Особенно с учётом того, что эти показатели будут меняться в зависимости от того, какой словарь dictionary и текст text вы загружаете в speller. Это и есть самая соль задачи, самое сложное, но при этом — очень увлекательное затруднение. К его решению можно подойти творчески.

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

• Вы не можете менять speller.c.
• Вы можете менять dictionary.c (по сути, вы должны его менять, чтобы завершить реализацию load, check, size и unload, но при этом нельзя изменять объявления load, check, size и unload).
• Вы можете изменять dictionary.h, но нельзя изменять объявления load, check, size и unload.
• Вы можете менять Makefile.
• Вы можете добавить функции в dictionary.c или в ваши собственные файлы. Только проследите, чтобы при этом ваш код успешно компилировался с помощью make.
• Ваша реализация check должна быть нечувствительна к регистру. Другими словами, если foo есть в словаре, check должна возвращать значение true для любого слова, которые отличаются от foo только регистром символов. Все слова foo, foO, fOo, fOO, fOO, Foo, FoO, FOo и FOO нужно считать правильными.
• Помимо регистра, ваша реализация check должна возвращать значение true для слов, которые действительно есть в dictionary. Осторожнее с часто употребляемыми словами (например, с the), если мы передали dictionary без них. Более того, разрешены только те конкретные слова, которые явно заданы в словаре dictionary, а их формы — нет. Иначе говоря, даже если foo есть в dictionary, команда check должна вернуть значение false для foo’s в случае если foo’s нет в dictionary.
• Считайте, что check проходит строки только по символам алфавита и/или апострофам.
• Считайте, что любой словарь в вашей программе будет структурирован точно так, как наши: лексикографически выстроен сверху вниз по одному слову в строке, и все строки заканчиваются знаком \n. Также примите, что dictionary должен содержать по крайней мере одно слово и все слова не должны быть длиннее LENGTH (эта константа определена в dictionary.h). Ни одно слово не должно повторяться и все они должны содержать строчные символы алфавита и, возможно, апострофы.
• Ваша программа проверки правописания должна принимать на вход только text и, дополнительно, может принимать словарь dictionary. Невзирая на то, что вы, скорее всего захотите предварительно “доработать” наш словарь по умолчанию с целью определить для него лучшую хеш-функцию, вы не сможете сохранить на диск результат любой подобной доработки с тем, чтобы повторно загрузить его в память для более быстрых дальнейших вызовов.
• Вы можете использовать хеш-функции из книг или интернета, при условии, что вы даете ссылку на оригинал любой хеш-функции, которую вы интегрируете в ваш код.

Начинаем

Вот что вам нужно сделать:

Еще немного подсказок:

Не забывайте, valgrind — ваш лучший приятель! Он отслеживает потерю доступа к памяти, пока ваша программа работает. Убедитесь, что аргументы в программной строке передаются, если вы хотите, чтобы функция valgrind анализировала speller, пока вы используете определенный словарь и/или текст. Лучше всего работать с небольшим текстом, в противном случае valgrind потребуется значительное количество времени.

valgrind — leak-check=full ./speller texts/ralph.txt

Если вы запускаете valgrind без указания text для speller, ваша реализация load и unload не будет вызываться (и анализироваться).

Если вы не уверены, как следует интерпретировать результат valgrind, запустите help50:

help50 valgrind — leak-check=full ./speller texts/ralph.txt

Проверка

Как понять, что программа выбрала верные слова с опечатками? Во-первых, вы можете посмотреть ответы в директории keys. Она находится внутри директории speller. Например, в keys/austinpowers.txt должны быть собраны все слова, которые ваша программа считает написанными неправильно.

Или вы можете запустить программу над текстом в одном окне.

./speller ~cs50/pset5/texts/austinpowers.txt

А потом запустите версию, созданную сотрудниками курса, с тем же самым текстом в другом окне, как показано ниже:

~cs50/pset5/speller ~cs50/pset5/texts/austinpowers.txt 

и провести визуальное сравнение визуально, строка за строкой. Правда, такая работа очень быстро надоедает. Вместо этого лучше перенаправить результат работы программы в отдельный файл (вы уже так делали с generate в третьем задачнике):

./speller ~cs50/pset5/texts/austinpowers.txt > student.txt
~cs50/pset5/speller ~cs50/pset5/texts/austinpowers.txt > staff.txt

Вы можете сравнить оба файла, открыв их в одном окне с помощью программы diff:

diff -y student.txt staff.txt

Или ещё один вариант: для экономии времени, вы можете сравнить результат работы вашей программы (предположим, что вы перенаправляете его в, например, student.txt) с одним из файлов ответов:

diff -y student.txt ~cs50/pset5/keys/austinpowers.txt

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

Если столбцы будут отличаться, вы увидите знаки > или |, там, где они отличаются. Например,

MISSPELLED WORDS                                                MISSPELLED WORDS

FOTTAGE                                                         FOTTAGE
INT                                                             INT
                                                              > EVIL'S
s                                                               s
                                                              > EVIL'S
Farbissina                                                      Farbissina

Это означает что программа (её вывод — слева) не считает, что EVIL’s не верен, а вот наша программа считает именно так, что представляется отсутствием EVIL’s в левой колонке и присутствием его в правой.

check50

Чтобы проверить свой код в автоматическом режиме (правда, не полностью), вы можете выполнить следующее:

check50 2015.fall.pset5.speller dictionary.c dictionary.h Makefile

Обратите внимание, check50 не отслеживает утечки памяти, поэтому обязательно используйте также valgrind.

Как понять, достаточно ли быстрая ваша версия?

Как всегда, вы можете запустить версию, созданную сотрудниками курса, и сравнить результат её работы с вашим:

~cs50/pset5/speller ~cs50/pset5/texts/austinpowers.txt