Комментарии 18
Хочу немного дополнить статью размышлением о том, что хватило ли 64 битов для хранения элементарного кода.
На самом есть случай, когда не хватило бы uint64_t, но размер сжимаемого файла должен быть больше 27777890035 байт, что равно почти 28 Гбайтам, не запредельный размер, но вряд-ли кто-то стал использовать данную реализацию для столь большого объёма данных. Для размышлений использовал последовательность чисел Фибоначчи.
#include <iostream>
#define array_length 64
int main()
{
uint64_t fr[array_length];
fr[array_length - 1] = 1;
fr[array_length - 2] = 1;
uint64_t sum = 2;
for (size_t i = array_length - 2, j = 3; i; i--, j++){
fr[i - 1] = fr[i] + fr[i + 1];
sum += fr[i - 1];
std::cout << j << "-ое число Фиббоначи - " << fr[i - 1] << ", сумма - " << sum << '\n';
}
return 0;
}
Процесс сжатия происходит за два чтения файла
немного включу зануду, но это при условии что вы не грузите файл в ОЗУ.
Здравствуйте, не совсем пынял, что Вы имеете в виду. В любом случае мы не можем напрямую работать с данными на дисках, всегда будет использоваться ОЗУ в качестве буфера. Данное замечание было сделано, так как изначально, до 2 редакции, реализация считывала данные из файла и писала по-байтово в динамический массив. Или Вы имеете в виду то, что так как поток на чтение был открыт, то часть данных останется в ОЗУ? Если честно не разбирался, но если Вам известны источники раскрывающие данную тему, то прошу Вас поделиться, был бы рад почитать.
ну если примитивно берём чистый ДОС без smartdrv и обращаемся к файлу через библиотеку стандартного ввода-вывода, то читая 1 байт, вы обращаетесь к диску, с которого считывается сектор (Х байт), но лично вашей программе отдаётся тот самый байт. Этот сценарий мы не рассматриваем.
В современных ОС прослойкой будет кеш системы, то есть даже читая с диска вы все равно во второй раз будете иметь дело с ОЗУ.
Но я и не такой сценарий имею в виду. Я о том, что по хорошему в программе имеет смысл делать две процедуры чтения, одна обращается к части файла по размеру выделенного буфера, а вторая тупо грузит весь файл в ОЗУ. Вот и получается, что дял современной системы большинство файлов просто уместятся в ОЗУ и ваша фраза "за два чтения файла" несколько некорректна, скорее "за две операция чтения данных". То есть описывая алгоритм не нужно создавать некие условия работы исключительно с диском, это просто данные, а на диске они или в ОЗУ - не важно.
Вот вам пример из моей программы, которая производит расчёт энтропии.
public static void CalcMap(ref ulong[] map_, string fn) {
Array.Clear(map_, 0, map_len);
try {
using (FileStream fsSource = new FileStream(fn, FileMode.Open, FileAccess.Read)) {
byte[] bytes = new byte[16777216]; int n;
while ((n = fsSource.Read(bytes, 0, bytes.Length)) > 0)
for (var i = 0; i < n; i++)
map_[bytes[i]]++;
map_[256] = (ulong)fsSource.Length; }
} catch (Exception e) { throw e; }
}
public static void CalcMapFast(ref ulong[] map_, string fn) {
Array.Clear(map_, 0, map_len);
try {
byte[] bytes = File.ReadAllBytes(fn);
for (var i = 0; i < bytes.Length; i++) map_[bytes[i]]++;
map_[256] = (ulong)bytes.Length;
} catch (Exception e) { throw e; }
}
Как видно по коду, я взял за основу 16 Мб и всё что меньше идёт через CalcMapFast с полным чтением в ОЗУ, а всё что больше читается порциями по 16 Мб в CalcMap.
Пынял, спасибо Вам большое за ответ, не задумывался о том, что в какой-то момент эффективней будет считать какое-то большое количество байт, чем считывать по одному.
Вы же в курсе что вы таким образом теряете оригинальный callstack ошибки?
Ваш вариант CalcMapFast принципиально ничем не отличается от CalcMap, можете посмотреть на реализацию ReadAllBytes
Крайне поверхностно знаком с языком Ассемблера, но данная ошибка вылезет же только в том случае, если процедура будет вызываться рекурсивно, разве нет?
Хм, если это вопрос ко мне - то тут нет языка Ассемблера и нет рекурсии. Поэтому не понимаю, о чем вы спрашиваете.
Не совсем пынямаю как может произойти call stack ошибка.
Не "call stack ошибка", а call stack или stack trace ошибки. Т.е. список вызовов до вызова, который выбросит исключение. В данном случае вызов любой системной функции внутри блока try/catch может выбросить исключение, которое будет отловлено в блоке catch и выброшено снова, но без информации об оригинальном списке вызовов.
Мне можно, я профессиональный говнокодер.
Ну для меня различия очевидны и они есть в коде. Но готов услышать от вас комментарии, я не против саморазвития.
В ReadAllBytes практически такой же цикл как у вас.
там
int num2 = (int)length;
byte[] array = new byte[num2];то есть память выделяется сразу вся в ОЗУ, что соответствует CalcMapFast, причем ограничение там только такое, мои 16 Мб по сравнению с ними просто ни о чём
if (length > int.MaxValue)а цикл
while (num2 > 0)
{
int num3 = fileStream.Read(array, num, num2);
if (num3 == 0)
{
__Error.EndOfFile();
}
num += num3;
num2 -= num3;
}он же не про чтение частями, просто filestream.Read возвращает число прочитанных байт, то есть формально для того чтобы всё же прочитать столько сколько нужно придется сдвигать offset (num) и менять count (num2). Тут смысл совсем иной.
Ваш текст "я взял за основу 16 Мб и всё что меньше идёт через CalcMapFast" - так что вы маленькие файлы читаете полностью в ОЗУ и они полностью влезают в ваши 16Мб, если читать их через CalcMapFast, так что ограничение на Int.MaxValue оно не про ваш случай. И в вашем цикле в CalcMap чуть меньше телодвижений (как раз про сдвиги смещений). И вы таже будете вычитывать данные в массив пока не прочтете весь файл (даже если он маленький и ОС будет вам отдавать его частями).
Эквивалентность кода довольно очевидна, но убеждать вас я не хочу.
Куча библиотек, а именно <vector>, <string> и <algorithm>
Почему это отнесено к недостаткам?
И раз сжимаются текстовые данные, почему бы не подсчитывать частоту слов, а не букв?
Использование сторонних библиотек всегда отпугивало, но решил включить, так как сам могу реализовать данные СД и алгоритм сортировки, пусть и в стократ хуже, чем в это представлено в данных библиотеках. Личная оценка автора статьи, грубо говоря.
Не совсем понял, что Вы имеете в виду. Если говорить в терминах теории информации, где слово - это R-бит, но чаще всего R-байт, то канонический алгоритм Хаффмана работает с однобайтовыми словами. Но мы можем в теории обрабатывать и 8-байтовые слова, то есть uint64_t, да и алгоритм Хаффмана относится к алгоритм сжатия на основе алфавита, сжатие данных на основе словаря это уже скорее про LZ.
Хочу немного дополнить статью размышлением о том, что хватило ли 64 битов для хранения элементарного кода.
На самом есть случай, когда не хватило бы uint64_t, но размер сжимаемого файла должен быть больше 27777890035 байт, что равно почти 28 Гбайтам, не запредельный размер, но вряд-ли кто-то стал использовать данную реализацию для столь большого объёма данных. Для размышлений использовал последовательность чисел Фибоначчи.
#include <iostream>
#define array_length 64
int main()
{
uint64_t fr[array_length];
fr[array_length - 1] = 1;
fr[array_length - 2] = 1;
uint64_t sum = 2;
for (size_t i = array_length - 2, j = 3; i; i--, j++){
fr[i - 1] = fr[i] + fr[i + 1];
sum += fr[i - 1];
std::cout << j << "-ое число Фиббоначи - " << fr[i - 1] << ", сумма - " << sum << '\n';
}
return 0;
}
«Hello, World!» от мира сжатия данных. Канонический алгоритм Хаффмана