Про IE

Открываю новую вкладку в IE7. По умолчанию стоит about:blank. Появляется новая вкладка, но работать с IE еще нельзя — довольно долго смотрю на красивое крутящееся колечко и надпись "Подключение..." За это время успеваю налить в кружку чай и поматериться на разработчиков.

Я не понимаю, почему нужно тратить столько времени на открытие пустой вкладки. Какое, нафиг, подключение? Куда? К about:blank? Я действительно не понимаю.

Цитата: Кериевски

В последние годы стало выходить столько литературы по разработке ПО, что не только читать не успеваешь, но и даже просто фильтровать — вместе с хорошими книгами куча всякой фигни на полках стоит, а пока не прочитаешь, не поймешь... Но иногда коллеги рекомендуют (или не рекомендуют) какие-то книги, и это здорово помогает в выборе.

Недавно мне порекомендовали книгу Джошуа Кериевски "Рефакторинг с использованием шаблонов". Очень понравилась. Толковый мужик, знает, о чем пишет. Как бы заполняет нишу между "Рефакторингом" Фаулера и "Шаблонами проектирования" Гаммы и его друзей.

Я позволю себе процитировать:

Если вы хотите повысить квалификацию разработчика, изучение эволюции программных проектов будет более ценно, чем изучение проектов самих по себе — ибо настоящая мудрость лежит в развитии.

Книга, к тому же, издается за подписью Фаулера.

Слияние отсортированных массивов

Даны M отсортированных массивов по N элементов каждый. Необходимо слить их в одну отсортированную последовательность.

Есть несколько способов сделать это.

Первый способ - сливать сортированные последовательности по несколько штук (например, по две) до тех пор, пока не останется одна. Это и будет искомая последовательность. Например, для М=4, есть массивы М1, М2, М3 и М4 длиной по N элементов. На первом шаге сливаем M1 и М2, а потом М3 и М4. Получим два массива М5 и М6 длиной по 2*N элементов. На втором шаге сливаем М5 и М6 и получаем искомую последовательность длиной 4*N.

Второй способ - сливать массивы все сразу. То есть, получить искомый отсортированный массив за один шаг.

Вопрос в том, какой из способов более эффективный?

Можно попытаться посчитать приблизительное количество операций сравнения. Для простоты примем, что количество исходных массивов является степенью 2, то есть 2,4,8,... Для первого способа количество операций сравнения будет равно N*M*2*log₂M. А для второго - N*M².

Видно, что для М=2 или 4 количество операций будет одинаковое для обоих способов. А вот дальше количество операций для первого начнет уменьшаться. При М=32 соотношение количества операций будет примерно 1/3 в пользу первого способа.

Однако, все это верно, если проводить все слияние в памяти. Если же предположить, что памяти достаточно на одновременное размещение только части массивов, то дело принимает совсем другой оборот.

Предположим, что памяти хватает только на обработку пары массивов. Следовательно, после обработки каждой пары массивов на любом шаге слияния, нам нужно сохранять на диск промежуточную последовательность, чтобы считывать ее на следующем шаге слияния. То есть, используя пример, нужно считать последовательности М1 и М2 и записать последовательность М5. Затем считать М3 и М4 и записать последовательность М6. Затем считать М5 и М6 и записать результирующий массив.

Если попробовать подсчитать, то получится, что на каждом шаге нужно считать М*N элементов и записать М*N элементов. При увеличении М количество шагов растет - K=log₂M. То есть количество операций чтения/записи будет равно 2*M*N*log₂M. А используя второй способ нужно считать и записать только 2*М*N элементов (потому, что для второго способа нужен только один шаг).

Получается, что при слиянии последовательностей, не помещающихся в памяти, все переворачивается с ног на голову - так как создание промежуточных массивов на диске довольно дорогостоящая операция, то намного выгоднее сливать все последовательности за один шаг, не смотря на количество операций. Похоже, что так.

Освобождение памяти в std::vector

Я почему-то раньше был уверен, что выделенную память в std::vector можно освободить присваиванием:

typedef vector<int> int_vector;

int_vector v;
v.resize(10);
...
v = int_vector();

Оказалось, ошибался. Так не освобождает. По крайней мере, стандарт не обязывает.

Следовательно, остался только один способ освободить память — с помощью vector::swap:

int_vector().swap(v);


(способ описан в "Эффективном использовании STL" Скотта Мейерса)

Задачи на собеседованиях: шаблоны проектирования

Вот такие вопросы еще задают на знание паттернов проектирования.

Описать недостатки паттерна singleton. Предложить решения устранения недостатков.

GCC и precision loss

В процессе портирования нашего линуксового проекта на Windows обнаружилась интересная вещь: наш компилятор GCC не умеет распознавать ситуации с присвоением из long в short и им подобные. То есть, распознавать, скорее всего, умеет, а вот сообщать о них — нет.

Вот простой пример:

int main (int argc, char **argv)
{
  unsigned long a = 0xFFFFFFFE;
  unsigned char b = a + 1;
  return 0;
}

Я, честно говоря, был немало удивлен. Специально этим вопросом не занимался, но был уверен, что такие ситуации GCC отслеживать умеет. Ан нет... Что самое интересное, большинство моих знакомых гуру тоже были в этом уверены. В нашем проекте, как и во многих других, известных мне проектах, используется GCC 4.1.2, некоторые используют 4.2. Вроде бы есть опция -Wconversion, но работает она только для fixed и floating point. В общем, подстава.

Думаю, что о важности такого предупреждения говорить не нужно. В MSVC++ эта ситуация легко отслеживается включением третьего уровня предупреждений — /W3. После портирования нашего проекта на MSVC++, мы смогли легко локализовать и исправить несколько ошибок, связанных как раз с некорректным преобразованием типов.

Но самое интересное не в этом. После длительного изучения документации по GCC, все-таки нашел :)

Итак, не прошло и 25 лет, как разработчики GCC все таки прониклись пользой отслеживания размерности типов. Начиная с версии 4.3 (первый релиз вышел в марте 2008 года, то есть, всего полгода назад) GCC умеет распознавать и сообщать о ситуациях с присваиманием из long в char и им подобных.

Опция -Wconversion, которая работала только для fixed и floating point теперь разделена на две опции -Wtraditional-conversion и -Wconversion. Подробности можно почитать здесь http://gcc.gnu.org/wiki/NewWconversion

Я проверил — на приведенный пример ругается "warning: conversion to ‘short unsigned int’ from ‘long unsigned int’ may alter its value". Аллелуйа!

Ура, товарищи! Даешь новые версии! Даешь новые баги! :)

Задачи на собеседованиях: наследование в C++

Очередной вопрос с собеседования, который часто спрашивают.

У нас есть некая иерархия классов. Нам нужно запретить наследование от какого-то класса. В Java для этого есть специальное ключевое слово final, но в C++ такого слова нет. Попытка наследования от финального класса должна пресекаться на этапе компиляции.

Javascript: "option" object и IE

Простой скриптик. Берет все input-элементы с именем "hiddenlist" и заносит их в выпадающий список "selectlist". Отображаться в списке должно значение value, а на сервер отсылаться значение id. В Firefox работает, а в Internet Explorer 7 — нет.

var elems = document.getElementsByName("hiddenlist");

var selectobj = document.getElementById("selectlist");
removeAllChildren(selectobj);

for (i = 0; i < elems.length; ++i) {   var optobj = document.createElement("option");   optobj.value = elems[i].id;   optobj.text = elems[i].value;   selectobj.appendChild(optobj); }
Почему-то в IE после вызова appendObject(optobj) поле text очищается, или просто игнорируется. А поле optobj.value обрабатывается нормально. В результате в IE после вызова скрипта имею список из N пустых строк, но при этом на сервер отсылаются правильные значения.

Пришлось сделать так:

for (i = 0; i < elems.length; ++i) {   selectobj.appendChild(document.createElement("option"));   selectobj.options[i].value = elems[i].id;   selectobj.options[i].text = elems[i].value; }
В этом варианте работает в обоих браузерах. Мне, в общем-то, все равно, хотя второй вариант мне кажется менее приятным для глаз. Однако, непонятно почему первый вариант не работает в IE.

Exceptions и Visual C++

Недавно понадобилось собрать STL-проект на Visual C++ 2008 без использования исключений.

Почитал мануал по компилятору, долго игрался с настройками проекта и ключами /EHsc... Что-то никак не получается отключить исключения.

Наконец, залез в код STL и обнаружил там некий волшебный макрос _HAS_EXCEPTIONS. Добавление в опции компиляции ключа -D_HAS_EXCEPTIONS=0 привело к нужному результату — исключения в STL отключились.

Припоминаю, что лет шесть назад пытался решить эту же задачу для Visual C++ 6.0. И решалась она абсолютно таким же способом, через _HAS_EXCEPTIONS. Вот я и думаю, то ли Microsoft что-то перемудрил с Visual C++, то ли я его "готовить" не умею?..

С праздником вас, дорогие коллеги! С днем программиста! :)

Updated: Если нужно линковаться с msvcrt.lib или msvcrtd.lib (опции компилятора /MD или /MDd), то нужно определить еще один макрос:
#define _STATIC_CPPLIB

Updated: Вот интересная статья в тему http://ccollomb.free.fr/blog/?p=34

Задачи на собеседованиях: графы

Задача про графы, которую часто задают на собеседованиях. Для людей, которые ранее не сталкивались с графами, неплохая разминка для мозгов.

У нас есть ориентированный граф и его матрица смежности. Необходимо разработать алгоритм, вычисляющий количество узлов графа, участвующих в циклах. Речь идет просто о количестве узлов. Нас не интересуют ни количество циклов, ни количество узлов в каждом цикле. Только общее количество узлов, задействованных в циклах данного графа.

UDP: Кстати, найдя кол-во узлов мы сможем ответить на общий вопрос о наличии цикла в графе. Иногда вопрос звучит именно так.