Реализуйте программу, которая будет проверять правильность написания слов файла, как показано ниже.
$ ./speller texts/austinpowers.txt
MISSPELLED WORDS
(Слова с ошибками)
[...]
Bigglesworth
[...]
Virtucon
[...]
friggin'
[...]
trippy
[...]
WORDS MISSPELLED:
(количество неправильно написанных слов)
WORDS IN DICTIONARY:
(слов в справочнике)
WORDS IN TEXT:
(слов в тексте)
TIME IN load:
(время для загурзку)
TIME IN check:
(время для проверки)
TIME IN size:
(время для размера)
TIME IN unload:
(время для выгрузки )
TIME IN TOTAL:
(общее время)
$ wget https://github.com/cs50/problems/archive/speller.zip
$ unzip speller.zip
$ rm speller.zip
$ mv problems-speller speller
$ cd speller
$ ls
dictionaries/ dictionary.c dictionary.h keys/ Makefile questions.txt speller.c texts/
Теоретически алгоритм с входными данными размера n и временем (эффективностью) выполнения n асимптотически эквивалентны, в плане O, алгоритму с временем выполнения 2n. В действительности же последний будет в два раза медленнее первого.
Далее вам предстоит реализовать программу, которая будет проверять с максимально возможной скоростью правильность введенного слова! Под “максимальной” мы имеем в виду настоящую скорость - ту, которую можно заметить при реальной работе с программой, а не в асимптотическом представлении.
В speller.c (орфографический справочник ) мы создали программу, которая проверяет на орфографию файл, после загрузки справочника с жесткого диска в нашу память (оперативку). К сожалению, мы не разобрались с тем, как реализовать функционал загрузки справочника и функционал проверки орфографии. Обе задачи (и кое-что еще) нужно будет реализовать вам самим! Но сперва маленькая экскурсия.
dictionary.{c,h}Откройте dictionary.h. В данном файле объявлены четыре функции. Ознакомьтесь с тем, что должна делать каждая из них. Теперь откройте dictionary.c. Заметьте, что мы уже имплементировали код данных четырех функций, правда самым минимальным образом, достаточным для того, чтобы код компилировался. Ваша задача сводиться к тому, чтобы по-новому реализовать эти функции наилучшим образом. Для нас главное скорость!
MakefileВспомните, что make автоматизирует компиляцию вашего кода и вам не придется вручную запускать clang вместе с огромным количеством аргументов. Но, по мере того, как будет увеличиваться размер вашей программы, make более не сможет сам определять, как именно ему компилировать код. Вам придется самим говорить make‘у, как нужно компилировать вашу программу, особенно, когда речь пойдет о нескольких файловых источниках (т.е. .c), как например в этой проблеме. Поэтому мы избавимся от Makefile, файла конфигурации, который говорит make‘у, что ему нужно делать. Откроем Makefile и разберем его строки.
Строка, приведенная ниже, определяет переменную под названием CC, которая устанавливает, что make должен использовать clang для компиляции программ.
CC = clang
Ниже идет строка, определяющая переменную CFLAGS, которая, в свою очередь, уточняет, что программа clang должна использовать кое-какие флаги (аргументы), многие из которых вам могут показаться знакомыми.
CFLAGS = -ggdb3 -O0 -Qunused-arguments -std=c11 -Wall -Werror
Следующая строка определяет переменную EXE. Ее значение будет задавать имя нашей программы.
EXE = speller
Другая строка определяет переменную HDRS. Ее значением выступает список, состоящий из разделенных пробелами заголовочных файлов, используемые программой speller.
HDRS = dictionary.h
Далее идет строка, определяющая переменную LIBS, значением которой является список, состоящий из разделенных пробелами библиотек. Каждая из таких библиотек, должна начинаться с -l (вспомните как мы ранее использовали -lcs50). Вполне вероятно, что вам не придется перечислять какие-либо библиотеки для этой проблемы, но мы все же включили эту переменную на всякий случай.
LIBS =
Следующая строка определяет переменную SRCS. Ее значением выступает список, состоящий из разделенных пробелами файлов Си, которые вместе смогут имплементировать программу speller.
SRCS = speller.c dictionary.c
Строка, приведенная ниже, определяет переменную под названием OBJS. Ее значение идентично значению SRCS, кроме того отличия, что каждое расширение файла не .c, а .o.
OBJS = $(SRCS:.c=.o)
Далее идущие строки определяют “цель”, используя эти переменные, которые говорят make‘у, как компилировать программу speller.
$(EXE): $(OBJS) Makefile
$(CC) $(CFLAGS) -o $@ $(OBJS) $(LIBS)
Следующая строка определяет, что все наши .o файлы зависят от dictionary.h и Makefile, поэтому изменение любого из них приведет к повторной компиляции .o файлов при следующем запуске make.
$(OBJS): $(HDRS) Makefile
Наконец, строки, приведенные ниже, определяют другую цель, которая служит для очистки (clean) папки этой “проблемы”.
clean:
rm -f core $(EXE) *.o
Можете как угодно изменять файл Makefile, все на ваше усмотрение. На самом деле, вам итак придется его менять, если вы создадите любые .c или .h файлы. Но будьте осторожны, постарайтесь не нарушить табуляцию, а именно заменив табы (\t), так как make ожидает, что эти табы будут под каждой целью.
Связь всех этих строк дает вам возможность компилировать программу speller, используя только одну команду, хоть она и охватывает немало файлов:
make speller
Но есть еще лучший способ, вы можете просто выполнить следующее:
make
И если вы когда-нибудь захотите удалить программу вместе с любыми другими core (важными) или .o файлами, вы можете сделать это одной командой:
make clean
В общем, если вы захотите скомпилировать код данной проблемы, достаточно будет запустить:
make
speller.cХорошо, теперь откройте speller.c и потратьте кое-какое время, пытаясь понять код и комментарии приведенные внутри данного файла. Вам не нужно менять его содержимое, но, как бы там не было, вам надо понимать этот код. Заметьте, как мы, используя getrusage, будем измерять скорость выполнения работы (бенчмаркинг) вашей имплементации check (проверки), load (загрузки), size (размера) и unload (выгрузки). Обратите еще внимание на то, как мы, слово за словом, передаем на проверку функции check содержимое файла. В итоге предоставляя отчет о каждом слове с орфографической ошибкой, которое было найдено в данном файле и еще с кое-какой статистикой.
Посмотрите, как нужно запускать программу speller
Usage (использование): speller [dictionary] text
где предполагается, что dictionary (справочник) будет выступать в качестве файла, который содержит список слов (все слова строчные, т.е. написаны маленькими буквами). Каждое слово на отдельной строке и text выступает файл который будет проверяться на наличие орфографических ошибок. Квадратные скобки указывают на необязательность предоставления dictionary (справочника). Если этот аргумент не будет указан, тогда speller будет по умолчанию использовать dictionaries/large. Другими словами, команда
./speller text
будет эквивалентна
./speller dictionaries/large text
где text - это файл, который вы хотите проверить на орфографические ошибки. Достаточно сказать, что намного легче использовать первый метод. Конечно, speller не сможет загрузить какие-либо справочники, пока вы не реализуете load (загрузчик) в dictionary.c! А до тех пор, вы будете видеть сообщение Could not load (не удается загрузить файл).
Внутри основного справочника находится 143,091 слов и все они должны быть загружены в память! Откройте этот файл для лучшего представления его структуры и размера. Обратите внимание на то, что каждое слово записано строчными (маленькими) буквами. Сверху вниз файл отсортирован лексикографически, с одним словом на каждую строку (каждая из которых оканчивается на \n). Ни одно слово не может превышать 45 символов и не одно из них повторно не употребляется. Во время разработки может оказаться полезным представить программе speller свой собственный справочник dictionary, который будет содержать намного меньше слов. Так вам не придется уделять много времени на отладку, избегая огромную структуру памяти. В dictionaries/small есть такой справочник. Чтобы им воспользоваться выполните
./speller dictionaries/small text
где text представляет из себя файл, который вы хотите проверить на орфографию. Теперь остановитесь и не продвигайтесь дальше, пока не будете уверены, что вы понимаете как работает сама программа speller!
Вполне вероятно, что вы недостаточно разобрались с файлом speller.c. Вернитесь назад и повторно пройдитесь по нему!
texts/Мы предоставили вам огромное количество текста, чтобы вы могли протестировать реализацию программы speller. Среди данных текстов, можно найти часть сценария фильма Остин Пауэрс: Человек-загадка международного масштаба, звуковой фрагмент Ральф Виггама, три миллиона байтов от Толстого, кое-какие выдержки из работ Макиавелли и Шекспира, весь текст библии короля Якова и т.д. Дабы вы имели лучшее представление о том, с чем вам придется работать, откройте и просмотрите каждый из этих файлов, которые находятся в папке под названием texts, которую в свою очередь можно найти в папке pset5.
Теперь, когда вы тщательно разобрали код speller.c, вы должны иметь представление каким получится результат на выходе (выходные данные программы), после запуска программы speller следующим образом
./speller texts/austinpowers.txt
В итоге, мы увидим результат приведенный ниже. Сперва попробуйте запустить “Гарвардское Решение” (используя основной справочник) с тем, что приведено ниже.
~cs50/pset5/speller texts/austinpowers.txt
Ниже идут выходные данные, которые появятся перед вами. Чисто для прикола, мы подобрали кое-какие наши любимые “неправильно написанные слова”. И, чтобы не испортить вам настроения, мы убрали нашу собственную статистику.
MISSPELLED WORDS
(слова с ошибками)
[...]
Bigglesworth
[...]
Virtucon
[...]
friggin'
[...]
trippy
[...]
WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:
TIME IN load (время для загрузки) представляет число секунд, которые затрачивает speller, выполняя вашу имплементацию load (загрузки). TIME IN check (время для проверки) представляет число секунд, которые затрачивает speller, выполняя вашу имплементацию check (проверки). TIME IN size (время для размера) представляет число секунд, которые затрачивает speller, выполняя вашу имплементацию size (размер). TIME IN unload (время для выгрузки) представляет число секунд, которые затрачивает speller, выполняя вашу имплементацию unload (выгрузка). TIME IN TOTAL (общее время) представляют сумму всех этих измерений времени.
Имейте в виду, что эти числа могут различаться при каждом запуске speller, в зависимости от загруженности среды разработки CS50 IDE, даже если вы не меняли свой код.
Под “misspelled” (слово с ошибкой) мы подразумеваем, что некоторые слова не находятся в dictionary (справочнике).
Откройте файл questions.txt и ответьте на каждый из следующих вопросов одним или несколькими предложениями.
Что такое pneumonoultramicroscopicsilicovolcanoconiosis?
Откройте документацию функции getrusage и объясните, что она делает?
Опираясь на ту же документацию скажите, сколько полей имеет переменная типа struct rusage?
Как вы думаете, почему мы передаем функции calculate ссылки (вместо значений) before и after, хоть мы и не меняем их содержимое?
Дайте нам точное объяснение того, как именно функция main считывает слова из файла. Другими словами, докажите нам, что вы действительно понимаете, как работает цикл for данной функции.
Почему, по вашему мнению, мы воспользовались функцией fgetc, таким образом поочередно считывая символы каждого слова, вместо того, чтобы применить fscanf вместе с "%s" считывая по одному слову за раз? Скажем по-другому - какие могут появиться проблемы, если мы будем использовать только fscanf?
Как вы думаете, почему мы объявили параметры check и load как const (т.е. константы)?
Перед вами стоит задача реализовать load, check, size и unload найэфективнейшими способами так, чтобы значения TIME IN load, TIME IN check, TIME IN size и TIME IN unload были сведены к минимуму. Конечно, не очевидно, что означает свести к минимуму, поскольку эти показатели, разумеется, будут меняться по мере того, как вы будете предоставлять программе speller различные значения для dictionary и для text. Но в этом и заключается вызов, если не удовольствие решения этой проблемы. Эта проблема - ваш шанс начать полноценную разработку. Хоть мы и хотим, чтобы ваша программа занимала как можно меньше памяти, но вашим главном врагом является время. До того, как вы погрузитесь в этот увлекательный мир программирования, получите кое-какие разъяснения от нас.
Вам нельзя менять 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 должна вернуть истину вне зависимости от того, какого размера буквы будут предоставлены. Ни один из foo, foO, fOo, fOO, fOO, Foo, FoO, FOo и FOO не должны считаться грамматически неверными.
Ваша имплементация check должна возвращать true только для слов, которые действительно будут находиться в словаре. Будьте осмотрительны и не хардкодьте часто используемые слова (например the), дабы предотвратить проблемы при передаче вашей имплементации словаря (dictionary), в котором они будут отсутствовать. Другими словами, даже если foo будет в словаре, функция check должна вернуть false при предоставлении слова foo’s, если конечно foo’s не присутствует в словаре.
Вы можете предположить, что check будет получать только строки с символами алфавита и/или апострофами.
Вы можете предположить, что любой словарь, переданный вашей программе, будет структурирован точно также, как наш, лексикографически отсортированный сверху вниз, по одному слову на строку, каждая из которых заканчивается на \n. Вы также можете предположить, что словарь будет содержать хотя бы одно слово. Количество символов в этих словах не должно превышать значения LENGTH (константа определенная в dictionary.h). Кроме того, ни одно слово не появится больше одного раза (никаких повторов) и каждое слово будет состоять только из алфавитных букв нижнего регистра (маленькие буквы) и возможно апострофов.
Ваша программа проверки правописания должна обязательно принимать text - в качестве входных данных, и, дополнительно, может принимать словарь. Несмотря на то, что вам скорее всего захочется предварительно обработать наш стандартный словарь дабы определить для него идеальную хеш-функцию, вы не можете сохранять результаты (выходные данные) такой обработки на запоминающий носитель (жесткий диск), чтобы потом обратно загружать данные с диска в память для получения преимущества при последующих запусках программы проверки правописания.
У вашей программы не должно быть утечек памяти.
Вы можете искать (хорошие) хеш-функции в интернете, главное указывать в своем коде источник, с которого вы скачали хеш-функцию.
Хорошо, готовы начать?
Реализуйте load.
Реализуйте check.
Реализуйте size.
Реализуйте unload.
Не забудьте реализовать освобождение памяти (free) в функции unload, которую вы выделили в функции load! Не забывайте про своего нового лучшего друга по имени valgrind. Знайте, что valgrind следит за утечками только тогда, когда ваша программа находится в рабочем состоянии (т.е. запущена), поэтому обязательно предоставляйте аргументы командной строки, если вы хотите, чтобы valgrind анализировал программу speller в то время, как вы пользуетесь определенным словарем и/или текстом, как показано ниже. Лучше всего использовать небольшой текст, так как, в противном случае, valgrind‘у понадобится намного больше времени, чтобы начать свою работу.
valgrind --leak-check=full ./speller texts/ralph.txt
Если вы запустите valgrind, не подставляя в качестве аргумента text для проверки программы speller, ваша имплементация функций load и unload не будут вызваны (а значит и анализированы).
Как проверить, правильно ли ваша программа выводит слова с орфографическими ошибками? Ну, вы можете обратиться к “answer keys” (ключам ответов), которые находятся внутри папки keys (ключи), которую в свою очередь можно найти внутри папки программы speller. К примеру, внутри текстового документа keys/austinpowers.txt находятся все слова, которые ваша программа должна распознавать как неправильные слова.
Поэтому вы могли бы применить свою программу на каком-нибудь тексте в одном окне, как показано ниже.
./speller texts/austinpowers.txt
И далее, вы могли бы запустить “Гарвардское Решение” на том же самом тексте в другом окне, как показано ниже.
~cs50/pset5/speller texts/austinpowers.txt
И потом, вы могли бы визуально сравнить оба окна. Однако, такой подход не практичен и очень быстро надоест. Поэтому, вы, скорее всего, захотите “перенаправить” выходные данные вашей программы в файл (точно также, как вы возможно поступали с программой generate в 3 Наборе Проблем), как показано ниже.
./speller texts/austinpowers.txt > student.txt
~cs50/pset5/speller texts/austinpowers.txt > staff.txt
Уже потом вы можете сравнить два файла, строка за строкой, в одном и том же окне, с помощью такой программы как diff.
diff -y student.txt staff.txt
Альтернативный способ, для сохранения времени, - вы можете просто сравнить выходные данные вашей программы (предполагая, что вы перенаправили выходные данные, например к student.txt) с одним из файлов с ответами (answer keys), не применяя “Гарвардское Решение”, как показано ниже.
diff -y student.txt keys/austinpowers.txt
Если ваш результат совпадает с нашим, diff выведет две (2) колонки, которые должны будут быть одинаковыми и могут, возможно, отличаться только нижними временами исполнения. Если же колонки различаются, тогда вы увидите > или | в местах их отличия.
check50Чтобы проверить ваш код более автоматизировано, вы можете также выполнить команду.
check50 2016.speller dictionary.c dictionary.h Makefile
Заметьте, что check50 не может обнаружить и не проверяет утечки памяти, поэтому обязательно воспользуйтесь valgrind‘ом.
Как определить на сколько быстр (и правилен) ваш код? Воспользуйтесь нашим решением и сравните показатели нашей программы с показателями вашей реализации орфографического словаря.
~cs50/pset5/speller texts/austinpowers.txt