25 декабря 2008 г.

Про IE

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

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

15 декабря 2008 г.

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

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

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

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


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

10 декабря 2008 г.

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

Даны 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*log2M. А для второго - N*M2.

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

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

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

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

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

9 декабря 2008 г.

Освобождение памяти в 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" Скотта Мейерса)

5 декабря 2008 г.

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

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

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