HA-2

[Волков Даниил]

Доброго времени суток!

Папка с решением II дз в репозитории ~/ha2

C уважением, Волков Д.В.

[Волков Даниил]

В связи с тем, что работа не была ещё проверена, а изменения в программе произведены довольно существенные по сравнению с первоначально выложенной версией - выявлены и исправлены утечки памяти и улучшена архитектура - отправляю свежий релиз.

---

Что исправлено.

Асимптотику построения дерева улучшать до O(N) вместо O(N logN) я посчитал нецелосообразным вследствие малости
вклада этого времени по результатам профилирования. Больше всего времени уходит на функции STL типа _M_assign,
fstream::write.

1. Fix huffman.cpp at 95.pos: (HuffmanTree::decodeData) Замена нескольких break -> return. До этого на каждом уровне вложенности цикла проверялось условие, что байты не кончились.
2. Fix huffman.cpp at 308.pos: (decoding) if (tree.freqsVector.size() == 1) блок перемещен на 308.pos, и в случае его выполнения не производятся лишние операции.
3. Fix all: добавлена структура HuffMagicNumbers, для избавления от магических констант. Теперь все константы задаются в одном месте.
4. Fix all: выравнивание по границе 80 символов.
5. Fix huffman.cpp at 292 pos: (recordEncodedData) for ... -> write(..., count). Вместо цикла записи по одному

байту можно сразу писать единственным вызовом функции write блока байт (хотя результаты бенчмарков не поменялись - в STL все равно циклическая запись).

6. Fix huffman.cpp at 305 pos:

так как при подсовывании программе пустого файла для раскодирования в таком случае ошибка доступа к памяти с падением.

7. unordered_map, основанные на хэш-таблицах, а не бывшие до этого map (на деревьях поиска) дают небольшой прирост производительности.
8. Fix huffman.cpp at 69-80.pos: добавление условий перед pop_back для массива char (утечка памяти? Неопределенное поведение?).
9. Добавлены ключевые слова const там, где это уместно.
10. Приведен в порядок заголовочный файл - убраны лишние декларации.
11. Fix huffman.cpp at 313.pos: add

if(tree.sizeInput > 0) delete[] tree.data;

т.е. исправлена утечка памяти в случае, когда распаковываем упакованный пустой файл.

---

Текущее состояние

Решение проходит smoketest с включенным valgrind'ом. Также я тестировал сжатие небольших файлов музыки и изображений, и разжатие обратно.

---

Вопросы

1. При запуске с такими параметрами valgrind --leak-check=full --show-leak-kinds=all распаковки некоторых файлов (в данном случае, пустого) получаем сообщения о каких-то утечках, суть которых осталась мне неясна.

   ==21888== HEAP SUMMARY:
   ==21888==     in use at exit: 72,704 bytes in 1 blocks
   ==21888==   total heap usage: 10 allocs, 9 frees, 100,197 bytes allocated
   ==21888== 
   ==21888== 72,704 bytes in 1 blocks are still reachable in loss record 1 of 1
   ==21888==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
   ==21888==    by 0x4EC3EFF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
   ==21888==    by 0x40104E9: call_init.part.0 (dl-init.c:72)
   ==21888==    by 0x40105FA: call_init (dl-init.c:30)
   ==21888==    by 0x40105FA: _dl_init (dl-init.c:120)
   ==21888==    by 0x4000CF9: ??? (in /lib/x86_64-linux-gnu/ld-2.23.so)
   

Запуск с более либеральными параметрами говорит, что проблем вроде бы нет.

2. Каким образом принято (или лучше всего в общем случае) поступать, когда нужно использовать много различных констант в коде (имеется ввиду, магических)? Я сделал таким образом, но думал конечно о том, чтобы писать #DEFINE MAGIC_NUMBER 42. Мой способ решения кажется мне довольно неуклюжим. Хранить же константы как приватные поля структуры дерева вроде тоже не очень (?).

---

Что планируется сделать

• На данном этапе моя структура не защищена от пользовательских модификаций. Сделать приватные поля и методы. Хотелось бы узнать, насколько это критичный баг для данного дз

[Волков Даниил]

Сейчас заметил, что указал неверный компонент к тикету. Исправил

[Vladimir Rutsky]

Замечания:

1. Принимайте аргументы, которые не планируете менять, по константной ссылке:

	static bool sortByFreq(const Node & a, const Node & b);

2. Не стоит указывать константной возвращаемых примитивных типов (в этом ну совсем нет смысла, в отличие от константных примитивных типов в аргументах функций). Плюс const void в качестве возвращаемого значения выглядит совсем странно.

3. В выводимой статистике размер доп. данных на 4 байт меньше фактического размера доп. данных.

Выводимая статистика распаковки не соответствует условию задачи.

4. Используйте более подходящую структуру данных для нахождения минимальных по частоте элементов дерева, чем сортируемый на каждой итерации массив. Например std::priotity_queue (но учтите, что std::priotity_queue не гарантирует порядок извлечения элементов с одинаковым приоритетом, поэтому вам нужно будет сделать свой компаратор явно стабильным).

Исправьте, пожалуйста, в ближайшее время.

[Волков Даниил]

Добрый вечер!
Исправил все пункты.

[Vladimir Rutsky]

Даниил, при сжатии aaaaaaab0x0A.2.in вы выводите, что сжатых данных 3 байта, а должно быть два.

[Волков Даниил]

Внес исправления

[Vladimir Rutsky]

При сжатии файла 0D0A0A0A0B.in вы выводите:

5
1
19

хотя результирующий файл размером 21 != 1 + 19.

[Волков Даниил]

Написал в slack'e про случай

aaaaaaab0x0A.2.in 

[Vladimir Rutsky]

Вы написали в Slack, что для файла aaaaaaab0x0A.2.in у вас получаются следующие коды:

10 ("\n") - "1"
98 ("b") - "01"
97 ("a") - "00"

а встречаются они:

10 ("\n") - 1
98 ("b") - 1
97 ("a") - 7

Символ перевода строки, который встретился один раз, имеет более короткий код, чем символ "a", встретившийся семь раз. Вам не кажется такой результат странным?

[Волков Даниил]

Исправил компаратор

[Vladimir Rutsky]

Решение зачтено.

[Vladimir Rutsky]

Milestone ha2-deadline deleted