четверг, мая 31, 2007

Как пасти котов

Как пасти котов - это известная книга по управлению программистами. Я не читала, но, говорят, хорошая. А вот одна компания идею выпаса котов использовала в своей рекламе. Очень неплохо получилось.




Нашла по ссылке с sozy.livejournal.com

Memoization

Memoization (я встречала только один перевод на русский и он ужасен - "мемоизация") - это оптимизационный прием, который подробно с примерами описан в Википедии. Буквы r там в середине нет, все правильно!
Опишу вкратце. Идея состоит в том, чтобы результат вызова функции заносить в таблицу какую-нибудь. Позже, получив те же аргументы во второй раз, можно все заново не считать, а из этой таблицы вытащить. Таблица эта - не данность, она заполняется в процессе мемоизации. В итоге получаются некоторые потери по памяти в обмен на выигрыш по скорости. При этом надо помнить, что функция функции рознь и не для каждой функции этот метод можно использовать.

вторник, мая 29, 2007

Выступление The emperor's old clothes

The emperor's old clothes (.pdf) - это текст выступления Хоара. Оказывается, это выступление довольно известное, но я вот о нем только сейчас узнала. Почитала, интересно. Хоар там много рассказывает об Алголе, об ошибках, допущенных при разработке Алгол68.

четверг, мая 24, 2007

Спор Таненбаума-Торвальдса (1992г)

В 1992 году, когда Линукс был еще мало известен, Таненбаум и Торвальдс поспорили в группе comp.os.minix. Все началось с того, что Таненбаум раскритиковал то, что Торвальдс сделал Линукс монолитным, ведь надо использовать микроядро, оно лучше. А Линукс отбрасывает людей в 70-е. Линус Торвальдс не мог на такое не прореагировать и, со словами "Time for some serious flamefesting!", ринулся отвечать.
Несмотря на то, что сообщения перемежаются небольшими наездами, например Таненбаум, который преподает в вузе, говорит, что он Линусу никогда бы хорошую оценку не поставил: "Be thankful you are not my student. You would not get a high grade for such a design :-) "... Так вот, несмотря на наезды, это очень познавательная дискуссия на тему проектирования операционных систем. Сейчас она еще интереснее, потому что Линукс получил широкое распространение. Поэтому особенно любопытно читать доводы Таненбаума почему Линукс - ОС уже устаревшая на момент выхода.

Ссылки по теме:
comp.os.minix LINUX is obsolete - тот самый спор
Tanenbaum-Torvalds debate - статья в Википедии
"Just for fun. Рассказ нечаянного революционера" - биография Торвальдса

понедельник, мая 21, 2007

Может ли main возвращать void

Вообще по Стандарту C++ функция main обязана возвращать int. Насколько мне известно, так же обстоят дела и в Стандарте С. И объявление функции main как void main формально ведет к undefined behavior. Тем не менее, main очень часто объявляют как void, особенно в синтетических примерах, код при это генерируется нормально. В принципе, объявление main как void может привести к проблемам, в частности код может получиться непортируемым.
Возвращаемый результат функции main иногда становится предметом вялых религиозных споров. Лично я чаще объявляю void main.

Ссылки по теме:
Can I write "void main()"? Страуструп в своем FAQ'e рассказывает, что объявлять main как void некорректно

четверг, мая 17, 2007

У меня теперь Ajax-powered блог

Я уже очень давно хотела сделать нормальную секцию последних комментариев. Потому что долгое время у меня на блоге были не последние комментарии, а последнии комментарии к последним постам. Делалось это через хак, предложенный Блоггером. Все это было криво и неудобно.
Сейчас Блоггер модернизируют чуть ли не каждый день. В частности, появился фид комментариев, которого раньше не было. Можно перейти на новый шаблон, который обладает большими возможностями, чем старый. Вроде как там и последние комментарии довольно просто подключить. Но переходить на новый шаблон мне было лень. Поэтому я решила как-нибудь встроить комментарии из фида на страницу.
Муж дал мне свою ajax'овую рыбу и на ее основе я написала код, который вытягивает из фида комментариев последние несколько и встраивает их в sidebar. В IE оно не работает, виноват не Ajax, виноват фид комментариев.
Так что у меня появился повод написать про Ajax. Муж отказывается писать посты про Ajax, он считает что и так уже слишком много про него написано, а он знает про Ajax недостаточно (скромничает то есть). Я так не считаю, так что я напишу что знаю.
HTML страничка представляет собой набор тегов, которые браузер как-то разбирает. По итогам разбора браузер формирует так называемое DOM-дерево. DOM расшифровывается как document object model. Это дерево можно просмотреть. В FireFox это здесь: Tools->DOM Inspector. Более того, в DOM-инспекторе вы можете его поменять.
Некоторое время назад, не помню когда, появилась интересная штука с трудно произносимым названием XMLHttpRequest и мне пришлось с ней поработать году эдак в 2003. Позже она станет известна как Ajax. Расшифровывается как "Asynchronous JavaScript and XML". Если объяснять по-человечески, то это означает, что, используя язык JavaScript, вы можете откуда-нибудь запросить, скажем, XML документ. Но и это еще не все. После получения данные из этого XML'а вы можете встроить в DOM дерево. Перестраивание DOM дерева выглядит красиво, как смена страницы без перезагрузки. В 2003 это смотрелось просто волшебно, ну и сейчас тоже ничего смотрится, хотя стало уже привычным.
Итак, мне нужно запросить фид комментарив и встроить его в DOM дерево. Код того, как это делается, можно посмотреть в исходнике основной странички блога.


function createRequest(){
try{
return new XMLHttpRequest(); //создаю объект запроса
} catch(Exception) {
return new ActiveXObject("Msxml2.XMLHTTP");
//если создание не удалось, то это IE(<7)
//здесь все происходит несколько иначе
}//try
}//createRequest

function getXML() {// функция получения XML
//тут лежит фид комментариев
var url = 'http://alenacpp.blogspot.com/feeds/comments/full';
var request = createRequest();

//создаю красивую картинку, которая будет веселить пользователя,
//пока XML не прогрузится
//в случае быстрого соединения ее не видно
//картинка опциональна, можно ее не добавлять вообще
var image = document.createElement('IMG');
image.src = "http://www.softwaremaniacs.org/Images/alenacpp/ajax-loader.gif";

request.onreadystatechange = function() {
//callback, который отрабатывает по ходу запроса
if (request.readyState != 4) //запрос окончен
return;
image.parentNode.removeChild(image); //убираю красивую картинку
if (request.status != 200) //запрос окончен без ошибок
return;
//полученный XML передаю в функцию парсинга
parseComments(request.responseXML);
}//onreadystatechange

//вставляю красивую картинку в DOM-дерево
var comments = document.getElementById('LastComments');
comments.parentNode.insertBefore(image, comments);

request.open('GET', url);
request.send('');
}//getXML

function parseComments(xml) {
var comments = document.getElementById('LastComments');
//это UL, к которому я буду добавлять LI элементы

var elements = xml.getElementsByTagName('entry');
//получаю элементы с нужным мне тегом
for (var i = 0; i < elements.length && i<6; i++) {
var li = comments.appendChild(document.createElement('LI')); //создаю LI

//создаю ссылку на комментарии
var links = elements[i].getElementsByTagName('link');
var link;
for (var j = 0; j < links.length; j++) {
var rel = links[j].getAttribute('rel');
var type = links[j].getAttribute('type');

if(rel == 'alternate' && type == 'text/html') {
link = links[j].getAttribute('href');
break;
}
}

//создаю дату
var date = elements[i].getElementsByTagName('published')[0].firstChild.nodeValue;
var date = date.replace(/(\d+)\-(\d+)\-(\d+).*/, '$3.$2.$1');

//заполняю LI
li.innerHTML = date+" :: "+'<a href="'+link+'" >'+elements[i].getElementsByTagName('author')[0].getElementsByTagName('name')[0].firstChild.nodeValue +'</a>';
}//for
}//parseComments

getXML(); //функция, инициирущая загрузку XML

Если вы смотрели код главной страницы блога, то заметили, что там все слегка не так. Это потому что подлые блоггеровцы поменяли возвращаемый content-type фида комментариев после того, как я добавила этот кусок ajax'а. Пришлось слегка извратиться, изврат не работает в IE. Поэтому мне все же, наверное, придется переходить на новый шаблон.

Ссылки по теме:
Бонус - генератор красивых картинок на загрузку

вторник, мая 15, 2007

Маленький спеллчекер

В статье How to Write a Spelling Corrector Питер Норвиг пишет маленький спеллчекер (21 строка на Питоне) и подробно рассказывает как он работает.
Вчера на teideal glic deisbhéalach Брайан О'Салливан написал о портировании этого кода на Хаскелл: Norvig’s spell checker and idiomatic Haskell.

пятница, мая 11, 2007

Ссылки на описание архитектуры Итаниумов

На блоге Not a kernel guy приведено несколько ссылок для интересующихся архитектурой Итаниумов: Отладка кода на Itanium (IA-64).

Начато бета-тестирование декомпилятора Hex-Rays

Hex-Rays - декомпилятор, над которым работает Ильфак Гильфанов, автор дизассемблера IDA Pro. Он немного рассказывал об этом декомпиляторе на своем блоге: Decompilation gets real. Сегодня же он написал, что теперь у этого декомпилятора появилось имя и по нему уже есть небольшой мануал.
Декомпилятор не может восстанавливать исходники по бинарникам, как может показаться. Но он может генерировать неплохой код, который гораздо проще анализировать, чем то, что выдаст дизассемблер. Выглядит это вот так:


Там в комментариях вспомнили другой декомпилятор, REC. Я с ним немного знакома, я его использовала когда играла в ngsec games и мне этот REC понравился. Так вот в комментариях говорят, что Hex-Rays сильно круче. От себя добавлю, что у REC'а есть одно очень сильное преимущество - он халявный :-).

вторник, мая 08, 2007

Книга "Стандарты программирования на С++"


Книга "Стандарты программирования на С++. 101 правило и рекомендация" у меня была в списке "надо прочесть". Я ее прочла, могу теперь поделиться впечатлениями.

Очень она мне понравилась. И дело не только в качестве советов - все они полезные, ясно сформулированные, с наглядными примерами. Прелесть этой книги еще и в том, что делавшие ее люди явно старались, чтобы мне было ее читать удобнее. Привычное разбиение на отдельные независимые главы - книгу удобно читать, если не располагаешь большим количестовм времени. В конце все советы приведены списком с кратким описанием. Качество соответсвует именам авторов: Герб Саттер и Андрей Александреску.

Обычно в книгах по ходу дела сложность возрастает. Тут не так - простые и сложные советы перемешаны. Не могу сказать хорошо это или плохо, просто вот такая вот особенность. По общей сложности я бы ее отнесла в раздел "Для продолжающих".

Я ее читала в русском переводе. В целом он мне понравился, хотя перевод несколько странен. Там, например, переведены термины, которые обычно не переводятся: public inheritance переведено как "открытое наследование" вместо привычного "публичное наследование". Временами из-под русского текста хищно проглядывает текст оригинала: "Позволение вызывающему коду непосредственно работать с внутренними данными класса работает против представленной им абстракции и поддерживаемых им инвариантов."

Где купить:

"Стандарты программирования на С++" на Ozon.ru
А я в Библио-Глобусе покупала

Ссылки по теме:
Хорошие книги по С++
Хорошие книги по организации кода

понедельник, мая 07, 2007

Teraflops Research Chip

Teraflops Research Chip - экспериментальный чип, разработанный Интелом. Весь из себя инновационный 80-ядерный, а главное - очень быстрый, как видно из названия. На страничке Интела, посвященной этому чипу, есть описание, художественные фотографии и видеоролик.

Sergey_, спасибо за ссылку. (это уже становится доброй традицией :-) )

Пост "Золотой век русского программиста"

Пост на блоге Сергея Розовика - Золотой век русского программиста. Интересный взгляд на российский IT сектор.

Вообще очень советую этот блог почитать, меня особенно раздел "Архитектура" радует. Вот этот пост мне очень нравится: Complexity Fighting.

пятница, мая 04, 2007

Делаю категории

В новой версии Блоггера появились категории и, как вы, возможно, уже заметили я начала ими пользоваться. В русской версии Блоггера они почему-то называются "ярлыками", но суть та же.

Итак, я хочу сделать минимальное количество максимально полезных категорий.
Буду делать это очень аккуратно, буду смотреть как это влияет на синдикацию в ЖЖ. Очень не хотелось бы опять весь блог туда вывалить ненароком. После некоторых раздумий я решила сделать следующие категории:
cpp - посты про С++
programming - посты по программированию, но не по С++. Я раздумывала на тем, не использовать ли два тега для С++ постов - cpp и programming. Уже несколько таких двойных постов прошло. Но затем я подумала, что это будет очень неудобно людям, которые хотят почитать о программировании, но C++ им не интересен.
fun - сюда попадает все несерьезное типа непростой жизни тараканов и кулинарных заметок
robots - редкие посты про роботов
gamedev - посты о разработке игр. Сюда же попадут посты про DirectX
books - посты о книгах
me - редкие заметки непосредственно обо мне и об этом блоге

После расстановки этих "ярлыков", я опубликую линки на фиды по каждой из категорий.

Идеи были следующие: если вы программируете на С++ и юморить вам особо некогда - подписывайтесь на cpp и, опционально, на programming.
Если вас интересует программирование, но не на C++ - тег programming ваш.
Если вам программирования и так хватает, то тег fun.
Возможны варианты вплоть до таких экзотических как: вы занимаетесь закупкой книг по программированию - тег books.

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

После категорий буду разбираться с фидами комментариев.

четверг, мая 03, 2007

Мультиметоды

Что такое мультиметод обычно объясняется на одном классическом примере. Вот у нас есть иерархия неких фигур.

struct  Shape            {...};
struct Square : Shape {...};
struct Triangle : Shape {...};

И надо уметь строить их пересечение.
bool    overlap( Square& a, Triangle& b) {...}
bool overlap( Triangle& a, Square& b) {...}
bool overlap( Shape& a, Square& b) {...}
bool overlap( Square& b, Shape& a) {...}

И хочется, чтобы можно было определить функцию вроде
bool    overlap( virtual Shape& a, virtual Shape& b);

При вызове которой автомагически бы выбирался нужный из вариантов overlap.
Формальное определение этого всего: "механизм мультиметодов - механизм вызова виртуальных функций на базе более чем одного объекта".

В своей книге "Дизайн и Эволюция С++" (13.8) Страуструп рассказывает, что очень хотел бы, чтобы мультиметоды были в С++, но вот как-то не сложилось. И в С++09 тоже не сложится, похоже. Предложения по мультиметодам они задвинули куда-то далеко. Вот официальные бумаги по этим предложениям раз и два. (все примеры кода взяты оттуда, кстати)

Мультиметоды можно сделать с использованием RTTI и dynamic_cast'ов. Например вот так: Multiple Dispatch. A new approach using templates and RTTI. Там не все так просто, потому что хочется, чтобы не нужно было делать двойную работу и чтобы не нужно было переписывать куски кода в случае появления новых фигур.

Можно обойтись без RTTI и dynamic_cast'ов. Например как здесь: MultiMethods in C++: Finding a complete solution. Код получается довольно тяжелый. По мне так лучше с RTTI.

Про мультиметоды много и загрузочно можно почитать у Александреску в "Современном проектирование на С++". Глава 11. Она так и называется "Мультиметоды".

Ссылки по теме:
Multiple dispatch - статья в Википедии