undefined

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

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

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

Итак, перед нами стоит следующая задача: реализовать 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. Невзирая на то, что вы, скорее всего захотите предварительно “доработать” наш словарь по умолчанию с целью определить для него лучшую хеш-функцию, вы не сможете сохранить на диск результат любой подобной доработки с тем, чтобы повторно загрузить его в память для более быстрых дальнейших вызовов.
  • Вы можете использовать хеш-функции из книг или интернета, при условии, что вы даете ссылку на оригинал любой хеш-функции, которую вы интегрируете в ваш код.

Начинаем

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

  • Реализовать load. Советуем вам подготовить словари, меньше 143 091 слов, с которыми вы будете тестировать ваш код во время разработки.
  • Реализовать check. Советуем вам подготовить несколько малых файлов для проверки правописания, перед началом. «Войну и мир», например.
  • Реализовать size.
  • Реализовать unload. Обязательно высвободите память (free), которую вы выделили под load!
  • Еще немного подсказок:

    Не забывайте, 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
    Комментарии (56)
    Чтобы просмотреть все комментарии или оставить свой,
    перейдите в полную версию
    Александр # 0 уровень
    6 мая 2021
    Парни (и девушки), а кто понял, как посмотреть или запустить версии преподавателей курса?
    Александр # 0 уровень
    6 мая 2021
    Может кому пригодится, очень понятный пример принципа реализации TRIE: https://www.techiedelight.com/trie-implementation-insert-search-delete/ На всякий случай, если кто-то не знает, в сети есть перевод на русский коротких видео от преподавателей CS50: https://www.youtube.com/c/OnlineUniver/playlists Если Вы пока ещё на 1-й стадии депрессии - знайте, это скоро пройдёт :) Задание сознательно построено с прицелом, что студенту придётся сначала поизучать теорию и справочники, прежде чем он поймет детали задания. Я также как и многие, несколько дней потратил просто на чтение.
    mak7imt 0 уровень
    4 февраля 2021
    GAME OVER
    Ихтияр Кадыров 1 уровень, Шымкент
    19 ноября 2020
    Без valgrind: Результат вместе с Valgrind:
    All Cool 1 уровень, Харьков
    11 октября 2020
    долго я бился над этой задачей решил через хеш таблицу
    xacker 5 уровень
    26 июня 2020
    На три варианта программы (две с хэш-таблицами, одна - с деревом) у меня ушло где-то две недели времени. Да, задание сложное для тех, кто недавно услышал про указатели, структуры, хэш-таблицы и т.п., но и в процессе решения скилл прокачивается соответственно.
    Даниил 41 уровень Master
    14 марта 2020
    Ну и задание... Думал будет проще и быстрее. Сначала прочитал большую часть того что советовали из литературы - потратил грубо говоря день. Долго не мог въехать что от меня конкретно хотят. Потом вроде как осознав, то начал делать. Сначала решил делать через hash-таблицу, но что-то у меня не пошло (уже не помню что именно так как делал я подходами с относительно большими перерывами) и по этому решил сделать через Префиксное дерево (trie). Самое сложное - это было реализовать метод load() так как делая его ты должен придумать самую главную вещь - в каком виде и как будут организованы данные в твоей реализации и исходя из этого уже будут делаться другие методы (с него и стоит начинать написание решения). На него я потратил дня 2, не меньше. В итоге в сумме потратил наверное целых дня 3 или 4 на реализацию полноценного рабочего решения которое освобождало все ресурсы (без листика и ручки не получилось найти ошибку где я не освобождал память). Получился такой результат на файле kjv.txt:
    
    WORDS MISSPELLED:     33441
    WORDS IN DICTIONARY:  143091
    WORDS IN TEXT:        799460
    TIME IN load:         0.05
    TIME IN check:        0.68
    TIME IN size:         0.00
    TIME IN unload:       0.01
    TIME IN TOTAL:        0.74
    
    оптимизировать я уже не буду, ну его в баню.
    Елена 19 уровень, Екатеринбург
    25 февраля 2020
    Долго не могла понять как создавать hash table. Мне помогла вот эта статья, может кому-то пригодится, все разложено по полочкам: https://stackoverflow.com/questions/31930046/what-is-a-hash-table-and-how-do-you-make-it-in-c
    Юрий 0 уровень
    28 ноября 2019
    Если честно, увидев задание, думал, это конец, и я не справлюсь. Но потом решился взяться, долго изучал выбранный способ (деревья) с точки зрения теории случился прорыв, когда до меня дошло четко, что я не буду хранить буквы в дереве в явном, скажем так, виде, а там будут указатели, а их наличие и будет являться подтверждением того, что буква есть. Ну и потом понеслось, вот что вышло (понял по комментам, что соревнуемся в kjv.txt, так что для проверки брал его): WORDS MISSPELLED: 33441 WORDS IN DICTIONARY: 143091 WORDS IN TEXT: 799460 TIME IN load: 0.07 TIME IN check: 0.50 TIME IN size: 0.00 TIME IN unload: 0.04 TIME IN TOTAL: 0.60 Комментарии: как я понял, у меня хорошее время по всем функциям кроме чека, ну там есть где сократить, сам вижу, но пока и так доволен результатом, что у меня все вышло. 2\3 времени над заданием ушло на понимание того, что от меня хотят + написание загрузки словаря, его отладку. Очень помогли в этом чекпоинты. Считать слова отдельно пробегом по дереву не стал - просто сохранял в переменную каждый раз, когда поднимал флаг is_word. Во время всего курса рекурсия вызывала уныние и непонимание, но я, как мог, старался ее себе представлять, чтобы понять. И вот здесь это пригодилось: функцию unload через рекурсию написал минут за 5 и без ошибок, т.е. с первого раза завелась. Ах да, когда дело дошло до valgrind, выяснилось, что у меня кучу проблем (столько же примерно сколько и malloc), кроме того, все ошибки указывали именно туда. Разобравшись, что не так (неинициализированные указатели все дела), подсмотрел в комментах функцию calloc (ранее не знал о ней), изучил и понял, что подойдет + изящнее выглядит, чем самому циклом инициализировать все свои узлы (ну и украл название переменной nodeSize, что уж). После этого valgrind успокоился, никаких утечек, так что добавлять результаты не буду. Да, комменты писал для себя, чтобы через время не забыть, что здесь происходит, может кому поможет чем.
    Татьяна 1 уровень, Казань
    17 июня 2019
    У меня не работает команда ~cs50/pset5/speller ~cs50/pset5/texts/austinpowers.txt. Сообщение об ошибке bash: ~cs50/pset5/speller: No such file or directory. Как правильно запускать? Папку cs50 дополнительно нужно в окружение загружать откуда-то?