Apr 13
Еще две лабораторные работы: бинарное дерево поиска и хеш таблица (хеш-таблица еще не документирована).
Исходники и примеры работы с классами - далее по тексту.
Apr 12
Очередня лабораторная работа по предмету “Архитектура ЕОМ” - работа с файловой системой используя интерпретируемые файлы. Под Windows для таких целей можно использовать либо bat/cmd-файлы, либо WSH. Так как батники мы не учили, а мне больше по душе использовать высокоуровневые языки, для выполнения лабы был выбран JavaScript.
Если кому понадобится - copy.js и readme к нему.
PS. Первая лабораторная была тоже на работу с ФС, только средствами С++.
Добавлено:
Обновил программу и readme.
Apr 10
Такая вот у нас третья лаба по “Методам и средствам компьютерных информационных технологий”. :)
Как вы помните декодировщик gif’а уже готов, теперь вот надо это записать в bmp-файл + научиться кодировать в gif-формат (т.е. от кодирования данных пл методу LZW никуда не денешься). У меня вот такой вопрос к читателям - как вы думаете, как это красивее всего сделать? В теории может не только gif будет, вдруг мне что-то в голову взбредет. :) Поэтому напрашивается реализация в следующем виде:
(графический формат) ↔ (некоторый несжатый формат) ↔ (графический формат)
На практике вижу 2 минуса:
- Перекодирование все же будет дольше, чем если его делать напрямую
- Перекодируемый файл, а точнее его расжатый аналог будет находится в памяти
С первым смирится можно. А вот со вторым - стоит ли это делать? Не будет ли это слишком накладно в плане расхода памяти?
Вот с этими вопросами я и обращаюсь к вам. :) Жду комментов. И побольше.
Apr 09
Как и обещал, сегодня будет рассказ о том, как я сдавал свой ungif.
Началось все просто замечательно - я забыл что и на каком месте находится в хедере gif-файла. В итоге препод меня оставил (сказал - давай, готовься) и ушел к своей дипломнице. Я в это время всё выписал что мне нужно было в тетрадку и… Стал ждать… Причем ждал не я один, кроме меня сдать ему лабы хотело еще как минимум 3 человека. После десяти минут ожидания я все-таки напомнил преподу о себе, на что получил ответ “ну тут диплом… подожди еще 5 минут.”. Сколько эти 5 минут длились я скромно умолчу. Наконец он подсел ко мне и я быстренько ему рассказал, что, как и где в gif-файле находится и показал работоспособность моей проги. Далее я боялся только одного - что он меня спросит, как это всё кодируется. Потому что строить таблицу LZW алгоритма для gif-файла у меня желания не было никакого. Но у него в голове созрел другой коварный план: во время рассказа о структуре gif’ов я ему сказал, что там присутствуют некоторые блоки, которые я игнорировал (т.к. мне они действительно были не нужны). Во время разбора файла я ему показывал, что там должно было находится. И вот он решил потестить мою прогу - удалить кусок файла, который я “пропускал” и посмотреть, как заработает моя программа. После удаления этого куска прога зависла… :( И препод, сказав “трудись дальше”, ушел просматривать лабораторную одногрупника. А я полез в коды… При этом думая - где же я так мог лохануться. В общем, оказалось, что я ему неправильно истолковал один момент при считывании из файла (момент касался считывания таблицы цветов). После удаления из файла куска, который действительно можно было удалить, дело пошло лучше - файл открылся, и к тому же правильно.
Потом был рассказ небольшой на тему: какие именно файлы мой ungif обрабатывает неправильно и почему. В самом конце состоялся показ одного из моих комментариев в кодах:
// ToDoИ прозвучала моя фраза - “ну я это к третьей лабе доделаю, ок?”. После чего в блокноте препода была поставлена дата и моя фамилия, что свидетельствовало о том, что вторая лабораторная по КИТам сдана.
PS. Или это всем влом лабы делать, или это я такой шустрый. Но вторую лабу я тоже сдал первый из потока. :)
Apr 06
Сегодня, уже через 3 часа уезжаю к бабушке с дедушкой, которых уже полгода не видел. :(
Так что до понедельника никаких новостей не будет.
PS. Свой декодировщик gif’а я сегодня все-таки сдал, как и первую лабу - первым из потока. :) Подробности в понедельник.
Ах да, еще одно - всех читателей моего блога поздравляю с Пасхой!
Apr 04
Вчера закончилась моя долгая борьба с форматом GIF. Как вы помните, это была вторая лабораторная работа по предмету “Компьютерные Информационные Технологии”.
Первая лабораторная работа (adaptive huffman) у меня делалась примерно 3 дня. На вторую ушло больше 4 недель. Правда две из них лаба спокойно пылилась у меня на винчестере, потому что никаких соображений по поводу того, что именно там было неправильно у меня не было. И вот после моего дня рождения меня пробило - я вьехал, что именно там было не так. Оказалось, что достаточно всего одного блока if-else, чтобы алгоритм стал хотя бы нормально завершаться.
До этого момента работа алгоритма проверялась по схеме пашет-не пашет и коды писались в консольном приложении. Как только он стал “пахать” - все быстро перенеслось на “окошки”. После чего я впал в ступор - алгоритм работал, но выдавал явно не то, что я от него хотел, т.е. на форму выводилось изображение, но не то, которое мне было нужно.
Все это происходило позавчера. Сдать я все хотел на следующий день - потому началась “погоня за ошибками”. В 4 ночи, после жесткого дебага всего алгоритма декодирования изображения в gif-файле (напомню, что в GIFе изображение кодируется с помощью алгоритма LZW), программа приняла относительно рабочий вид - изображение выводилось… Даже понять, что изображено на нем можно было (не на всех файлах, правда)… Но, выводилось оно все-таки немного неправильно. После некоторого момента часть изображения начинала смещаться в непонятном направлении. Обессиленный, я отправился спать, т.к. понять, почему это всё не работает я не мог.
Проснувшись утром, я все-таки решил пойти на практику по КИТам и показать преподу хотя бы то, что есть. Авось у него такие “гении” уже были и он подскажет, где может быть ошибка. Надежды, конечно были маленькие, но… Ну, в общем, им не суждено было сбыться - в универе алгоритм в тот день так и не заработал.
Пришел домой и сел все-таки доделывать этот мой декодировщик gif’а. Началось очень интересное попиксельное сравнение моего изображения с оригиналом. Была найдена точка, с которой начинались глюки. Далее начался дебаг кода. Оказалось, что блок if-else, который мной был добавлен с самого начала работал все-таки немного неправильно. Весь прикол в том, что этот блок к самому декодированию явно не относился. Он относился к чтению данных из файла. Изменил этот блок, запустил программу и… Увидел абсолютно правильное изображение. Ура, товарищи!
Осталось теперь это все сдать преподу. :) Но я уже доволен как слон - 4-х недельные муки закончились!
PS. Я вот сейчас часто ловить себя на мысли - “а если бы я не нашел этот баг…”. Мне страшно даже подумать, что бы со мной было.
Mar 12
С данного поста начинается цикл статей о написании десктопного RSS ридера. Окончание проекта - где-то к маю, по крайней мере к тому моменту должна уже быть работающая версия. Пишу на C++ и Qt, буду рад помощи. Так что, если захочется поучавствовать - веллкам в icq (625-585).
Планы на ближайшее время: сегодня и завтра буду думать над техзаданием. Если кто может помочь его написать, или у кого просто есть идеи относительно того, что там нужно - высказывайтесь. Попытаюсь учесть все, что напишете.
Mar 09
Сегодня, несмотря на плохое самочувствие (уже второй день горло болит), пришел в универ и сдал свой архиватор. Меня долго мучали. :) Сначала проверили, как он работает на тестовом файлике (его содержание - “aa bbb cccc ddddd”), потом меня заставили строить на листочке дерево и сравнивать мою выходную строку (то, что в файле находится) и ту, что должна получится. Дойдя до 2-го символа “c” препод сказал - “Ладно, нафиг. Показывай текст программы.” :)
В итоге вся проверка лабы заняла минут 20-30. Раньше я по столько лабы не сдавал. :)
PS. Препод просто супер: мало того, что на лекциях классно обьясняет, так еще и на практике не сильно придирается (если где-то ошибся - поправит, где нужно - поможет). То, что принимает долго - просто проверяет, насколько человек понял алгоритм.
PPS. Побольше бы нам таких преподов!
Mar 08
В предыдущем посте я писал уже об алгоритме FGK. Сегодня (точнее уже вчера) я все-таки доделал и архивирование и разархивирование. Все работает, но пока не так быстро, как хотелось бы. Ничего, посплю, поздравлю девушку с 8 марта и вечерком засяду оптимизировать. Т.к. в пятницу (да, да, мы в эту пятницу учимся) буду показывать это все преподу. Может еще что-нибудь посоветует. И если совсем уж пробьет на программирование - на выходных сразу буду делать 2-ую лабу по этому предмету - раскодировать и вывести на экран изображение какого-нибудь формата. Я себе выбрал gif (построен на алгоритме LZW), так что работы мне на все выходные хватит.
Если кто знает, где можно почитать (и желательно взять реализацию) хеш-таблицы - киньте линк.
Кстати, сегодня пришел к классному выводу - компилятор VS2005 офигенно медленный по сравнению с MinGW (windows-сборка GCC). Это показали тесты моего архиватора. Файл размером ~2,5мб VS2005 (release-режим, оптимизации особого эффекта не дали) заархивировала за 100 секунд, а MinGW (со всеми оптимизациями) - за 48 секунд. Есть над чем задуматься… Нет, мою любимую студию я не брошу - эргономичность у нее просто супер. Но если нужна будет скорость - компилировать буду MinGW’шкой.
Mar 05
Семестр начался просто офигенно. Целая куча предметов по программированию и целая куча лабораторных, причем некоторые из них довольно сложные. Вчера вот (точнее уже сегодня) всю ночь делал одну из них, а именно архиватор. Задали вот нам написать, предложили ~10-15 вариантов кодирования. Мне пришлось взять один из 3-го (и последнего) уровня сложности (т. к. экзамен писать не охота, а для тех, кто делает не 1-й уровень имеются “поблажки” :) ).
Собственно - адаптивный (или динамический) алгоритм кодирования хаффмана или алгоритм FGK (Faller, Gallager, Knuth). О самом алгоритме можно почитать здесь.
Я же скажу несколько слов об организации всего этого хозяйства:
- По-моему использовать нормальный класс дерева в данном случае - бред. Хотя если дерево построено на массиве и у k-го элемента сыновья 2k и 2k+1 - тогда что-то попробовать можно.
- От дерева требуется быстрый обход в ширину.
- Дереву не обязателен быстрый поиск.Хотя и желателен.
Я решил не использовать свое дерево (которое я пишу по еще одной лабе по другому предмету), а написать отдельное для этого случае на базе массива из пункта 1. Попарился полночи. В итоге - архивация данных уже работает. Над разархивированием пока раздумываю. Не могу придумать алгоритм, который бы мог не записывая весь файл в оперативку, а работая с помощью буфферов, раскодировал это все… Но думаю, все же найду решение.
PS. Побольше бы таких лаб. Если бы еще не было других - неинтересных, но тоже забирающих на себя кучу времени…
Последние комментарии