Юруков на живо

Ако не знаете какво е Assembler, няма да разберете защо ми е толкова яко. Assembler е бил основният език за програмиране преди 30-40-тина години. После се появяват езици от по-високо ниво като Fortran, Pascal, Ada и т.н. Все още обаче при писането на драйвери се използва асемблер.

Каква е връзката обаче тук? Нашите умни професори са решили, че е от особена важност да научим асемблер и то в късните семестри - след като сме се занимавали бая с Java. По принцип няма лошо - това е част от историята и наистина развива алгоритмичното мислене. Проблемът е, че професорът тази година такива неща дава, че не е истина. Едно, че имаме изпит, трябва да се предават домашни всяка седмица с по две задачи и куп подточки. Освен това всеки две седмици имаме да предаваме проект. И всичко това е на асемблер и не ни влиза в оценката. Ако не го направим обаче, няма да ни допуснат до изпита.

За да ви дам представа какви са проектите, ето кратко описание на последният. Имаме в един файл списък с имена и номера. Форматирани са по определен начин. Трябва да прочетем имената едно по едно и да изградим бинарно дърво за търсене, т.е. всеки корен е по-голям от левият елемент и по-малък от десният. След като построим дървото, трябва да изпишем елементите в определен формат на екрана, като използваме дървото за да са сортирани. Другите изисквания са, че трябва да използваме максимум 512Кб памет и не трябва динамично да резервираме сегменти в паметта.

На пръв поглед изглежда лесно. На C и Java това може да се направи за максимум 15 мин. Тук обаче става дума за асемблер, където си говориш направо с процесора. Затова е обяснимо защо вчера ми трябваха 6 часа висене пред лаптопа да го направя. Пак си е малко. Добре, че вече съм работил с асемблер и имам добър усет към алгоритмите. Кодът стана 400 реда, а паметта, която използвахме - около 250 Кб. Можеше и по-малко, защото примерните списъци за тестване бяха само 14 Кб, но реших да действам на сигурно и направих са поддържа списъци до 100 Кб. или 3300 имена.

Ето кодът на програмата, примерен тест и заданието(на немски). Може да ги тествате с MIPS компилатора Mars:

Поради това, че не можехме да резервираме памет динамично, се наложи да направя голям буфер. В него един след друг слагах редовете с имената и номера във следният формат: 4 байта за адрес на ляв под-възел (child node), 4 байта за адрес на десен под-възел, фамилно име, “шапация”, първо име, “:”, номер. Когато съответният възел няма ляв под-възел, адресът е равен на нула. Първият ред от данните се взима за главен корен. После всеки следващ елемент се сравнява с него. Ако е по-малък - отива се на адреса на левият под-възел (или съответно десният) и се сравнява с него по същият начин. Така докато не се намери, че някой възел няма под-възел и съответният ред се добавя като такъв на правилното място. Така се изгражда бинарно дърво за търсене. За жалост не е балансирано и предполагам, че би могло лесно да се направи с този формат на данните. Тъй като в задачата пишеше да не го балансираме, реших да не си тровя живота допълнително.

Фактът, че прекарах 6 часа в писане на 10Кб код не ме отчая. Напротив - точно обратното. Накрая като завърших кодът намерих само един малък бъг, в последните 5 реда код, които написах. Като го оправих, всичко тръгна отведнъж. Мед ми капеше на сърцето. Вярно, че тествах двете малки функции - strcmp и онази за обръщане на string в число, но другите две - за въвеждането на възли в дървото и изписването на дървото на екрана, както и четенето от файла, не ги бях тествал. Този вид програмиране е толкова далече от това, което правя по принцип, че факта че стана ме зарадва страшно. Сега остава и проверяващият да е доволен и всичко ще е наред.

Тази статия е написана на 19 ноември 2007 в 20:22:26, има 665 думи и е в следните категории: Технологии и Интернет. Защитена е с лиценз CC BY-SA. Можеш да следиш коментарите по статията чрез този RSS 2.0 абонамент. Можеш да оставиш коментар, или trackback към твоя сайт.