Цели

  • Разработать и реализовать программу для проверки орфографии.
  • Оптимизировать время (реальное время) выполнения вашего кода.

Литература

  • Страницы 18 — 20, 27 — 30, 33, 36, и 37 из www.howstuffworks.com/c.htm.
  • Часть 26 из Absolute Beginner’s Guide to C.
  • Часть 17 из Programming in C.Введение в JavaScript, Ajax, JSON.
  • Знакомство с объектами и методами.
  • Работа с «реальными» API и библиотеками.

Начинаем

Зайдите в «Виртуальную лабораторию» или залогиньтесь в cs50.io и выполните команду

update50

в терминальном окне, чтобы убедиться, что ваше рабочее пространство обновлено. Теперь перейдите в вашу рабочую директорию (Dropbox в «Виртуальной лаборатории» или workspace в CS50 IDE).

После этого выполните команду загрузки zip-архива:

wget http://cdn.cs50.net/2015/fall/psets/5/pset5/pset5.zip 

После этого разархивируйте pset5, удалите архив, зайдите в папку pset5 и посмотрите, какие в ней есть файлы:

$ unzip pset5.zip
$ rm –f pset5.zip
$ cd pset5
$ ls

Вы увидите такое содержимое:

dictionaries/  dictionary.c  dictionary.h  keys/  Makefile  questions.txt  speller.c  texts/

Это ваша заготовка! На базе этих файлов вам и предстоит создать «проверщика» орфографии speller!

Speller

$ ./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:

Теоретически на исходных данных размера n, алгоритм с временем выполнения n в терминах нотации O-большое асимптотически эквивалентен алгоритму с временем выполнения 2n. Хотя в реальности второй на самом деле вдвое медленнее, чем первый.
Вам предстоит реализовать максимально быструю проверку правописания. Под «максимально» в этот раз подразумевается фактическое, реальное измеримое время, а не вся эта асимптотика.
В файле speller.c мы реализовали программу, которая проверяет орфографию после загрузки словаря с диска в память. К сожалению, мы не реализовали процесс загрузки и проверки. Они оба (и не только они!) — теперь ваша проблема! Но сначала небольшой экскурс.

dictionary.{c,h}

Откройте файл dictionary.h. В нём объявлены четыре функции. Постарайтесь понять, для чего нужна каждая из них. Теперь откройте dictionary.c. Обратите внимание, что мы реализовали все четыре функции не полностью, а лишь настолько, чтобы код мог компилироваться. В конечном итоге, ваша задача — восстановить эти функции так, чтобы проверка орфографии работала, да ещё и быстро!

Makefile

Возможно, вы ещё помните о том, что команда make автоматически компилирует ваш код таким образом, чтобы вам не нужно было запускать clang и мучиться с его настройками.
Однако по мере роста ваших программ, make больше не сможет определять, опираясь на контекст, каким образом нужно компилировать ваш код. В таком случае вам понадобится сообщить make, как это сделать. Давайте мы используем файл настройки конфигурации Makefile, который и определяет, что именно должна делать make. Откройте Makefile.
Строка ниже определяет переменную, которая называется CC, которая указывает, что make должна использовать clang для компиляции.

сс = 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. Её значение равно списку разделенных пробелом файлов Си, которые вместе реализуют проверку правописания.

SRCS = speller.c dictionary.c

Строка под ней определяет переменную OBJS. Её значение идентично SRCS, только расширение каждого файла здесь равно .c, а не .o.

OBJS = $(SRCS:.c=.o)

В строке ниже определена “цель” использования данных переменных, которая подсказывает, как make будет компилировать программу.

$(EXE): $(OBJS) Makefile
$(CC) $(CFLAGS) -o $@ $(OBJS) $(LIBS)

Следующая строка определяет, что все наши .o файлы “зависят” от dictionary.h и Makefile. Так что изменение любого из них повлекут перекомпиляцию .o-файлов при следующем запуске make.

$(OBJS): $(HDRS) Makefile

Наконец, в строках ниже определена другая цель по очистке директории этой задачи.

clean:
rm -f core $(EXE) *.o

Теперь, когда вы разобрались со значением кода в Makefile, вы можете менять его, как угодно. Правда, менять вам его в любом случае придётся, если создадите собственный файл с разрешением .c или .h. Но при этом постарайтесь не менять табуляцию (напр., \t) на пробелы, так как make ожидает именно их. Также лучше будет
Благодаря этим строкам кода вы можете скомпилировать speller одной командой, невзирая на то, что в него входит несколько файлов:

make speller

Более того, вы можете просто запустить:

make

И если вы захотите удалить speller и любые core или файлы .o, это можно сделать с помощью одной единственной команды:

make clean

То есть для компиляции кода этого задания достаточно следующей команды:

make

speller.c

Откройте speller.c и посмотрите на код и комментарии. Вам не потребуется ничего менять в этом файле, тем не менее, важно понимать его содержание. Обратите внимание, как с помощью getrusage, мы будем замерять время исполнения ваших реализаций файлов check, load, size и unload.

Также обратите внимание как мы запускаем check: содержимое файлов проверяется слово за словом. Из всех ошибок и статистических данных составляется отчет.

Мы определили использование speller следующим образом:

usage: speller [dictionary] text

где text — файл, в котором мы проверяем орфографию, а dictionary — файл, содержащий список слов со строчной буквы, по одному в каждой строке.

Использование dictionary является опциональным, о чём нам сообщают квадратные скобки; если этот аргумент опустить, speller будет использовать /home/cs50/pset5/dictionaries/large по умолчанию.

Другими словами, запуск

./speller text

эквивалентен запуску

./speller dictionaries/large text

в котором text — это файл, в котором мы проверяем орфографию. Очевидно, первый вариант набрать и не ошибиться — гораздо проще! Разумеется, speller не может подгружать словари до тех пор, пока вы не реализуете load в dictionary.c! А до тех пор вы будете видеть надпись Could not load (загрузка невозможна).

Напоминаем, словарь по умолчанию содержит 143 091 слово, и их нужно загрузить в память. Загляните в файл, чтобы разобраться в его структуре и размере. Каждое слово в нем написано со строчной буквы (даже имена собственные и аббревиатуры).

Сверху вниз файл упорядочен по лексикографическому принципу, по одному слову в строке. Каждая строка заканчивается символом \n. Слова не повторяются, и каждое из них короче 46 символов. Во время работы вам может быть удобно предоставить speller ваш собственный dictionary с гораздо меньшим количеством слов, чтобы при отладке не загружать в память всякий раз огромный массив данных.

Вы можете найти такой словарик в папке /home/cs50/pset5/dictionaries/small. Чтобы его использовать, выполните команду:

./speller dictionaries/small text

Здесь text —файл, который вы проверяете на ошибки. Не переходите к следующему этапу до тех пор, пока вы не поймете, как работает speller!

Скорее всего вы не особо углублялись в изучение speller.c. Вернитесь на шаг назад и снова осмыслите процесс! Только не поддавайтесь искушению разбираться во всём этом слишком глубоко, иначе рискуете попасть в бесконечный цикл.

questions.txt

Откройте questions.txt и ответьте на вопросы одним или несколькими предложениями.

  • Что такое pneumonoultramicroscopicsilicovolcanoconiosis? (0_0 Google точно знает!)
  • Каково предназначение getrusage, согласно странице справочника man?
  • Согласно этой же странице, сколько полей в переменной типа struct rusage?
  • Как вы думаете, почему мы передаем параметры before и after по ссылке (вместо передачи по значению) в calculate, несмотря на то, что мы не изменяем их содержание?
  • Объясните максимально точно, каким образом main может считывать слова из файла. Другими словами, убедите нас, что вы действительно понимаете, как работает цикл с параметром функции main.
  • Как вы думаете, почему мы использовали fgetc и считываем каждый раз одну букву в слове, вместо того, чтобы использовать fscanf со строкой формата “%s” для чтения всего слова сразу? Подумайте, какие проблемы могут возникнуть, если использовать только fscanf?
  • Почему мы объявили параметры для check и load как константы (const)?

texts

Для проверки реализации speller’а мы подготовили несколько текстов. Среди них — сценарий фильма «Остин Пауэрс: человек-загадка международного масштаба», звуковой фрагмент из Ральфа Виггама, три миллиона байт из Льва Толстого, выдержки из Макиавелли и Шекспира, полное издание Библии Короля Якова V и другое.

Чтобы осознавать, что вам предстоит, откройте и просмотрите все файлы. Они лежат в каталоге texts в вашей директории pset5.

После (относительно!) внимательного изучения speller.c вы знаете, что результат работы speller, если выполнить, скажем, ./speller ~cs50/pset5/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’а (то есть, сумма предыдущих четырёх параметров). 

Внимание! Данные числа (время) могут меняться во время реализации speller, в зависимости от того, какие ещё процессы запущены в «Виртуальной лаборатории» или CS50 IDE, даже если вы не меняете код.

Кстати, чтобы внести ясность, под «ошибками» мы подразумеваем слова, которые не внесены в dictionary.