#52 closed ожидается проверка (задача сдана)
Домашнее задание №2
Reported by: | kormyshov.mikhail | Owned by: | Vladimir Rutsky |
---|---|---|---|
Priority: | проверка | Milestone: | |
Component: | HA#2 huffman | Version: | |
Keywords: | Cc: |
Description
Change History (5)
comment:1 Changed 7 years ago by
Milestone: | ha2-milestone1 → ha2-milestone2 |
---|---|
Type: | ожидается проверка → ожидаются исправления |
comment:2 Changed 7 years ago by
Type: | ожидаются исправления → ожидается проверка |
---|
Добрый день.
Все замечания постарался исправить.
Переписал поиск символа за O(k), но это почти не дало прироста скорости. Это и понятно, потому что у бинпоиска на таком маленьком массива небольшая константа.
Профилирование кода показало, что больше половины времени тратится на считывание и вычленение одного бита, поэтому реализация была дополнена аккуратной работой с буферами, что существенно ускорило программу. На моей машине в g++ весь набор smoke проходит за 15 секунд, при этом все тесты меньше 2 секунд.
comment:4 Changed 7 years ago by
Resolution: | → задача сдана |
---|---|
Status: | new → closed |
Note: See
TracTickets for help on using
tickets.
Замечания:
size_t
для индексов и размеров (for (int i = 0; i < count_chars_with_eof; ++i)
).<memory.h>
:<cmemory>
.is
,os
при выходе из области видимости (в их деструкторах):eof
как отдельный символ в дереве символов. Вместо явного кодированияeof
лучше хранить в качестве дополнительной информации количество символов, сжатых в файле. Для пустого файла размер сжатых данных должен быть 0 байт; для файла видаaaaabbbb
размер сжатых данных должен быть 1 байт.Исправьте, пожалуйста, в течение 60 часов.