Лекции
Начать
Начать обучение
JavaRush /Курсы /Harvard CS50 /Подготовка к практической работе. Знакомство

Подготовка к практической работе. Знакомство

Harvard CS50
5 уровень , 8 лекция
Открыта

Цели

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

Литература

  • Страницы 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. Обратите внимание, что мы реализовали все четыре функции не полностью, а лишь настолько, чтобы код мог компилироваться. В конечном итоге, ваша задача — восстановить эти функции так, чтобы проверка орфографии работала, да ещё и быстро!

Telegram

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.

Комментарии (12)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Shahin Уровень 2
13 сентября 2023
Мои ответы: 0. Это придуманное слово вымышленной болезни лёгких зародившаяся вдыханием кремнеземной или кварцовой пыли. 1. Ф-ция getrusage возвращает статистику использования сис-ных ресурсов. Возвращённые данные об использовании сис-ных ресурсов сохраняются в структуре, на которую указывает указатель usage 2. В структуре usage 16 полей 3. При передачи аргумента по ссылке,в функцию передаётся адрес объекта.Это делается для того,что минимизировать затраты ресурса компьютера. По этой причине при вызове ф-ции calculate передаётся аргументы before и after по ссылке. 4. "main" считывает слова из файла посимвольно при помощи фун-ии fgetc(), которая выступает в качестве параметра цикла "for". В цикле "for" задаётся несколько условий: 1) содержит ли строка алфавитные символы и апостроф(если содержит, добавить их в массив word); 2) является ли строка слишком длинной,чтоб быть словом.(если "да", пропустить её); 3) если слово содержит числа, пропустить; 4) если слово найдено: 1. увеличиваем счётчик, указ-ий кол-во найденных слов; 2. проверяем правописание этого слово (если слово написано с ошибкой,выводим его в консоль и увеличиваем кол-во неправильно написанных слов); 3. готовимся к следующему слову; 5. Потому что при использовании fscanf извлекается всё слово целиком из файла и невозможно будет поставить ограничения на проверку каждого символа в слове при помощи условных операторов 6. Потому что эти параметры неизменны и имеют фиксированный размер.
FeatHonnar Уровень 16
29 октября 2022
Пипец, все вопросы построены по принципу "ну ты поищи сам там где-нибудь, мы объяснять не будем, но иначе ты ничего не сделаешь" На русском источников почти нет, на английском либо углубляться в литературу, либо пытаться понять наборы из кучи терминов, которые тебе тоже, естесна, не объяснят. Справлюсь. И для таких, как я, оставлю в ответах наибольшую помощь, какую только смогу.
FeatHonnar Уровень 16
30 октября 2022
Полезно для понимания getrusage: https://www.youtube.com/watch?v=Os5cK0H8EOA&t=133s (Смотрите предысловие и блок непосредственно с getusage, благо, таймкоды там есть) https://ru.manpages.org/getrusage/2# (Описание всего, что входит в rusage на русском)
FeatHonnar Уровень 16
2 ноября 2022
Не уверен, что ответил на 100% верно, но вроде язык понятный: 0. Что такое pneumonoultramicroscopicsilicovolcanoconiosis? (0_0 Google точно знает!) -Самое длинное слово в английском, синоним к названию болезни "силикоз". 1. Каково предназначение getrusage, согласно странице справочника man? -getrusage возвращает подробную информацию о том, как и сколько памяти у нас в данный момент используется. Вся информация сохраняется в структуру rusage, где есть множество переменных, отвечающих за различную информацию о потреблении памяти (например, long ru_maxrss хранит информацию о том, сколько всего используется памяти на данный момент). 2. Согласно этой же странице, сколько полей в переменной типа struct rusage? -16. 3. Как вы думаете, почему мы передаем параметры before и after по ссылке (вместо передачи по значению) в calculate, несмотря на то, что мы не изменяем их содержание? -Потому что так мы экономим ресурсы компьютера. Без амперсанта программа бы сперва создала копию before и after, загрузила в функцию calculate, и далее бы функция работала с копиями, занимающими отдельное место в памяти. С амперсантом же мы передаем адрес переменных, после чего функция обращается непосредственно сразу к оригинальным before и after.
FeatHonnar Уровень 16
2 ноября 2022
4. Объясните максимально точно, каким образом main может считывать слова из файла. Другими словами, убедите нас, что вы действительно понимаете, как работает цикл с параметром функции main. -Сначала мы запускаем цикл for и с каждым повторением читаем символ из текста, сдвигая курсор вперёд. Если прочитанный символ является буквой или апострофом, мы сохраняем его в массив word (в слово) под определенным индексом и увеличиваем этот индекс на 1. Если индекс стал больше допустимого размера слова, то дальнейшие символы (относящиеся к данному слову) для нас не имеют ценности, поэтому мы аннулируем их и индекс Если символ является цифрой, то мы аннулируем все дальнейшие цифры, являющиеся частью данного числа, и индекс. Если индекс на данном этапе уже больше нуля (и, раз мы дошли до этого этапа, символ не является буквой, апострофом или числом), то мы заканчиваем наше слово, обновляем счетчик слов, проверяем его на орфографию и аннулируем индекс, создавая новое слово. Стоит упомянуть, что если символ является не буквой, апострофом или числом (и индекс в этом время равен 0), а, например, пробелом, точкой или иным знаком, то мы просто пропускаем этот символ и повторяем цикл.
FeatHonnar Уровень 16
2 ноября 2022
5. Как вы думаете, почему мы использовали fgetc и считываем каждый раз одну букву в слове, вместо того, чтобы использовать fscanf со строкой формата “%s” для чтения всего слова сразу? Подумайте, какие проблемы могут возникнуть, если использовать только fscanf? -Насколько мне известно, fscanf можно использовать для чтения символов. В таком случае разницы между fgetc и fscanf быть не должно. Но речь о чтении целого слова сразу. Тогда всплывает целый ряд проблем: Во-первых, функция не очень точно умеет определять конец слова, поэтому может занести в массив иные знаки, помимо букв. Во-вторых, если наше слово окажется длиннее заданной длины массива, то функция начнет перезаписывать иные данные в памяти, что легко может привести к ошибке сегментации. Ну и в-третьих, мы теряем достаточно много контроля, ведь обязаны сперва читать целое слово и только потом читать его посимвольно (если возникает такая нужда), а не взаимодействовать с каждым символов сразу 6. Почему мы объявили параметры для check и load как константы (const)? -Потому что это параметры, которые нет смысла как-либо менять? Ну а на практике это может быть полезно, чтобы случайно не поломать значения этих данных в ходе работы.
Shahin Уровень 2
13 сентября 2023
C чего это ты так решил "Стоит упомянуть, что если символ является не буквой, апострофом или числом (и индекс в этом время равен 0), а, например, пробелом, точкой или иным знаком, то мы просто пропускаем этот символ и повторяем цикл." ??? Согласно какой строчке кода в файле speller.c
FeatHonnar Уровень 16
14 сентября 2023
Я уже плоховато помню, что именно было в том задании, но вроде как иные символы, кроме вышеупомянутых, игнорируются методом исключения через if-else: -Это буква? Апостроф? Нет? Идем дальше. -Это цифра? Нет? Идем дальше. -Индекс больше нуля? Нет? Других условий нет, поэтому пропускаем данную итерацию. Т.е. мы пропускаем тот же пробел не потому, что у нас есть код, пропускающий пробелы, а потому что у нас просто нет кода, который как-то с этими пробелами взаимодействует. (но я это пишу при условии, что вообще не помню, что именно делал тогда в том задании)
Александр # Уровень 0
27 апреля 2021
Забавно, что книга, на которую ссылается задание www.howstuffworks.com/c.htm видимо совсем уж древняя: в примерах приведены функции, которые были уже удалены из стандарта Си. Например, на странице 18 предлагается скомпилировать и запустить код: 

#include <stdio.h>
#include <string.h>

void main()
{
    char s[1000];
    int count=0;
     while (gets(s))
        count += strlen(s);
    printf("%d\n",count);
}
Если это сделать, компилятор выдаст ошибку: implicit declaration of function 'gets' is invalid in C99, т.к. данную функцию удалили в релизе C2011 как опасную. upd Однако текст там очень понятно изложен. Зацените, например, проверку на ошибку открытия файла :) 

    f=fopen("out","w");
    if (!f)
        return 1;
Maksud Уровень 1
7 июля 2019
Есть вопрос почему в файле questions.txt 10 вопросов TODO, а в этой статье только 6.
Anonymous #376733 Уровень 3
10 мая 2018
Уточните, пожалуйста литературу начиная с "Введение в JavaScript, Ajax, JSON", а то не ищется ничего конкретного. По предыдущим пунктам ясно что это книги и разделы, а дальше что?
Ярослав Уровень 0
28 сентября 2020
Да это опечатка наверное... какой здесь JS... да и здесь и так хватает информации для изучения на неделю-вторую и без него.