Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#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 Vladimir Rutsky

Milestone: ha2-milestone1ha2-milestone2
Type: ожидается проверкаожидаются исправления

Замечания:

  1. Используйте тип size_t для индексов и размеров (for (int i = 0; i < count_chars_with_eof; ++i)).
  1. Передавайте неизменяемые объекты-классы по константной ссылке:
Compress_result huffman_compress(std::string const & input_filename, std::string const & output_filename);
  1. Используйте C++ версию заголовочного файла <memory.h>: <cmemory>.
  1. Используйте инициализацию массива здесь:
//size_t table_of_freq[count_chars_with_eof];
//memset(table_of_freq, 0, sizeof(table_of_freq));
size_t table_of_freq[count_chars_with_eof] = {0};
  1. Нет необходимости явно закрывать файлы здесь, они будет закрыт при уничтожении is, os при выходе из области видимости (в их деструкторах):
	ifstream is(input_filename, ios_base::binary);
	ofstream os(output_filename, ios_base::binary);
	write(os, tree_from_table, true);
	encode(is, os, code);
	write(os, "", true);
	//os.close();
	//is.close();

	return result;
  1. Избегайте магических констант:
if (get_statistic(input_filename, table_of_freq) == 5)

get_statistic() могла бы возвращать bool, а для кодов ошибок лучше использовать enum.

return "011000000001011111111";
  1. Не храните eof как отдельный символ в дереве символов. Вместо явного кодирования eof лучше хранить в качестве дополнительной информации количество символов, сжатых в файле. Для пустого файла размер сжатых данных должен быть 0 байт; для файла вида aaaabbbb размер сжатых данных должен быть 1 байт.
  1. При декодировании вы для каждого префикса битовой строки ищете - не найдётся ли символ, кодируемый данным префиксом. Это не оптимальный подход, необходимо декодировать символ, кодируемый с помощью k бит за O(k).

На моей машине в clang c оптимизациями -O2 на некоторых входных данных ваше решение декодирует более 5 секунд.

Вы можете, например, построить префиксное дерево для всех символов и спускаться по нему до листа --- в листе будет закодированный символ.

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

Использование std::string для битовых строк также, скорее всего, тормозит ваше решение.
Рекомендую попробовать либо хранить биты как биты в массиве чисел, либо использовать std::vector<bool>, либо std::bitset (максимальная длина кода ограничена).

Исправьте, пожалуйста, в течение 60 часов.

comment:2 Changed 7 years ago by kormyshov.mikhail

Type: ожидаются исправленияожидается проверка

Добрый день.

Все замечания постарался исправить.
Переписал поиск символа за O(k), но это почти не дало прироста скорости. Это и понятно, потому что у бинпоиска на таком маленьком массива небольшая константа.

Профилирование кода показало, что больше половины времени тратится на считывание и вычленение одного бита, поэтому реализация была дополнена аккуратной работой с буферами, что существенно ускорило программу. На моей машине в g++ весь набор smoke проходит за 15 секунд, при этом все тесты меньше 2 секунд.

comment:3 Changed 7 years ago by Vladimir Rutsky

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

comment:4 Changed 7 years ago by Vladimir Rutsky

Resolution: задача сдана
Status: newclosed

comment:5 Changed 7 years ago by Vladimir Rutsky

Milestone: ha2-milestone2

Milestone ha2-milestone2 deleted

Note: See TracTickets for help on using tickets.